img192

192

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

Zakładamy przy tym, że £ = £/v U Et oraz E^r fi Er = 0.

Gramatyką struktur frazowych nazywamy gramatykę, której produkcje są postaci:

V—>y, gdzie t) e E*E/vE’, 76E*.

Ciąg rj składa się zatem z przynajmniej jednego symbolu nieterminalnego, przed (i po) którym może znaleźć się pewna liczba symboli alfabetu E. Ciąg 77 jest nazywany lewą stroną produkcji, natomiast 7 - prawą stroną produkcji.

Gramatyką kontekstową nazywamy gramatykę, której produkcje są postaci:

ł?i^2—* Vi7V2> gdzie >?i,»72€£*, 7€£⁺, i€E_w.

Tak więc, gramatyka kontekstowa pozwala na zastąpienie symbolu nieterminalnego A niepustym ciągiem symboli 7 wtedy, gdy A pojawiło się w kontekście ciągów tji i r^.

Gramatyką bezkontekstową nazywamy gramatykę, której produkcje są postaci:

A—>7, gdzie A 6 £^, 7££⁺.

W przypadku gramatyki bezkontekstowej, nieterminal A jest zastępowany przez niepusty ciąg 7, niezależnie od kontekstu, w jakim się znąjduje A.

Gramatyką prawostronnie (lewostronnie) regularną nazywamy gramatykę, której produkcje są postaci: A —► 7G (dla gramatyki lewostronnie regularnej: A —► Gy) lub A —► 7, gdzie A,G 6 £jv, 7 6 Ej.

W literaturze dotyczącej teorii języków formalnych dają się zauważyć rozbieżności pomiędzy postaciami przytaczanych definicji gramatyk według klasyfikacji Chomsky’ego. Głównie dotyczą one sposobu określania ciągu 7. Podane definicje przedstawiono opierając się na pracach Chom-sky’ego (np. [21]).

Jeśli 7 £ E⁺, to przez 7" oznaczymy ciąg powstały przez przepisanie ciągu 7 n razy, a I7I oznacza długość (liczbę symboli z alfabetu E) w ciągu 7. Przykładowo, dla 7 = abc: y³ = abcabcabc, I7I = 3, It³) = 9.

t] —* 7 oznacza (bezpośredni) krok wyprowadzający w gramatyce ©, tzn. jeśli i) = a\\a-i i 7 = <T\TOi, to istnieje produkcja \ —* r 6 P.