Bagaimana membuktikan bahwa suatu bahasa bebas konteks?

26

Ada banyak teknik untuk membuktikan bahwa bahasa adalah tidak bebas konteks, tapi bagaimana saya membuktikan bahwa bahasa adalah bebas konteks?

Teknik apa yang ada untuk membuktikan ini? Jelas, salah satu caranya adalah dengan menunjukkan tata bahasa bebas konteks untuk bahasa tersebut. Apakah ada teknik sistematis untuk menemukan tata bahasa bebas konteks untuk bahasa tertentu?

Untuk bahasa biasa, ada yang cara yang sistematis untuk memperoleh biasa robot tata bahasa / terbatas-negara: misalnya, Myhill-Nerode teorema menyediakan salah satu cara. Apakah ada teknik yang sesuai untuk bahasa bebas konteks?


Motivasi saya di sini adalah (mudah-mudahan) membangun pertanyaan referensi yang berisi daftar teknik yang sering membantu, ketika mencoba membuktikan bahwa bahasa yang diberikan bebas konteks. Karena kita memiliki banyak pertanyaan di sini yang merupakan kasus khusus ini, akan lebih baik jika kita dapat mendokumentasikan pendekatan umum atau teknik umum yang dapat digunakan ketika menghadapi masalah semacam ini.

DW
sumber
Izinkan saya untuk meninggalkan catatan saya yang biasa: ketika memberikan tata bahasa bebas konteks untuk bahasa yang ada, Anda membutuhkan bukti kebenaran yang dapat membuat pendekatannya agak sulit.
Raphael
Demi menjadikan ini sebagai pertanyaan referensi yang tepat yang dapat kami berikan pada penimbun masalah, dapatkah Anda menambahkan jawaban tentang membuat tata bahasa dan automata, mungkin dengan masing-masing contoh? Terima kasih!
Raphael
Sampai bahan dipindahkan di sini, perhatikan bahwa Rick Decker dan babou mengumpulkan beberapa idiom bebas konteks pada pertanyaan duplikat .
Raphael

Jawaban:

13

Pendekatan praktis yang dalam banyak contoh berhasil [tetapi tidak selalu, saya tahu] sedang mencoba menemukan struktur bersarang dari string dalam bahasa. "Ketergantungan bersarang" harus dihasilkan pada waktu yang sama di berbagai bagian string.

Kami juga memiliki kotak alat dasar :

  1. rangkaian: jika Anda dapat membagi bahasa menjadi dua bagian berturut-turut, gunakan produksi iniSS1S2

  2. union: dibagi menjadi beberapa bagian yang terpisahSS1S2

  3. iterasi:SS1Sε

Contoh 1

Berikut contoh untuk bersarang (terima kasih Raphael).

L={bkal(bc)manbok,l,m,n,oN,ko,2l=n,m2}

Ganti dengan . Kami sekarang dapat drop dalam kondisi.2 l nn2ln

Ganti dengan (bingung? adalah 'oh' bukan 'nol'). Terapkan alat untuk serikat pekerja. Kami bekerja dengan sini. Juga iff dan mana adalah variabel baru. Ganti dengan .k > o  atau  k < o o k > o k > o k = s + o s > 0 s k s + okok>o or k<ook>ok>ok=s+os>0sks+o

L1={bs+oal(bc)ma2lbol,m,o,sN,s>0,m2}

Beberapa penulisan ulang sederhana.

L1={bbsboalbcbc(bc)m(aa)lbol,m,o,sN}

Sekarang kita melihat struktur bersarang, dan mulai membangun tata bahasa.

T b U U b U εS1TV , , (lihat: rangkaian dan iterasi di sini)TbUUbUε

o bVbVbW (kita menghasilkan 's di kedua sisi)o b

WaWaaX

Y b c b c Z b c Z εXYZ , ,YbcbcZbcZε

Contoh 2

K={akblcml=m+k}

Penulisan ulang "jelas" pertama.

K={akbm+kcmm,k0}={akbmbkcmm,k0}

Dalam linguistice ini disebut "dependensi lintas-seri": interleaving (biasanya) sangat menunjukkan sifat tidak kontekstual. Tentu saja dan kita diselamatkan.m + k = k + mk,m,k,mm+k=k+m

K={akbk+mcmm,k0}={akbkbmcmm,k0}

dengan produksi , ,X a X b ε Y b Y c εSXYXaXbεYbYcε

Demikian pulaK={akblcmm=k+l}={akblclckk,l0}

dengan produksi ,X b X c εSaScXXbXcε


Komentar akhir: teknik-teknik ini membantu Anda menghasilkan tata bahasa kandidat bebas konteks yang diharapkan akan mengenali bahasa Anda. Bukti kebenaran mungkin masih diperlukan, untuk memastikan bahwa tata bahasa benar-benar berfungsi untuk mengenali bahasa Anda (tidak lebih, dan tidak kurang).

Hendrik Jan
sumber
11

Ada satu karakterisasi CFL yang dapat digunakan, teorema Chomsky-Schützenberger .

Bahasa Dyck

Biarkan alfabet. Kami mendefinisikan Dyck -language dari dengan bebas konteks tata bahasa dengan diberikan olehTDT(TT^)TG=({S},TT^,δ,S)δ

SaSa^Sε,aT .

Teorema Chomsky-Schützenberger

LΣ bebas konteks jika dan hanya jika ada

  • alfabet ,T
  • bahasa reguler danR(TT^)
  • homomorfismeψ:(TT^)Σ

maka

L=ψ(DTR) .

Perhatikan bahwa homomorfisme diperluas ke kata-kata (simbol demi simbol) dan kemudian ke bahasa (kata demi kata).

Contoh

Pertimbangkan . DenganL={anbncmn,mN

  • T={[,} (dan, secara kanonik, ),T^={],}
  • R=L([]) dan
  • ψ(x)={a,x=[b,x= ]ε,x=c,x= 

teorema ini menyiratkan bahwa bebas dari konteks, khususnya sejak ituL

DTR={[n]nmmn,mN} .

Contoh 2

Tunjukkan bahwa bebas konteks.L={bkal(bc)manbok,l,m,n,oN,ko,2l=n,m2}

Di sini, kita membutuhkan satu jenis kurung untuk , satu untuk , satu untuk , dan yang lainnya digunakan untuk memodelkan yang menyebabkan . Kita gunakanabcbbko

  • T={[,,,<} ,
  • R=L(<+>+[++])L([++]<+>+) dan
  • ψ(x)={b,x{,,<}a,x=[aa,x= ]bc,x=ε,else

dan menerapkan teorema. Untuk melihat bahwa , kita tidak perlu lebih dari fakta bahwa simbol yang cocok (mis. Dan ) harus sering terjadi secara sama di . Menambahkan contraint ini ke ekspresi reguler yang kita tentukan dengan , kita dapatkanL=ψ(DTR)[]wDTR

DTR={<p>po[lmm]lop1,o0,l0,m2} {}

dan karenanya

ψ(DTR)={bp+oal(bc)ma2lbop1,o0,l0,m2} {}={bkal(bc)manbok,l,m,n,oN,k>o,2l=n,m2} {}=L.

Untuk tata bahasa dan automata

Jika kita ingin memiliki otomat atau tata bahasa pada akhirnya, kita memiliki beberapa pekerjaan di depan kita.

  • Menuju robot, membangun NPDA untuk dan NFA untuk . Yang pertama adalah standar dan kami memiliki algoritma untuk yang terakhir, asalkan bahasa diberikan dalam representasi yang sesuai (lihat juga di sini ). Persimpangan keduanya adalah konstruksi standar lain dan dapat diterapkan untuk setiap transisi secara individual. R ψDTRψ

  • Menuju tata bahasa, bangun satu untuk (sekali lagi, harus standar), ambil satu untuk dan memotongnya . Kemudian terapkan pada set aturan (simbol untuk simbol).D T ψRDTψ

Bisa dibilang, ini mudah karena algoritmik; kompleksitasnya terletak pada menemukan , , dan . Saya tidak tahu apakah pendekatan ini (sering) lebih sederhana daripada membangun PDA / tata bahasa secara langsung tetapi mungkin memungkinkan untuk fokus pada fitur-fitur penting dari bahasa yang ada. Coba sendiri!R ψTRψ

Raphael
sumber
Tidak dapat dipastikan apakah bahasa yang diberikan bebas konteks.
reinierpost