Pentingnya bentuk normal seperti bentuk normal Chomsky untuk CFG

12

Saya mengerti bahwa tata bahasa bebas konteks dapat digunakan untuk mewakili bahasa bebas konteks. Mungkin ada ambiguitas. Kami juga memiliki bentuk normal seperti bentuk normal Chomsky dan Greibach . Saya tidak bisa mengerti kebutuhan itu.

Mengapa mereka penting dalam teori bahasa? Semua buku teks yang saya maksudkan menceritakan tentang bentuk-bentuk normal ini tetapi tidak memberi tahu apa-apa tentang pentingnya.

formal-languages context-free formal-grammars normal-forms pengguna5507
sumber

2

Bentuk normal berguna ketika memberikan bukti konstruktif.

Karolis Juodelė

12

Setidaknya ada dua kegunaan yang relevan.

Kesederhanaan bukti
Ada banyak bukti di sekitar tata bahasa bebas konteks, termasuk reducability dan kesetaraan dengan automata. Itu adalah semakin sederhana semakin terbatas tata bahasa yang harus Anda tangani. Karena itu, bentuk normal dapat membantu di sana.

Sebagai contoh konkret, bentuk normal Greibach digunakan untuk menunjukkan (secara konstruktif) bahwa ada PDA -transisi-bebas untuk setiap CFL (yang tidak mengandung ). $\varepsilon$ $\varepsilon$
Mengaktifkan penguraian
Meskipun PDA dapat digunakan untuk mengurai kata-kata dengan tata bahasa apa pun, ini sering kali tidak nyaman. Bentuk normal dapat memberi kita lebih banyak struktur untuk bekerja, menghasilkan algoritma penguraian yang lebih mudah.

Sebagai contoh nyata, algoritma CYK menggunakan bentuk normal Chomsky. Bentuk normal Greibach, di sisi lain, memungkinkan penguraian rekursif-keturunan; meskipun mungkin diperlukan backtracking, kompleksitas ruang adalah linier.

Raphael
sumber

5

Bentuk normal Chomsky memungkinkan algoritma waktu polinomial untuk memutuskan apakah suatu string dapat dihasilkan oleh tata bahasa. Algoritma ini cukup apik jika Anda tahu pemrograman dinamis ...

Jika panjang input Anda ( ) adalah maka Anda mengambil array 2d ( ) dari redup x . $I$ $n$ $A$ $n$ $n$

$A[i,j]$ menunjukkan semua simbol dalam tata bahasa yang dapat menurunkan sub-string . $G$ $I(i,j)$

Jadi akhirnya jika berisi simbol awal ( ) maka itu berarti string saya dapat diturunkan oleh yang ingin kami periksa. $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.

Saya tahu bahwa indeksnya terlihat cukup gila. Tapi pada dasarnya inilah yang terjadi.

Kasus dasarnya cukup jelas.

Pada langkah induktif kita membangun solusi untuk panjang substring dari semua solusi dengan panjang kurang dari .

s

$s$

s

$s$

Katakanlah, Anda menemukan solusi untuk panjang substring ( ) mulai dari indeks . Kemudian Anda memulai loop (bagian lain) ..... yang memeriksa apakah ada aturan ( ) sehingga dan mendapatkan dua substring yang berdekatan dan terpisah dari sub dan jika demikian tambahkan semua seperti itu ke .

5

$5$ sub

1

$1$

A - > B C

$A->BC$

B

$B$

C

$C$

A

$A$

N [1, 6]

$N[1,6]$

Akhirnya, jika Anda memiliki simbol awal dalam maka Anda menerima!

N [1, n]

$N[1,n]$

ishan3243
sumber

3

Ini adalah algoritma CYK yang a) harus Anda beri nama dan b) telah disebutkan dalam jawaban saya. Perhatikan bahwa runtime polinom hanya mengesankan karena algoritmanya seragam untuk semua CFG, yaitu umum.

Raphael

@Raphael ok .... saya tidak tahu namanya :)

ishan3243

4

Sheila Greibach menemukan bentuk normal Greibach untuk membuktikan bahwa setiap CFG dapat dikenali oleh PDA yang bekerja secara real time (yaitu, tanpa transisi ). $\epsilon$

Dominik D. Freydenberger
sumber

Pentingnya bentuk normal seperti bentuk normal Chomsky untuk CFG

Jawaban: