Znaczenie normalnych form, takich jak normalna forma Chomsky'ego dla CFG

12

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.

— użytkownik5507
źródło

2

Normalne formy są przydatne przy podawaniu konstruktywnych dowodów.

— Karolis Juodelė

12

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 . $\varepsilon$ $\varepsilon$
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.

— Raphael
źródło

5

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 . $I$ $n$ $A$ $n$ $n$

$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ć. $A[1,n]$ $S$ $S$

def decide (string s,grammar G):
    //base case
    for i=1 to n:
        N[i,i]=I[i]    //as the substring of length one can be generated by only a
                       terminal.
    //end base case

    //induction
    for s=1 to n:       //length of substring
        for i=1 to n-s-1: //start index of substring
            for j=i to i+s-1:   //something else
                 if there exists a rule A->BC such that B belongs to N[i,j] and C
                 belongs to N[j+1,i+s-1] then add A to N[i,i+s-1]
    //endInduction

    if S belongs to N[1,n] then accept else reject.

Wiem, że indeksy wydają się dość szalone. Ale w zasadzie oto, co się dzieje.

Myślę, że podstawowy przypadek jest całkiem jasny.

W kroku indukcyjnym budujemy rozwiązanie dla podciągu o długości ze wszystkich rozwiązań o długości mniejszej niż .

s

$s$

s

$s$

Powiedzmy, że znajdujesz rozwiązanie dla podłańcucha o długości zaczynając od indeksu . Następnie należy uruchomić pętlę (coś innego ..... część), która sprawdza, czy nie jest to regułą ( ) takie, że i wywodzą się dwie sąsiadujące i rozłączne podciągi sub a jeśli tak dodać wszystkie takie „s do .

5

$5$ sub

1

$1$

A - > B C

$A->BC$

B

$B$

C

$C$

A

$A$

N [1, 6]

$N[1,6]$

Wreszcie, jeśli masz symbol początkowy w to akceptujesz!

N [1, n]

$N[1,n]$

— ishan3243
źródło

3

Jest to algorytm CYK, który a) powinieneś nazwać jako taki i b) został wymieniony w mojej odpowiedzi. Zauważ, że wielomianowe środowisko wykonawcze robi wrażenie, ponieważ algorytm jest jednolity we wszystkich CFG, czyli ogólnie.

— Raphael

@ Rafael ok .... nie znałem nazwy :)

— ishan3243

4

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). $\epsilon$

— Dominik D. Freydenberger
źródło