Postać normalna Chomsky’ego

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

$A\to a$

$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\to \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

Zastąpienie symboli terminalnych symbolami nieterminalnymi

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\to aAb|ab$

$A\to S|aaSc$

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

$S\to A_{a}AA_{b}|A_{a}A_{b}$

$A\to S|A_{a}A_{a}SA_{c}$

$A_{a}\to a$

$A_{b}\to b$

$A_{c}\to c$

Eliminacja reguł łańcuchowych

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

$S\to A_{a}AA_{b}|A_{a}A_{b}$

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

$A_{a}\to a$

$A_{b}\to b$

$A_{c}\to c$

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

We wszystkich produkcjach tego typu, czyli o postaci $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\to A_{1}B_{2}$

$B_{2}\to A_{2}B_{3}$

$B_{3}\to A_{3}A_{4}$

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

$S\to A_{a}AA_{b}$

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

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

$S\to A_{a}B$

$A\to A_{a}B|A_{a}C$

$B\to AA_{b}$

$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\to A_{a}SA_{c}.$ By ją znormalizować, wprowadzamy kolejny symbol, $D{:}$

$C\to A_{a}D$

$D\to SA_{c}$

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

$S\to A_{a}B|A_{a}A_{b}$

$A\to A_{a}B|A_{a}C|A_{a}A_{b}$

$B\to AA_{b}$

$C\to A_{a}D$

$D\to SA_{c}$

$A_{a}\to a$

$A_{b}\to b$

$A_{c}\to c$

Zobacz też

• algorytm CYK
• postać normalna Greibach

Bibliografia

• 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.