Saya akan memposting ini sebagai jawaban, tetapi tidak menjawab seluruh pertanyaan Anda: komplemen dari setiap CFL adalah R (rekursif), karena bahasa rekursif ditutup di bawah pelengkap dan semua CFL adalah R.
Eric
CFL tidak ditutup di bawah komplementasi tidak berarti bahwa 'L' berada di CFL berarti komplemennya tidak dalam CFL. Ini hanya berarti bahwa ada 'L' di CFL sehingga komplemennya tidak dalam CFL
SHREYANSHU THAKUR
@ Eric Penanya sudah tahu bahwa komplemen dari setiap CFL bersifat rekursif. Mereka telah membuat banyak pernyataan kuat bahwa komplemen dari setiap CFL adalah di P .
David Richerby
Jawaban:
17
Satu dapat memahami pertanyaan Anda dalam dua cara, sesuai dengan definisi "pelengkap CFL".
kasus A: Komplemen CFL adalah kelas dari semua bahasa yang tidak ada dalam CFL. Secara formal,
Dalam hal ini, jauh lebih besar dari , bahkan memiliki bahasa yang tidak ada dalam , dll. Tapi mungkin bukan itu yang Anda maksudkan.¯ C F L PR
CFL.¯¯¯¯¯¯¯¯¯¯¯= { L ∣ L ∉ CFL } .
CFL.¯¯¯¯¯¯¯¯¯¯¯PR
kasus B: Tentukan kelas komplemen-CFL sebagai
dengan kata-kata, himpunan semua bahasa , sehingga komplemen adalah bebas konteks .L L
c o CFL ={ L¯∣ L ∈ CFL } ,
L.L.
Dalam hal itu, apa yang Anda tulis masuk akal:
(oleh algoritma CYK ), dan juga (jalankan algoritma yang sama, jawaban yang berlawanan), dan karena , maka harus langsung bahwa , kan?c o C F L ⊆ P C F L ≠ c o C F L c o C F L ⊊ PCFL ⊊ Pc o CFL⊆PCFL≠coCFLcoCFL⊊P
definisi CFK sejauh yang saya mengerti: bahasa L dalam coCFK jika dan hanya jika pelengkap L adalah dalam CFK. Dengan komplemen LI berarti semua string yang mungkin kecuali string dalam L. Masalahnya saya pikir adalah komplemen tidak dapat didefinisikan sebagai "jalankan algoritma yang sama dan balikkan jawabannya" Sebagai contoh: L = (x ^ iy ^ iz ^ i) tidak CFL, tapi saya tidak tahu algoritma apa yang bisa saya jalankan untuk mendapatkan jawaban (negatif).
user432
1
jadi Anda mengacu pada kasus B. Perhatikan bahwa komplemen CFL mungkin tidak CFL, tetapi itu tidak berarti bahwa algoritma CYK tidak bekerja sama .. Maksud saya, kita menjalankan CYK pada , yang CFL, dan mendapatkan jawaban untuk setiap apakah atau tidak itu adalah di . kebalikan dari itu adalah jawaban untuk pertanyaan apakah itu dalam , meskipun mungkin non-CFL. LL¯¯¯¯xL¯¯¯¯xLL
Ran G.
1
@ user432 ! coCFL≠CFL¯¯¯¯¯¯¯¯¯¯
Raphael
1
@RanG adalah standar notasi Anda di sini? Saya berharap dan kelas bahasa sedemikian rupa sehingga . coCFL={L:L¯∈CFL}CFL¯¯¯¯¯¯¯¯¯¯¯=LL∉CFL
usul
1
Sebenarnya, izinkan saya mengubah notasi sesuai saran Anda, itu akan lebih masuk akal.
Ran G.
3
Kelas kuat yang berisi CFL dan coCFL adalah LOGCFL , yang berisi semua bahasa yang dapat direduksi logspace menjadi bahasa bebas konteks. Kelas ini antara NL dan AC1, dan memiliki beberapa masalah alami lengkap. Itu juga dapat didefinisikan dalam hal sirkuit AC1 terbatas. LOGCFL ditutup dengan komplemen (ini merupakan perpanjangan dari argumen yang digunakan untuk menunjukkan bahwa NL = coNL).
Komplemen CFL mungkin bisa CFL tetapi tidak harus demikian. Komplemen CFL bersifat rekursif (R) dan berulang secara berulang (RE). Mengapa? Semua CFL keduanya R dan RE. Bahasa R ditutup dengan komplemen (tetapi RE tidak). Dalam konteks itu, komplemen dari CFL adalah R yang secara inheren RE.
Penanya telah telah mengatakan bahwa mereka tahu bahwa komplemen dari setiap CFP adalah di P . Itu pernyataan yang jauh lebih kuat daripada itu bersifat rekursif atau RE. Sepertinya penanya telah menyebutkan seseorang yang tidak bisa berjalan dan Anda telah menjawab dengan bukti bahwa ia tidak bisa berlari dengan kecepatan suara.
Jawaban:
Satu dapat memahami pertanyaan Anda dalam dua cara, sesuai dengan definisi "pelengkap CFL".
kasus A: Komplemen CFL adalah kelas dari semua bahasa yang tidak ada dalam CFL. Secara formal, Dalam hal ini, jauh lebih besar dari , bahkan memiliki bahasa yang tidak ada dalam , dll. Tapi mungkin bukan itu yang Anda maksudkan.¯ C F L PR
kasus B: Tentukan kelas komplemen-CFL sebagai dengan kata-kata, himpunan semua bahasa , sehingga komplemen adalah bebas konteks .L L
Dalam hal itu, apa yang Anda tulis masuk akal: (oleh algoritma CYK ), dan juga (jalankan algoritma yang sama, jawaban yang berlawanan), dan karena , maka harus langsung bahwa , kan?c o C F L ⊆ P C F L ≠ c o C F L c o C F L ⊊ PCFL ⊊ P c o CFL⊆P CFL≠coCFL coCFL⊊P
sumber
Kelas kuat yang berisi CFL dan coCFL adalah LOGCFL , yang berisi semua bahasa yang dapat direduksi logspace menjadi bahasa bebas konteks. Kelas ini antara NL dan AC1, dan memiliki beberapa masalah alami lengkap. Itu juga dapat didefinisikan dalam hal sirkuit AC1 terbatas. LOGCFL ditutup dengan komplemen (ini merupakan perpanjangan dari argumen yang digunakan untuk menunjukkan bahwa NL = coNL).
sumber
Komplemen CFL mungkin bisa CFL tetapi tidak harus demikian. Komplemen CFL bersifat rekursif (R) dan berulang secara berulang (RE). Mengapa? Semua CFL keduanya R dan RE. Bahasa R ditutup dengan komplemen (tetapi RE tidak). Dalam konteks itu, komplemen dari CFL adalah R yang secara inheren RE.
sumber