Construct a NFA and DFA state diagram that recognizes the following language : L = {w | w is a palindrome }
Turing machine
Start at the beginning of the input tape with the read/write head on the leftmost cell.
Scan the input tape from left to right to check if the input string is in the form of am b” c” www.
Count the number of “a”s by moving right on the tape until a “b” is encountered.
If there is no “b” after all the “a”s, then the input string is not in the language A. Reject the input and halt.
If a “b” is found, move right on the tape until a “c” is found.
If there is no “c” after all the “b”s, then the input string is not in the language A. Reject the input and halt.
If a “c” is found, move right on the tape until the end of the string.
If the end of the string is reached and there are no more “w”s, accept the input string and halt.
If there are more “w”s, repeat the process starting from step 3.