Rozumiem, że gramatyki bezkontekstowe mogą być używane do reprezentowania języków bezkontekstowych. Mogą być niejasne. Mamy również normalne formy, takie jak normalna postać Chomsky'ego i Greibacha . Nie mogłem zrozumieć takiej potrzeby.
Dlaczego są ważne w teorii języków? Wszystkie podręczniki, o których mówiłem, mówią o tych normalnych formach, ale nie mówią nic o ich znaczeniu.
formal-languages
context-free
formal-grammars
normal-forms
użytkownik5507
źródło
źródło
Odpowiedzi:
Istnieją co najmniej dwa odpowiednie zastosowania.
Prostota dowodów
Istnieje wiele dowodów dotyczących gramatyk bezkontekstowych, w tym możliwość redukcji i równoważności automatów. Są one tym prostsze, im bardziej ograniczony jest zestaw gramatyk, z którymi masz do czynienia. Dlatego normalne formy mogą być tam pomocne.
Jako konkretny przykład, normalna postać Greibacha jest używana do pokazania (konstruktywnie), że dla każdego CFL (bez zawartości ) istnieje PDP- -wolne od przejścia .εε ε
Umożliwia parsowanie
Podczas gdy PDA mogą być używane do parsowania słów z dowolną gramatyką, jest to często niewygodne. Normalne formularze mogą dać nam więcej struktury do pracy, co skutkuje łatwiejszymi algorytmami parsowania.
Jako konkretny przykład algorytm CYK wykorzystuje normalną postać Chomsky'ego. Natomiast normalna forma Greibacha umożliwia parsowanie rekurencyjno-opadające; chociaż może być konieczne cofanie, złożoność przestrzeni jest liniowa.
źródło
Normalna postać Chomsky'ego pozwala algorytmowi wielomianowemu decydować, czy gramatyka może wygenerować ciąg. Algorytm jest dość zręczny, jeśli znasz programowanie dynamiczne ...
Jeśli długość twojego wejścia ( ) wynosi to bierzesz tablicę 2d ( ) o wartości dim x .n A n nI n A n n
G I ( i , j )A[i,j] oznacza wszystkie symbole w gramatyce które mogą wyprowadzić podłańcuch .G I(i,j)
Tak więc na koniec, jeśli zawiera symbol początkowy ( ), oznacza to, że ciąg I można uzyskać przez co chcieliśmy sprawdzić.S S.A[1,n] S S
Wiem, że indeksy wydają się dość szalone. Ale w zasadzie oto, co się dzieje.
sub
źródło
Sheila Greibach wynalazła normalną formę Greibacha, aby udowodnić, że każdy CFG może być rozpoznany przez PDA, który działa w czasie rzeczywistym (tj. Bez -transitions).ϵ
źródło