finite-automataturing-machines

Turing Machine for {XF*X|F)*


I have a language:

(XF*X|F)*

over the alphabet:

{X,F}

How can I get/design a Turing machine to recognize that language?


Solution

  • That's trivial:

    digraph _ {
        _ [ shape=none, label="" ]
        1 [ shape=doublecircle ]
        2 [ shape=circle ]
        _ -> 1
        1 -> 1 [ label="F" ]
        1 -> 2 [ label="X" ]
        2 -> 2 [ label="F" ]
        2 -> 1 [ label="X" ]
    }