質問

I need help creating a single tape deterministic Turing machine for this language enter image description here

here I am not sure how to determine which strings the TM will accept. How can I make the machine accept strings where a=c? because the b part has elements from both a and c.

役に立ちましたか?

解決

Maybe you can try do adapt a machine which accepts palidromes: you read a character to the left. If it belongs to {0,1} you delete it and go to the right (the last character). If the character belongs to {2,3}, you delete it and go back to the left (the first character). Repeat it until you find a character which does not belong to the "a" or "c" side (and check the last character if you were on the left), the remaining characters should belong to the "b" block.

ライセンス: CC-BY-SA帰属
所属していません StackOverflow
scroll top