Postać normalna Chomsky’ego

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

${\displaystyle A\to a}$

${\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^[1].

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

${\displaystyle S\to \epsilon }$ (${\displaystyle S}$ – symbol startowy, ${\displaystyle \epsilon }$ – słowo puste), ale gramatyka zawierająca taką regułkę nie może zawierać ${\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.

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:

${\displaystyle S\to aAb|ab}$

${\displaystyle A\to S|aaSc}$

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

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

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

${\displaystyle A_{a}\to a}$

${\displaystyle A_{b}\to b}$

${\displaystyle A_{c}\to c}$

Eliminacja reguł łańcuchowych

Reguły łańcuchowe mają postać ${\displaystyle A\to B,}$ gdzie ${\displaystyle A}$ i ${\displaystyle B}$ to symbole nieterminalne. Do każdego symbolu ${\displaystyle A}$ dodajemy produkcję ${\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 ${\displaystyle B\to \alpha .}$ W przypadku powyższej gramatyki eliminacja reguł łańcuchowych dotyczy tylko jednej produkcji: ${\displaystyle A\to S.}$ Po usunięciu tej produkcji gramatyka będzie miała postać:

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

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

${\displaystyle A_{a}\to a}$

${\displaystyle A_{b}\to b}$

${\displaystyle 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 ${\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:

${\displaystyle A\to A_{1}B_{2}}$

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

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

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

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

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

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

${\displaystyle S\to A_{a}B}$

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

${\displaystyle B\to AA_{b}}$

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

${\displaystyle C\to A_{a}D}$

${\displaystyle D\to SA_{c}}$

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

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

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

${\displaystyle B\to AA_{b}}$

${\displaystyle C\to A_{a}D}$

${\displaystyle D\to SA_{c}}$

${\displaystyle A_{a}\to a}$

${\displaystyle A_{b}\to b}$

${\displaystyle A_{c}\to c}$

Zobacz też

• algorytm CYK
• postać normalna Greibach

Przypisy

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.