2078 3

Theory of Computation207810 marksEncoding of Turing Machine

Construct a Turing Machine that accepts the language of odd length strings over alphabet {a, b}. Give the complete encoding for this TM as well as its input string w = abb in binary alphabet that is recognized by Universal Turing Machine.

Construct a Turing Machine that accepts the language of odd length strings over alphabet {a, b}. Give the complete encoding for this TM as well as its input string w = abb in binary alphabet that is recognized by Universal Turing Machine.[10]

The TM accepts a string if and only if its length is odd. We use a two-state parity tracking approach: the TM scans the input one symbol at a time, toggling between an "odd count" state and an "even count" state. When it hits a blank (end of input), it accepts if it is in the odd-count state. ---...

Up nextDefine the term alphabet, prefix and suffix of string, concatenation and Kleen closure wit