InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
Design a turing machine which recognizes language L = 101*1 |
|
Answer» The LANGUAGE L = {ww | w ∈ {0, 1}} tells that every string of 0’s and 1’s which is FOLLOWED by itself falls under this language. The logic for solving this problem can be divided into 2 parts: Finding the mid point of the string After we have found the mid point we match the symbols Example – Lets understand it with the help of an example. Lets string 1 0 1 1 0 1, so w = 1 0 1 and string is of form (ww). The first THING that we do is to find the midpoint. For this, we CONVERT 1 in the beginning into Y and move right till the end of the string. Here we convert 1 into y. |
|