img195

195

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

ciąg numerów produkcji gramatyki, jakie zostały użyte podczas dotychczasowej analizy słowa.

Działanie automatu %Lll klasy LL( 1) zdefiniujemy w następujący sposób:

1)    konfiguracją początkową jest (rj, SZo, A), gdzie rj jest słowem, które będziemy analizować, S - znacznikiem końca (S € Er), S - symbolem startowym gramatyki;

2)    (a7,i4ir,¹r)l-(7,t,t) O 6(>4i,a) = rem, Ai € E, a £ E_r,

7 6 EJ., t 6 E¹, tc jest ciągiem numerów produkcji, I— - oznacza przejście automatu z jednej konfiguracji do drugiej;

3)    (a7,4ir,¹)l-(07, ot, tt«) <=► ^(-Ai,a) = (<r,i);

4)    (07, A\t, t)I— acc O 6(j4i,a) = acc, gdzie acc jest konfiguracją rozpoznania ciągu rj (i zakończenia działania automatu);

5)    (07, A\T, tt)I-err «=> 6(A\,d) = err, gdzie err jest konfiguracją

błędu - nierozpoznania ciągu rj (i zakończenia działania automatu).

Z tego opisu wynika, że zbiór słów akceptowanych przez automat %ll klasy LL( 1) definiujemy jako

T{¹ll) = {7 € EJ. | (_TS,5Z₀,A)h- ¹ -($,£<>,¹r)),

gdzie 7r jest ciągiem numerów produkcji gramatyki LL( 1) prowadzących do wygenerowania 7.

Sekwencyjnym trans djus erem 2 wielokrotnym wejściem^) (ang. sequ-ential multiple entry transducer) [24] nazywamy piątkę

ST = (Q, Br, A,

gdzie Q - skończony zbiór stanów, Et - skończony zbiór symboli wejściowych, A - skończony zbiór symboli wyjściowych, 6 : Q x E$» —♦ Q x A¹ - funkcja przejścia (przypadek deterministyczny), Qo C Q - zbiór stanów początkowych.

1

Nie należy mylić sekwencyjnego transdjusera z wielokrotnym wejściem z bardziej znanym z teorii automatów deterministycznym transdjuserem o skończonej liczbie stanów (ang.deterministic finite transducer) (25).