Postać normalna Chomsky'ego

Gramatyka formalna jest w postaci normalnej Chomsky'ego , jeśli wszystkie jej reguły produkcji mają jedną z następujących postaci:

$A$$\rightarrow \,$${\ Displaystyle BC}$zarówno

$A$$\rightarrow \,$α

gdzie , i są symbolami niekońcowymi (lub zmiennymi), a α jest symbolem końcowym. $A$$B.$$C$

Każdy język bezkontekstowy , który nie ma pustego ciągu, można wyrazić za pomocą gramatyki postaci normalnej Chomsky'ego (GFNCH) i na odwrót. Co więcej, biorąc pod uwagę gramatykę bezkontekstową , możliwe jest algorytmiczne utworzenie równoważnego GFNCH, czyli takiego, który generuje ten sam język.

Alternatywna definicja

W niektórych tekstach można znaleźć definicję GFNCH taką, że każdy GFNCH tworzy dowolny język bezkontekstowy i podobnie, że dla dowolnego języka bezkontekstowego istnieje GFNCH, który go definiuje. Definicja ta prawie nie różni się dopuszczaniem reguły ε o następującej postaci:

$A$$\rightarrow \,$${\ Displaystyle BC}$zarówno

$A$$\rightarrow \,$α lub

$tak$$\rightarrow \,$ε

gdzie jest wyróżnionym (lub początkowym) symbolem gramatyki, jest symbolem niekońcowym (lub zmiennym), a także są niekońcowymi, ale odrębnymi symbolami , α ​​jest symbolem końcowym, a ε jest pustym (lub pustym) łańcuchem. $tak$$A$$B.$$C$$tak$

Zobacz także

• Gramatyka (automat)
• Postać normalna Greibacha