Q156: Turing machine to check palindrome strings

Consider the design of a Turing Machine which accepts the language consisting of all palindromes of 0’s and 1’s. Initially, the input string is written on to the tape preceded and followed by infinity of blank symbols and the tape head is on the leftmost symbol of the input string.

The above table represents the transitions for such a Turing machine.

Question 156: For a string of length ‘n’, how many transitions will be there before acceptance of the string?

1. O(n)
2. O(n log(n))
3. O(n^2)
4. O(n^3)

Solution: Basically, for each pair of symbols (one from the front and one from the reverse), we may have to do O(n) transitions while traversing the tape from left to right and back. Hence for all ‘n/2’ pairs, it would lead to O(n^2) transitions. Hence, the correct answer is option 3.

Q9: Context Free Grammar

Question #9: What does the following grammar represent?

Options:

1. All strings which start with 0 and end with 1.
2. All strings whose only first and last symbol is same.
3. All strings that reads the same forward and backward.
4. All strings of 0 and 1.

 

Solution:

First three rules are the basis and 4^th and 5^th rule can form any string by appending same symbol before and after the string. These strings are known as palindrome strings. Hence, the correct answer is option 3.