img192

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€Ew.

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: y3 = abcabcabc, I7I = 3, It3) = 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.


Wyszukiwarka

Podobne podstrony:
img193 D3. Podstawowe pojęcia teorii języków formalnych i automatów 193 t) -i-> 7 oznacza wyprowa
img194 194 D3. Podstawowe pojęcia teorii języków formalnych i automatów Innymi słowy, z każdego niet
img195 195 D3. Podstawowe pojęcia teorii języków formalnych i automatów ciąg numerów produkcji grama
img196 196 D3. Podstawowe pojęcia teorii języków formalnych i automatów Zapis 6(q> 7) = (g ,*?) o
img191 Dodatek 3Podstawowe pojęcia teorii języków formalnych i automatów Podstawowe pojęcia teorii j
img191 Dodatek 3Podstawowe pojęcia teorii języków formalnych i automatów Podstawowe pojęcia teorii j
img198 198 D4. Wybrane pojęcia teorii języków drzewowych i grafowych gdzie j4,i4i,j42ł...,j4r(a) € E
img197 Dodatek 4Wybrane pojęcia teorii języków drzewowych i grafowych W dodatku znajdują się definic
img197 Dodatek 4Wybrane pojęcia teorii języków drzewowych i grafowych W dodatku znajdują się definic

więcej podobnych podstron