Bagaimana saya bisa mengubah mesin Turing yang mengenali bahasa

Menurut artikel Wikipedia ini , tata bahasa tidak terbatas setara dengan mesin Turing. Artikel tersebut mencatat bahwa saya dapat mengubah mesin Turing apa pun menjadi tata bahasa yang tidak dibatasi, tetapi hanya menunjukkan cara mengubah tata bahasa menjadi mesin Turing.

Bagaimana saya melakukan itu dan mengubah mesin Turing yang mengenali bahasa menjadi tata bahasa yang tidak dibatasi? Saya telah mencoba mengganti aturan transisi dengan aturan tata bahasa, tetapi mesin Turing dapat memiliki banyak konfigurasi negara yang berbeda juga ...$L$

Kami menyandikan konten rekaman mesin Turing dalam bentuk sentensial; satu set khusus non-terminal mengkodekan keadaan saat ini. Hanya ada satu dari mereka dalam bentuk sentensial pada titik waktu mana saja, ditempatkan di sebelah kanan simbol yang ditunjuk TM saat ini.

Gagasan penting kedua adalah bahwa kita harus membalik proses: TM mengambil kata tersebut sebagai input dan mengubahnya menjadi atau 0 , atau tidak berakhir. Tata bahasa, bagaimanapun, harus menghasilkan kata. Untungnya, tata bahasa secara inheren non-deterministik, jadi kita bisa membiarkannya "menebak" dari mana 1 penerima berasal; semua kata yang menyebabkan TM menerima dapat dihasilkan kemudian.$1$$0$$1$

Misalkan himpunan state-nonterminals; wlog misalkan Q 0 menjadi starting-state-nonterminal dan Q F ⊆ Q set dari accept-state-nonterminals. Pertama, kita perlu aturan awal yang menghasilkan semua kemungkinan konfigurasi yang dapat diterima:$\cal{Q} = \{Q_0,\dots,Q_k\}$$Q_0$$\cal{Q}_F \subseteq \cal{Q}$

$\qquad \displaystyle S \to \#1Q_f\# \qquad$untuk semua .$Q_f \in \cal{Q}_F$

Demikian pula, kita berakhir ketika kita "mencapai" keadaan awal di posisi yang benar, yaitu pada simbol pertama:

$\qquad \#aQ_0 \to \#a \qquad$$a \in \Sigma$

Menerjemahkan transisi keadaan aktual sangat mudah:

$\qquad \begin{align} aQ &\to cQ' \qquad\ \,\text{ for } a,c \in \Sigma \land (a,Q,N) \in \delta(c,Q') \\ aQb &\to acQ' \qquad \text{ for } a,b,c \in \Sigma \land (b,Q,L) \in \delta(c,Q') \\ abQ &\to cQ'b \qquad\, \text{ for } a,b,c \in \Sigma \land (a,Q,R) \in \delta(c,Q') \end{align}$

$\#$$\#$$\#$$d=\#$

$\#$$Q_0$$\Sigma$