Postać normalna Chomskiego

Postać normalna Chomskiego 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 ChomskiegoSzablon:Odn.

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

$S\to ϵ$ ($S$ – symbol startowy, $ϵ$ – 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}A{A}_b|A_a{A}_b$

$A\to S|A_a{A}_{a}S{A}_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}A{A}_b|A_a{A}_b$

$A\to A_{a}A{A}_b|A_a{A}_b|A_a{A}_{a}S{A}_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}A{A}_b$

$A\to A_{a}A{A}_b|A_a{A}_{a}S{A}_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 A{A}_b$

$C\to A_{a}S{A}_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}S{A}_c.$ By ją znormalizować, wprowadzamy kolejny symbol, $D:$

$C\to A_{a}D$

$D\to S{A}_c$

Po tym kroku gramatyka znajduje się w postaci normalnej Chomskiego:

$S\to A_{a}B|A_a{A}_b$

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

$B\to A{A}_b$

$C\to A_{a}D$

$D\to S{A}_c$

$A_a\to a$

$A_b\to b$

$A_c\to c$

Zobacz też

• algorytm CYK
• postać normalna Greibach

Bibliografia

• Szablon:Cytuj książkę
• Szablon:Cytuj książkę