Define turing Machine and design it to recognize the language L={0^n 1...
Turing Machine:
A Turing Machine is a mathematical model of a hypothetical computing machine that can manipulate symbols on a tape according to a table of rules. It is the foundation of the modern theory of computation.
Designing Turing Machine for L={0^n 1^2n/n>=1}:
To design a Turing Machine that recognizes the language L={0^n 1^2n/n>=1}, we need to follow these steps:
1. Start at the leftmost cell of the tape.
2. Read the input symbol.
3. If the input symbol is 0, replace it with X and move to the right until the next symbol is not 0.
4. If the input symbol is 1, replace it with Y and move to the right until the next symbol is not 1.
5. If the input symbol is blank, move the head to the left until the first non-blank symbol is encountered.
6. If the first non-blank symbol encountered is X, replace it with 0 and move to the right until the next non-blank symbol is encountered.
7. If the first non-blank symbol encountered is Y, replace it with 1 and move to the right until the next non-blank symbol is encountered.
8. If the next non-blank symbol is 0, repeat steps 3-7.
9. If the next non-blank symbol is 1, repeat steps 3-7.
10. If the next non-blank symbol is blank, move to the left until the first non-blank symbol is encountered.
11. If the first non-blank symbol encountered is X, replace it with 0 and move to the right until the next non-blank symbol is encountered.
12. If the next non-blank symbol is Y, reject the input.
13. If there are no more symbols to read, accept the input.
Example:
Let's illustrate the action of the Turing Machine in accepting or rejecting the word 0^3 1^3.
1. Start at the leftmost cell of the tape and read the input symbol 0.
2. Replace the input symbol with X and move to the right until the next symbol is not 0.
3. Replace the input symbol with X and move to the right until the next symbol is not 0.
4. Replace the input symbol with X and move to the right until the next symbol is not 0.
5. Replace the input symbol with Y and move to the right until the next symbol is not 1.
6. Replace the input symbol with Y and move to the right until the next symbol is not 1.
7. Replace the input symbol with Y and move to the right until the next symbol is not 1.
8. If the next non-blank symbol is blank, move to the left until the first non-blank symbol is encountered.
9. If the first non-blank symbol encountered is X, replace it with 0 and move to the right until the next non-blank symbol is encountered.
10. If the next non-blank symbol is Y, reject the input.
Since the Turing Machine rejected the input, it means that the word 0^3 1^3 is not in the language L={0^n 1^2n/n>=1}.
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).