Postać normalna Chomsky’ego

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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

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[1].

Żeby rozszerzyć ten zbiór do wszystkich gramatyk bezkontekstowych, rozszerza się czasem postać normalną Chomsky’ego o reguły:

( – symbol startowy, – słowo puste), ale gramatyka zawierająca taką regułkę nie może zawierać 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:

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

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

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

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 wprowadzamy nowe symbole nieterminalne, które nie są elementami zbioru symboli nieterminalnych danej gramatyki, w poniższy sposób:

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

W tym celu wprowadzamy nowe symbole nieterminalne

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

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

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  • Uwe Schöning: Theoretische Informatik – kurzgefasst. Spektrum Akademischer Verlag, 1994, s. 52–54. ISBN 3-8274-1099-1.
  • Martin D. Davis, Ron Sigal, Elaine J. Weyuker: Computability, Complexity, and Languages. Morgan Kaufmann Publishers, 1994. ISBN 1-4933-0034-2.