postać normalna Greibacha

W teorii języka formalnego gramatyka bezkontekstowa jest w postaci normalnej Greibacha (GNF), jeśli prawe strony wszystkich reguł produkcji zaczynają się od symbolu końcowego , po którym opcjonalnie następują pewne zmienne. Nieścisła forma dopuszcza jeden wyjątek od tego ograniczenia formatu, aby puste słowo (epsilon, ε) było członkiem opisywanego języka. Forma normalna została ustanowiona przez Sheilę Greibach i nosi jej imię.

Mówiąc dokładniej, gramatyka bezkontekstowa jest w postaci normalnej Greibacha, jeśli wszystkie reguły produkcji mają postać:

{\ Displaystyle A \ do aA_ {1} A_ {2} \ cdots A_ {n}}

gdzie $,$ symbolem nieterminalnym jest symbolem terminalnym, $Displaystyle A_ {1} A_ {2}$ ${n}} ($ A_ $prawdopodobnie pusta$ sekwencja symboli nieterminalnych niezawierająca symbolu startu i jest symbolem startu.

Zauważ, że gramatyka nie ma lewych rekurencji .

Każdą gramatykę bezkontekstową można przekształcić w równoważną gramatykę w normalnej postaci Greibacha. Istnieją różne konstrukcje. Niektóre nie dopuszczają drugiej formy reguły i nie mogą przekształcać gramatyk bezkontekstowych, które mogą generować puste słowo. Dla jednej takiej konstrukcji rozmiar konstruowanej gramatyki wynosi O( n ⁴ ) w ogólnym przypadku i O( n ³ ), jeśli żadna pochodna oryginalnej gramatyki nie składa się z pojedynczego nieterminalnego symbolu, gdzie n jest rozmiarem oryginalnej gramatyki. Konwersji tej można użyć do udowodnienia, że każdy język bezkontekstowy automat czasu rzeczywistego (niedeterministyczny) przesuwający w dół , tzn. automat odczytuje literę ze swojego wejścia w każdym kroku.

Biorąc pod uwagę gramatykę w GNF i dający się wyprowadzić łańcuch w gramatyce o długości n , każdy parser odgórny zatrzyma się na głębokości n .

Zobacz też

^ Greibach, Sheila (styczeń 1965). „Nowe twierdzenie o postaci normalnej dla gramatyk struktur fraz bezkontekstowych”. Dziennik ACM . 12 (1): 42–52. doi : 10.1145/321250.321254 . S2CID 12991430 .
Bibliografia _ Kocha, Robert (1999). „Powrót do transformacji postaci normalnej Greibacha” . Informacja i obliczenia . 150 (1): 112–118. CiteSeerX 10.1.1.47.460 . doi : 10.1006/inco.1998.2772 .

Aleksander Meduna (6 grudnia 2012). Automaty i języki: teoria i zastosowania . Springer Science & Business Media. ISBN 978-1-4471-0501-5 .
György E. Révész (17 marca 2015). Wprowadzenie do języków formalnych . Firma kurierska. ISBN 978-0-486-16937-8 .

[1] Greibach, Sheila (styczeń 1965). „Nowe twierdzenie o postaci normalnej dla gramatyk struktur fraz bezkontekstowych”. Dziennik ACM . 12 (1): 42–52. doi : 10.1145/321250.321254 . S2CID 12991430 .

[2] Bibliografia _ Kocha, Robert (1999). „Powrót do transformacji postaci normalnej Greibacha” . Informacja i obliczenia . 150 (1): 112–118. CiteSeerX 10.1.1.47.460 . doi : 10.1006/inco.1998.2772 .