Postać normalna Chomsky’ego


Postać normalna Chomsky’ego w encyklopedii

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:

A a {\displaystyle A\to a} A B C {\displaystyle A\to 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 ϵ {\displaystyle S\to \epsilon } ( S {\displaystyle S} – symbol startowy, ϵ {\displaystyle \epsilon } – słowo puste), ale gramatyka zawierająca taką regułkę nie może zawierać S {\displaystyle S} po prawej stronie żadnej reguły.

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

Spis treści

Konstrukcja | edytuj kod

Zastąpienie symboli terminalnych symbolami nieterminalnymi | 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 a A b | a b {\displaystyle S\to aAb|ab} A S | a a S c {\displaystyle A\to S|aaSc}

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

S A a A A b | A a A b {\displaystyle S\to A_{a}AA_{b}|A_{a}A_{b}} A S | A a A a S A c {\displaystyle A\to S|A_{a}A_{a}SA_{c}} A a a {\displaystyle A_{a}\to a} A b b {\displaystyle A_{b}\to b} A c c {\displaystyle A_{c}\to c}

Eliminacja reguł łańcuchowych | edytuj kod

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

S A a A A b | A a A b {\displaystyle S\to A_{a}AA_{b}|A_{a}A_{b}} A A a A A b | A a A b | A a A a S A c {\displaystyle A\to A_{a}AA_{b}|A_{a}A_{b}|A_{a}A_{a}SA_{c}} A a a {\displaystyle A_{a}\to a} A b b {\displaystyle A_{b}\to b} A c c {\displaystyle A_{c}\to c}

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

We wszystkich produkcjach tego typu, czyli o postaci A A 1 A 2 A 3 A 4 , {\displaystyle A\to A_{1}A_{2}A_{3}A_{4},} wprowadzamy nowe symbole nieterminalne, które nie są elementami zbioru symboli nieterminalnych danej gramatyki, w poniższy sposób:

A A 1 B 2 {\displaystyle A\to A_{1}B_{2}} B 2 A 2 B 3 {\displaystyle B_{2}\to A_{2}B_{3}} B 3 A 3 A 4 {\displaystyle B_{3}\to A_{3}A_{4}}

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

S A a A A b {\displaystyle S\to A_{a}AA_{b}} A A a A A b | A a A a S A c {\displaystyle A\to A_{a}AA_{b}|A_{a}A_{a}SA_{c}}

W tym celu wprowadzamy nowe symbole nieterminalne B , C : {\displaystyle B,C{:}}

S A a B {\displaystyle S\to A_{a}B} A A a B | A a C {\displaystyle A\to A_{a}B|A_{a}C} B A A b {\displaystyle B\to AA_{b}} C A a S A c {\displaystyle C\to A_{a}SA_{c}}

Po pierwszej turze eliminacji gramatyka zawiera jednak jedną produkcję, gdzie po prawej stronie występują więcej niż 2 symbole nieterminalne: C A a S A c . {\displaystyle C\to A_{a}SA_{c}.} By ją znormalizować, wprowadzamy kolejny symbol, D : {\displaystyle D{:}}

C A a D {\displaystyle C\to A_{a}D} D S A c {\displaystyle D\to SA_{c}}

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

S A a B | A a A b {\displaystyle S\to A_{a}B|A_{a}A_{b}} A A a B | A a C | A a A b {\displaystyle A\to A_{a}B|A_{a}C|A_{a}A_{b}} B A A b {\displaystyle B\to AA_{b}} C A a D {\displaystyle C\to A_{a}D} D S A c {\displaystyle D\to SA_{c}} A a a {\displaystyle A_{a}\to a} A b b {\displaystyle A_{b}\to b} A c c {\displaystyle A_{c}\to c}

Zobacz też | edytuj kod

Bibliografia | edytuj kod

  • Uwe Schöning: Theoretische Informatik – kurzgefasst. Spektrum Akademischer Verlag, 1994, s. 52–54. ISBN 3-8274-1099-1.
Na podstawie artykułu: "Postać normalna Chomsky’ego" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy