Postać normalna Chomsky'ego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Postać normalna Chomsky'ego to postać gramatyki bezkontekstowej, w której wszystkie reguły (inaczej: produkcje) są postaci:

A \rightarrow a
A \rightarrow BC

gdzie małe litery oznaczają symbole terminalne, duże zaś nieterminalne.

Każdą gramatykę bezkontekstową niegenerującą symbolu pustego można przekształcić do postaci normalnej Chomsky'ego. Żeby rozszerzyć ten zbiór do wszystkich gramatyk bezkontekstowych, rozszerza się czasem postać normalną Chomsky'ego o reguły:

S \rightarrow \epsilon (S – symbol startowy, \epsilon – słowo puste), ale gramatyka zawierająca taką regułkę nie może zawierać S po prawej stronie żadnej reguły.

Gramatyka taka to de facto alternatywa gramatyki w postaci normalnej oraz gramatyki generującej tylko symbol pusty.

Konstrukcja[edytuj | edytuj kod]

Zastąpienie symboli terminalnych symbolami nieterminalnymi[edytuj | edytuj kod]

Wszystkie symbole terminalne z alfabetu gramatyki zastępujemy symbolami nieterminalnymi, które nie są jeszcze elementami danej gramatyki. Następnie dodajemy produkcje posiadające te nowo wprowadzone symbole po lewej stronie, a po prawej stronie symbole terminalne, które zostały przez nie zastąpione.

Przykładowo, poniższa gramatyka bezkontekstowa:

S\rightarrow aAb | ab
A\rightarrow S | aaSc

poprzez zastosowanie odpowiednich zastąpień zostaje przetransformowana do formy:

S\rightarrow A_aAA_b | A_aA_b
A\rightarrow S | A_aA_aSA_c
A_a\rightarrow a
A_b\rightarrow b
A_c\rightarrow c

Eliminacja reguł łańcuchowych[edytuj | edytuj kod]

Reguły łańcuchowe mają postać A\rightarrow B, gdzie A i B to symbole nieterminalne. Do każdego symbolu A dodajemy produkcję A\rightarrow \alpha jeśli \alpha nie składa się tylko z jednego symbolu nieterminalnego oraz jeśli dana gramatyka zawiera produkcję postaci B\rightarrow \alpha. W przypadku powyższej gramatyki eliminacja reguł łańcuchowych dotyczy tylko jednej produkcji: A\rightarrow S. Po usunięciu tej produkcji gramatyka będzie miała postać:

S\rightarrow A_aAA_b | A_aA_b
A\rightarrow A_aAA_b | A_aA_b | A_aA_aSA_c
A_a\rightarrow a
A_b\rightarrow b
A_c\rightarrow c

Eliminacja reguł, w których po prawej stronie stoją więcej niż 2 symbole nieterminalne[edytuj | edytuj kod]

We wszystkich produkcjach tego typu, czyli o postaci A\rightarrow A_1A_2A_3A_4, wprowadzamy nowe symbole nieterminalne, które nie są elementami zbioru symboli nieterminalnych danej gramatyki, w poniższy sposób:

A\rightarrow A_1B_2
B_2\rightarrow A_2B_3
B_3\rightarrow A_3A_4

W powyższej przykładowej gramatyce eliminacji muszą podlec reguły

S\rightarrow A_aAA_b
A\rightarrow A_aAA_b | A_aA_aSA_c

W tym celu wprowadzamy nowe symbole nieterminalne B, C:

S\rightarrow A_aB
A\rightarrow A_aB | A_aC
B\rightarrow AA_b
C\rightarrow A_aSA_c

Po pierwszej turze eliminacji gramatyka zawiera jednak jedną produkcję, gdzie po prawej stronie występują więcej niż 2 symbole nieterminalne: C\rightarrow A_aSA_c. By ją znormalizować wprowadzamy kolejny symbol, D:

C\rightarrow A_aD
D\rightarrow SA_c

Po tym kroku gramatyka znajduje się w postaci normalnej Chomsky'ego:

S\rightarrow A_aB | A_aA_b
A\rightarrow A_aB | A_aC | A_aA_b
B\rightarrow AA_b
C\rightarrow A_aD
D\rightarrow SA_c
A_a\rightarrow a
A_b\rightarrow b
A_c\rightarrow c

Bibliografia[edytuj | edytuj kod]

  • Uwe Schöning: Theoretische Informatik - kurzgefasst. Spektrum Akademischer Verlag, 1994, s. 52-54. ISBN 3-8274-1099-1.

Zobacz też[edytuj | edytuj kod]