Consider a (single-tape) Turing machine M2, with input alphabet {a, b} and accept state qa, that has the following behav
Posted: Sat May 14, 2022 3:04 pm
Consider a (single-tape) Turing machine M2, with input alphabet
{a, b} and accept state qa, that has the following behaviour: Given
any input string w ∈ {a, b}∗, M2 halts in an accepting state in the
configuration qax|w| #wR, where wR is the reverse of w. For
example, on input abb, M2 halts in an accepting configuration
qaxxx#bba, while on input baaaba it halts in an accepting
configuration qaxxxxxx#abaaab.
Create a state diagram in JFLAP for M2, using the fewest states
possible. You may assume a two-way infinite tape, and the reject
state may be omitted from your diagram
{a, b} and accept state qa, that has the following behaviour: Given
any input string w ∈ {a, b}∗, M2 halts in an accepting state in the
configuration qax|w| #wR, where wR is the reverse of w. For
example, on input abb, M2 halts in an accepting configuration
qaxxx#bba, while on input baaaba it halts in an accepting
configuration qaxxxxxx#abaaab.
Create a state diagram in JFLAP for M2, using the fewest states
possible. You may assume a two-way infinite tape, and the reject
state may be omitted from your diagram