img194

194

D3. Podstawowe pojęcia teorii języków formalnych i automatów

Innymi słowy, z każdego nieterminala A do elementu zbioru first(A) możemy pójść tylko jedną drogą (tzn. dla nieterminala A i elementów zbioru first.(A) mamy zdeterminowaną, w sensie stosowania produkcji, drogę).

Po wprowadzeniu klas gramatyk, których używamy do generacji ciągu uczącego w rozdziale 10, zdefiniujmy podstawowe klasy automatów, wykorzystywanych jako mechanizmy rozpoznawania obrazów.

Deterministycznym automatem o skończonej liczbie stanów nazywamy piątkę

a = (£_r,Q,<5,_?0,F),

gdzie Et ~ skończony zbiór symboli wejściowych, Q - skończony zbiór stanów, 6 : Q X. Et —* Q - funkcja przejścia, qo - stan początkowy, F C Q - zbiór stanów końcowych. Zakładamy przy tym, że

%><*7) = 7 G Et, u 6 Et-

Przez rp(j) oznaczamy stan jaki osiąga automat a po przeczytaniu ciągu 7, tzn.

^rP(7) = %o,7)-

Zbiór słów akceptowanych przez automat a definiujemy jako r(ćl) = {7 e | %0,7) € F}.

Automatem Sin klasy LL( 1) [22,23] nazywamy czwórkę *ll = (Et,E,8,Z₀),

gdzie Et - skończony zbiór symboli wejściowych, E - skończony zbiór symboli stosu, S : E x Et —* {(<r,/), rem, acc, err}, cr 6 E*, / € ^ -funkcja przejścia, Zo - symbol znajdujący się na dnie stosu Zo € E.

W celu opisania działania automatu Sl_LL klasy LL{ 1) wprowadźmy pojęcie konfiguracji automatu. Konfiguracją automatu klasy LL( 1) nazywamy trójkę

(INPUT, STACK, OUTPUT),

gdzie INPUT € EJ. - ciąg symboli, jakie znajdująsię na wejściu automatu, STACK € E⁺ - ciąg symboli, jakie znajdują się na stosie, OUTPUT -

img194

img194

a = (£r,Q,<5,?0,F),

a = (£_r,Q,<5,_?0,F),