Bagaimana saya menunjukkan bahwa apakah PDA menerima string

8

Bagaimana saya menunjukkan bahwa masalah dalam memutuskan apakah PDA menerima beberapa string dari formulir $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ tidak dapat diputuskan?

Saya telah mencoba untuk mengurangi masalah ini ke masalah lain yang tidak dapat diputuskan seperti apakah dua tata bahasa bebas konteks menerima bahasa yang sama. Namun, saya tidak yakin bagaimana menggunakannya sebagai subrutin.

formal-languages automata context-free undecidability pushdown-automata David Faux
sumber

12

Inilah pendekatan saya: Saya akan menunjukkan bahwa jika Anda dapat memutuskan masalah Anda, maka Anda dapat memutuskan masalah korespondensi Post (PCP), yang diketahui tidak dapat ditentukan.

Ingat, PCP adalah masalah keputusan yang menanyakan apakah dalam satu set $2$ -tuples $P=\{(x_1,y_1),\ldots,(x_n,y_n)\}$ Anda dapat membangun urutan (termasuk. pengulangan) sedemikian rupa sehingga digabungkan $x_i$ dan digabungkan $y_i$ s dari urutan ini membentuk kata yang sama. Perhatikan bahwa alfabet harus memiliki setidaknya 2 karakter.

Jadi, biarkan $P$ menjadi contoh dari PCP. Pertimbangkan tata bahasa bebas konteks berikut, di mana kami telah memperkenalkan simbol terminal baru $t_i$ Untuk $i$ elemen ke-dalam $P$ . Tata bahasanya memiliki aturan berikut:

\begin{aligned} S & \to X! Y \\ X & \to x_{1} X^{'} t_{1} ∣ x_{2} X^{'} t_{2} ∣ \dots x_{n} X^{'} t_{n} \\ X^{'} & \to x_{1} X^{'} t_{1} ∣ x_{2} X^{'} t_{2} ∣ \dots x_{n} X^{'} t_{n} ∣ ε \\ Y & \to y_{1} Y t_{1} ∣ y_{2} Y t_{2} ∣ \dots y_{n} Y t_{n} ∣ ε \end{aligned}

$\begin{align} S& \to X \; ! \;Y \\ X& \to x_1 X' t_1 \mid x_2 X' t_2 \mid \cdots x_n X' t_n \\ X'& \to x_1 X' t_1 \mid x_2 X' t_2 \mid \cdots x_n X' t_n \mid \varepsilon\\ Y& \to y_1 Y t_1 \mid y_2 Y t_2 \mid \cdots y_n Y t_n \mid \varepsilon \\ \end{align}$ (Variabel

X^{'}

$X'$ hanya ada di sana untuk mengesampingkan

S \Rightarrow!

$S\Rightarrow !$ ).

Tentu saja, mengingat tata bahasa apa pun, kita dapat menemukan PDA yang sesuai yang menerima bahasa yang sama dengan tata bahasa. Jadi, buat PDA yang sesuai, dan kemudian gunakan algoritma hipotetis untuk masalah Anda untuk menentukan apakah PDA ini menerima kata apa pun dari formulir $u!v$ (Yaitu, apakah seseorang dapat memperoleh kata dari formulir tersebut $u!v$ dari tata bahasa ini). Saya akan menunjukkan cara menggunakan informasi ini untuk menyelesaikan contoh PCP $P$ .

Asumsikan sekarang $u!v$ adalah kata dalam tata bahasa ini. Kata $u$ memiliki dua bagian, akhiran, yang terdiri dari $t_i$ terminal, dan sisanya disebut awalan. Hal yang sama berlaku untuk $v$ . Kita punya $u=v$ jika dan hanya jika awalan dan sufiksnya bertepatan. Sufiks bertepatan hanya jika kita menggunakan urutan tupel yang sama $P$ untuk membangun kata-kata $u$ dan $v$ . Awalan dari $u$ dan $v$ bertepatan jika gabungan dari $x_i$ dan $y_i$ s (berdasarkan urutan tupel terbalik yang diberikan oleh $t_i$ s) sama. Karenanya $u=v$ jika dan hanya jika ada solusi untuk instance PCP $P$ .

Demikian pula, jika ada solusi untuk contoh PCP $P$ , maka dari solusinya mudah untuk membangun kata bentuk $u!v$ yang diturunkan dari tata bahasa ini.

Oleh karena itu contoh PCP $P$ punya solusi jika dan hanya jika tata bahasa ini mengandung kata dalam bentuk $u!v$ . Jika ada algoritma untuk memutuskan masalah Anda, kami dapat menggunakannya untuk menyelesaikan PCP. Namun tentu saja PCP diketahui tidak dapat diputus, sehingga masalah Anda juga tidak dapat diputuskan.

A.Schulz
sumber

1

Bagus! Yah, jelas lebih mudah daripada solusi saya sendiri. +1

Hendrik

1

Saya merasa sulit untuk mengikuti alur jawaban ini. Mengapa Anda berdebat tentang keberadaan PDA / tata bahasa di paragraf ketiga? Jika saya membaca dengan benar, Anda ingin memetakan instance PCP ke tata bahasa, sehingga mengurangi pertanyaan apakah PCP dapat dipilih. Untuk itu, Anda juga harus menunjukkan kebalikan dari paragraf terakhir, yaitu bahwa jika tidak

u! u

$u!u$ diterima, PCP tidak memiliki solusi. (Trik yang bagus dengan

t_{i}

$t_i$ , ngomong-ngomong.)

Raphael

@ Raphael, saya mengedit jawaban untuk menjawab komentar Anda. Poin bagus - terima kasih!

DW

5

Pendekatannya mungkin sebagai berikut. Cobalah untuk membuat bahasa bebas konteks (= PDA) yang mengkode langkah-langkah perhitungan TM, sehingga perhitungan lengkap berhasil jika ada kata dari bentuk yang Anda gambarkan.

Pertama, Anda perlu mengkode konfigurasi terpisah: isi kaset + status + posisi kepala (Anda akan melihat bahwa untuk kesetaraan tata bahasa). Bahasa bebas konteks dapat menyandikan satu langkah $C\vdash C'$ perhitungan yang disediakan Anda menggunakan gambar cermin $C\#m(C')$ dimana $m(C)$ menunjukkan gambar cermin (pembalikan) dari (Saya ceroboh di sini: Anda mungkin harus membedakan konfigurasi dan deskripsinya.)

Sekarang perhatikan bahasa langkah-langkah terpisah, disatukan dengan bahasa konfigurasi duplikat: $C_0\#C_1\#m(C_2)\#C_3\#m(C_4)\# \dots C_{2n-1}\#m(C_{2n})\#C_f!$ $C'_1\#m(C'_1)\#C'_2\#m(C'_2)\#\dots C'_{n+1}\#m(C'_{n+1})$ with for every $k$ , $C_{2k-1} \vdash (C_{2k})$ . This is context-free, additionally code $C_0$ as initial and $C_f$ as final configurations.

Now the first part ensures we have consecutive steps, the second part that successive configurations are equal. If both parts match we have a computation. Which we cannot decide.

That is the idea. I may have some indexes wrong, and the whole sequence has to be encoded in binary, but that can be solved.

Hendrik Jan
sumber

Okay I got it. However the part "Now consider the language of separate steps, concatenated with the language of duplicated configurations ..." could profit from further explanations. For example, you could use the correct indices. Anyway, its a nice idea.

A.Schulz

Bagaimana saya menunjukkan bahwa apakah PDA menerima string

Jawaban: