Automaty skończone 1

Automaty skończone 1



Automaty skończone

Zanim podamy formalna definicję automatu skończonego spróbujmy go przybliżyć.

Za automat skończony możemy przyjąć układ mający pewną liczbę np. / wejść i innąnp. k wyjść. Istotną rzeczą jest, że sygnały x występujące na wejściu należą do skończonego zbioru symboli wejściowych X. zaś sygnały wyjściowe y należą do skończonego zbioru sygnałów wyjściowych Y.

Ze względu na skończoność zbiorów symboli wejściowych i wyjściowych mówimy o automatach skończonych.

Automat taki przedstawia poniższy rysunek:

Automat posiadający tylko sygnały wejściowe i wyjściowe jest dość ubogi. W automacie tym dany zestaw sygnałów wejściowych wywoła zawsze ten sam sygnał wyjściowy. Taki automat nazywa się często układem kombinacyjnym. Jest on jednak użyteczny — służy do projektowania układów logicznych.

Bardziej skomplikowane i ciekawe to układy sekwencyjne, gdzie reakcja automatu na sygnał wejściowy zależy od "historii automatu", czyli od tego jakie sygnały odbierał automat w przeszłości. Wiedza automatu o jego "historii" zawarta jest w zbiorze stanów wewnętrznych Si.... Sp. Stany te wraz z sygnałem wejściowym Xj określają stany wyjściowe Yj.

automat z wyróżnionymi stanami

Możemy teraz podać formalną definicję automatu skończonego.

Jest to niatka elementów:

A = (Q, T, P. q. F), gdzie:

Q — skończony i niepusty zbiór stanów,

T — alfabet służący do budowy języka (alfabet terminalny),

P — funkcja przejść — opisująca zmianę stanu (w jakim sensie analogon zbioru produkcji w gramatyce), q — wyróżniony stan początkowy, F — zbiór stanów końcowych.

Funkcja P określona jest na iloczynie kartezjańskim T x Q i przyjmuje wartość w Q czyli

F: T x O =» O

czyli w oparciu o sygnał wejściowy € T i stan wewnętrzny € Q określa nowy stan wewnętrzny € Q.


Wyszukiwarka

Podobne podstrony:
-język formalny L definiujemy matematycznie jako: L = <X, Syn, DSem, Sem> X - alfabet, skończo
Ćwiczenie 5 Katedra Informatyki i Automatyki Politechnika RzeszowskaZarządzanie bazą danych za pomoc
Uczę się pisać  Narysuj poniżej taki sam obrazek. Gdy skończysz, pokoloruj go ulubionymi
9777295166 Zadanie egzaminacyjne Drzwi automatycznie otwierane (przesuwane) sterowane są za pomocą
Slajd3 FORMALNA DEFINICJA DEMOGRAFII „Demografia —jest nauką traktującą o prawidłowościach rozwoju
Uczę się pisać  Przerysuj i pokolorujNarysuj poniżej taki sam obrazek. Gdy skończysz, pokoloruj go
Elementy teorii sieci Petriego: podstawy formalne - definicje, reprezentacje, własności, klasyfikacj
pdl2 szło, węgiel mu sic walił i zarobił dużo. W do ma bieda sic skończyła. I tak płynął rok za rok
Technika cyfrowa Formalna definicja FSMD rozszerza definicję FSM przez wprowadzenie zbioru zmiennych
258 2 258 7. Różnice skończone w całkowaniu i różniczkowaniu Przybliżone oszacowania błędów zaczynaj
Formalna definicja drogi (język modelowania ST), podaj przykład Drogą - w grafie G , z węzła a do wę
P1080920 IRENEUSZ ZIEMI,% świat w sobie bowiem z definicji może być nam dany wyłącznie za pośrednict

więcej podobnych podstron