Bangun PDA untuk komplemen dari

Saya bertanya-tanya apakah ini bahkan mungkin, karena $\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL}$ . Oleh karena itu PDA yang dapat membedakan kata $w\in\{a^n b^n c^n \mid n \geq 0\}$ dari sisa $\{a^*b^*c^*\}$ mungkin juga menerimanya, yang kedengarannya bertentangan dengan saya.

Saya kira saya perlu mengambil keuntungan dari sifat PDA yang tidak deterministik tetapi saya kehabisan ide. Jika Anda bisa memberikan saran, saya akan sangat menghargainya.

formal-languages automata context-free pushdown-automata hauptbenutzer
sumber

Poin menarik tentang itu sepertinya kontradiktif. Memang, bahasa bebas konteks tidak ditutup dengan mengambil pelengkap ... jadi ada banyak contoh bahasa bebas konteks yang bisa "diterima" dalam arti yang Anda singgung. Saya bukan ahli teori dan, dengan demikian, tidak bisa benar-benar mendamaikan ini, tapi mungkin orang lain bisa berpura-pura mengapa ini bukan sesuatu yang perlu dikhawatirkan?

Patrick87

Perhatikan bahwa ini menggeneralisasi: komplemen

adalah CFG.

{a^{n} b^{n} c^{n} d^{n} e^{n}}

$\{a^n b^n c^n d^n e^n\}$

sdcvvc

Pertanyaan serupa .

Raphael

Jawaban:

Tidak, ini bebas konteks. Untuk menerima , Anda harus memastikan bahwa tiga angka sama. Untuk menerima , Anda hanya perlu memastikan bahwa Anda berada di salah satu dari tiga kasus berikut: $a^nb^nc^n$ $a^*b^*c^* \setminus a^nb^nc^n$

Jumlah berbeda dari jumlah s; atau $a$ $b$
Jumlah berbeda dari jumlah ; atau $a$ $c$
Jumlah s berbeda dari jumlah s. $b$ $c$

Tulis PDA untuk masing-masing kasus ini, kemudian gabungkan dengan melompat nondeterministis ke masing-masing dari keadaan awal.

Patrick87
sumber

Saya telah menuliskan kasus-kasus ini dengan baik, tetapi saya kehilangan ide untuk menghubungkannya. Terima kasih!

hauptbenutzer

Sebenarnya Anda hanya membutuhkan dua kasing saja.

sdcvvc

@ sdcvvc Poin bagus. :)

Patrick87

Untuk jumlah karakter yang berbeda, anggap ini sebagai inspirasi:

. Seharusnya mudah untuk merekatkan

ke kiri ini atau

ke kanan dan mengubahnya menjadi PDA. Untuk kasus rumit (yang tidak Anda butuhkan)

S \to x S y | X | Y; X \to x | x X; Y \to y | y Y

$S → xSy | X | Y ; X → x | xX ; Y → y | yY$

a^{+}

$a^+$

c^{+}

$c^+$

S \to a S c | A | C; A \to a B | a A; C \to B c | C c; B \to ε | b B

Jonas Kölker