Automaty skończone 2

Automat, gdzie sygnał wyjściowy zależy od wejściowego i stanu automatu to automat Mealy'<jo, zaś gdy jest wyłącznie funkcja stanu to automat Moore’a.

Do czego służy nam automat?

Sposób rozpoznawania języka przez gramatykę polegał na generacji poprawnych słów. Jak do tego podejdzie automat?

Bedzie rozpoznawał dowolne wczytane napisy i decydował czy ie akcentuje czy nie. Ogół słów akceptowanych przez automat to akceptowany przez niego język. Rozpoznawanie polega na zapisaniu na wejściu słowa do sprawdzenia, ustawienia urządzenia sterującego w stanie początkowym q a następnie wczytywaniu symbol po symbolu z wejścia i równoczesnym zmienianiu stanów według funkcji przejść. Jeśli po wczytaniu całego słowa dojdziemy do stanu końcowego, to jest ono akceptowane. Jeśli nie, to nie.

Przykład:

Prześledźmy język o parzystej liczbie takich samych liter. Mamy automat:

A= ({q. p. r}, {a}, P. q,{r},), gdzie: P (q, a) = p P (p, a) = r stany    stany

P (r, a) = p

symbol z wejścia

Podobnie, jak w przypadku parsera konfiguracja to para (p, w) gdzie w jest następnym nienrzeczytanym symbolem będącym częścią słowa (z jakiego zbudoyyane jest słowo). Jeśli nieprzeczytana część słowa jest pusta pojawia się symbol @.

Sprawdźmy akceptację słowa aaaa

(q, aaaa) =* (p. aaa) =» (r, aa) =*• (p, a) =*• (r, @)

Słowa o nieparzystej długości nie będą akceptowane! (otrzymam (p, @) zamiast stanu końcowego r.

Powyższy automat skończony pozwala zatem akceptować iezyki liniowe. Niestety, nie dla każdego języka bezkontekstowego da się zbudować automat skończony. Np. nie da się dla naszego aⁿbⁿ! Wynika to z braku możliwości pamiętania informacji o przeczytanej części słowa (np. o jego długości — liczbie znaków).