7

Turing Machine

7.1 BASIC OF TURING MACHINE

Q. What is Turing Machine? What is the significance of it?

Ans. Turing Machine is the machine format of unrestricted language, i.e. all types of languages are accepted by Turing Machine. In 1936, this machine was proposed by A.M.Turing as a model of any possible combination. Any computational process carried out by present days computer can be done on Turing machine.

Based on Turing machine a new theory called “Theory of undecidable problems” is developed. These types of problems can not be solved by any computer. Turing machine is a model of present days' computer. We can say that is any problem is not solved by Turing Machine, that problem can not be solved by computer, i.e. there does not exist any program or algorithm to solve it.

Q. Define Turing Machine. Give a block diagram with specified functions of each parts of it.
What is the difference with Turing machine and Two way Finite Automata?

Ans. Turing machine in short TM is defined by 7 touples (Q, ∑, Γ, δ, q₀, B, F), where

Q: Finite set of states

∑: Finite set of input alplabets.

Γ: Finite set of allowable tape symbol.

δ: Transitional function

q₀: Initial state

B: Is a symbol of Γ called blank

F: Final states.

Where δ is a mapping from Q X Γ (Q X Γ X {L, R, H})

That is from one state by getting one input from the input tape the machine moves to a state, writing a symbol on the tape and moves to left, right or halts.

Mechanical Diagram:

A Turing machine consists of an input tape, read-write head and finite control. The input tape contains input alphabets with infinite number of blanks at the left and right hand-side of the input symbols. The read-write head reads an input symbol from the input tape and send it to finite control. The machine must be in some state. In Finite control transitional functions are written. According to the present state and present input suitable transitional function is executed. Upon execution of a suitable transitional function the following operations are performed

(a) The machine goes into some state

(b) Writes a symbol in the cell of the input tape from where the input symbol was scanned

(c) Moves the reading head in left or right or halts.

Two way finite automata has a movement in both left and right-side like Turing machine. But, in Turing machine both read and write operations are done from and on the input tape, but for Two way Finite Automata only read operation is done, no write operation is done. A string is accepted by a Turing machine if the string is totally traversed and the machine halts. A string is accepted by a Two way finite automata is the string is totally traversed and the machine reaches to a final state.

Q. Define instantaneous description in the respect of Turing Machine.

Ans. The Instantaneous Description (ID) of Turing machine remembers

(a) The contents of all the cells of the tape, starting from the right most cell upto atleast the last cell, containing a non-blank symbol and containing all cells upto the cell being scanned.

(b) The cell currently being scanned by the read write head and

(c) The state of the machine.

at a given instance of time.

Q. Show the movement of the read-write head and the contain of the input tape for the string ‘abba’ traversed by the following Turing Machine

Ans.

7.2 EXAMPLES

Q. Design a Turing Machine to accept the language L = {aⁿbⁿ ≥ 1}. Show an ID for the string ‘aaabbb’ with tape symbols.

Ans. The string consists of two types of input alphabets, ‘a’ and ‘b’. Number of ‘a’ is equal to number of ‘b’. All the ‘a’s will come before ‘b’. In the language set there is at least one ‘a’ and one ‘b’. Traverse the leftmost ‘a’ and replace this by X, then traverse right to find the leftmost ‘b’. When it is found, replace ‘b’ by Y and traverse left to find the next ‘a’. When traversing left if ‘X’ is found, the next ‘a’ is the ‘a’ after the traversed X. So, traverse right again and replace ‘a’ by X and traverse right to find the next ‘b’. The transitional functions of the machine are designed as follows

When the leftmost ‘a’ is traversed, that ‘a’ is replaced by X and the head moves to one right.

The transitional function is

Then the machine needs to search for the left most ‘b’. Before that ‘b’ there exist (n - 1) numbers of ‘a’. Those ‘a’ are traversed by

When the leftmost ‘b’ is traversed the state is q₁. That ‘b’ is replaced by Y, the state is changed to q₂ and the head moved to one left. The transitional functional is

Then it needs to search for the second ‘a’ starting from the left. The first ‘a’ is replaced by X, that means the second ‘a’ exists after X. So, it needs to search for the right most ‘X’. After traversing the leftmost ‘b’ the head moves to left to find the rightmost X. Before that it has to traverse ‘a’. The transitional function is

After traversing all the ‘a’ we get the rightmost ‘X’. Traversing the X the machine changes its state from q₂ to q₀ and the head moves to one right. The transitional function is

From the traversal of second ‘b’ onwards the machine has to traverse ‘Y’. The transitional function is

Like the same, after traversing ‘b’ the machine has to traverse some Y to get the right most ‘X’.

When all the ‘a’s are traversed the state is q₀, because before that state was q₂ and the input was X. The head moves to one right and gets a Y. Getting a Y means all ‘a’s are traversed and same number of ‘b’s are traversed. Traversing right if at last the machine gets no ‘b’ but blank ‘B’ then the machine halts. The transitional functions are

ID for the string ‘aaabbb’

First the tape symbols are

Q. Design a Turing Machine to accept the language L = {WW^R, where W ε (a, b)⁺}. Show an ID for the string ‘abaaaaba’ with tape symbols.

Ans. W^R is the reverse of W. If W starts with ‘a’ or ‘b’, W^R ends with ‘a’ or ‘b’ respectively. If W ends with ‘a’ or ‘b’, W^R starts with ‘a’ or ‘b’, respectively. The Turing Machine can be designed as follows:

If the string W starts with ‘a’, upon traversal that ‘a’ is replaced by X with state change from q₀ to q_l and the head moves to one right. The transitional function:

The W^R ends with ‘a’ if W starts with ‘a’. The machine needs to search the end ‘a’ of W^R. Before that the machine needs to traverse the end symbols of W and beginning symbols of W^R. The transitional functions are

After the end symbol of W^R there exists blank symbol B. In the traversal process if the machine gets a B, it traverses back to left side and gets the end symbol of W^R. The transitional functions are

Now the machine needs to search for the second symbol of W. Before that it has to traverse the beginning symbols of W^R and the end symbols of W. The transitional functions are

When the machine gets the right most X, it recognizes that the next symbol of W exists after that ‘X’. The transitional function:

If the string W starts with ‘b’ the transitions are same as the previous but with some states changed. The transitional functions are

From second traversal onwards the machine needs not to traverse upto the end of W^R. In state q₁ (W starts with ‘a’) or q₄ (W starts with ‘b’) if the machine gets X or Y it traverses back to left to point the rightmost ‘a’ or ‘b’. The transitional functions are

When all the symbols of W and W^R are traversed, the machine gets X or Y in the state q₀. The machine halts if in state q₀ it gets X or Y. The transitional functions are

The transitional functions can be given in a tabular format like this

ID for the string ‘abaaaaba’

(Here the symbol is bold represents the read write-head position)

 

Q. Design a Turing Machine to accept the language L = {set of all palindrome over a,b}.
Show IDs for null string, ‘a’, ‘aba’ and ‘baab’.

Ans. Palindrome are of two types (a) Odd palindrome, where number of characters are odd anδ (b) Even palindrome, where number of characters are even. Null string is also a palindrome.

A string starts with ‘a’ or ‘b’ must ends with ‘a’ or ‘b’, respectively if the string is a palindrome.

If a string starts with ‘a’ that ‘a’ is replaced by blank symbol ‘B’ upon traversal with a state change from q₁ to q₂ and right shift of the read-write head. The transitional function:

Then the machine needs to search for the end of the string. The string must ends with ‘a’ and that ‘a’ exists before blank symbol B at the right-hand-side. Before getting that blank symbol the machine needs to traverse all the remaining ‘a’ and ‘b’ of the string. The transitional functions are

The machine now needs to search for the second symbol (from the starting) of the string. That symbol exists after the blank symbol B, which is replaced at the first. Before that the machine needs to traverse the remaining ‘a’ and ‘b’ of the string. The transitional functions are

If the string starts with ‘b’ the transitional functions are same as ‘a’ but some states changed. The transitional functions are

When all ‘a’ and ‘b’ are traversed and replaced by B, the states may be one of q₃ or q₆, if the last symbol traversed is ‘a’ or ‘b’, respectively. Transitional functions for acceptance are

Null string is also a palindrome. On the tape null symbol means blank B. In state q₁ the machine gets the symbol. The transitional function is

The transitional functions in tabular form are represented as

ID for null string

ID for the string ‘a’

ID for the string ‘aba’

ID for the string ‘baab’

Q. Design a Turing Machine to accept the language L = aⁿbⁿcⁿ, where n ≥ 1.

Ans. This is a context sensitive language. The language consists of a, b, c. Here number of ‘a’ is equal to number of ‘ b’ which is equal to number of ‘c’. The n number of ‘c’ are followed by n number of ‘b’ which are followed by n number of ‘a’. The Turing machine is designed as follows. For each ‘a’, search for ‘b’ and ‘c’ and again traverse back to left to search for the leftmost ‘a’. The ‘a’ is replaced by ‘X’, ‘b’ is replaced by ‘Y’ and ‘c’ is replaced by ‘Z’.

When all ‘a’ are traversed and replaced by ‘X’ the machine traverses right side to find if any untraversed ‘b’ or ‘c’ left or not. If not the machine gets Y and Z and at last Blank. Upon getting Blank symbol the machine halts.

The transitional functions are

Upon executing the last transitional function the machine halts.

The transitional functions in tabular form are represented as

Q. Design a Turing Machine to perform the concatenation operation on string of ‘1’
Show an ID for w1= 111 and w2 = 1111.

Ans.: The Turing machine does the concatenation operation on two strings w₁ and w₂. These two strings are placed on tape of the Turing Machine separated by Blank symbol B. After traversal the blank symbol is removed and the two strings are concatenated.

The transitional functions are

(This machine is also applicable for performing Z = X+Y, where X = |w1| and Y = |w2|)

ID for w1= 111 and w2 = 1111 resulting 1111111

Q. Design a Turing machine to perform the following operation
           f(x,y) = x-y, where x > y

Show an ID for 4–2 =2.

Ans.

 

This performs subtraction operation. Here x and y both are integer number. Let x = |W₁| and y = |W₂|. Where W₁ and W₂ are strings of ‘1’. The two strings are placed on the input tape separated by B.

Starting traversal from left-hand-side ‘1’ the machine moves towards right. It traversed B with a state changed from q₀ to q₁. In state q₁ it again traverses right to find B, that is end of second string. It changes its state and traverses left and changes the rightmost ‘1’ by B(With state change and traversing left). It traverses the separating ‘B’ symbol and all ‘1’s of the first string and find the beginning of first string, which starts after B at the left hand side. It changes the first ‘1’ by B and again traverses right. This process continues till all ‘1’s of the second string are replaced by ‘B’.

The transitional functions are

ID for 4–2 = 2:

Q. Design a Turing Machine to accept string L = (a,b)*, where N(a) + N(b) = even.

Ans. The string consists of any combination of ‘a’ and ‘b’. In the string total number of characters is even. The Turing machine is designed as follows. If the machine gets ‘a’ or ‘b’ it moves right with state changed from q₀ to q₁. In state q₁ if the machine gets ‘a’ or ‘b’, it moves right with state changed from q₁ to q₀. In state q₀ if the machine gets blank symbol it halts.

The transitional functions are:

Q. Design a Turing machine for infinite loop.

Ans. Infinite loop means the machine does not halts. It can be designed in the following way.

Let the string consists of only ‘a’. If ‘a’ is traversed in state q₁, the machine moves right. After all ‘a’ of the string are traversed B is traversed and the machine moves left and changes state to q₂. Getting ‘a’ in state q₂ the machine moves left again to find the beginning of the string.

When the machine gets ‘B’, it moves right again with changed state from q₂ to q₁. This process continues and the machine falls in an infinite loop.

The transitional functions are:

Q. Design a Turing Machine to perform the function f(x) = x+1.

Ans. The function adds a ‘1’ with the value of x. If one blank symbol at the right-hand-side is replaced by ‘1’ then the machine can be easily designed.

The transitional functions are:

Q. Design a Turing machine which copies a string of ‘0’ and paste it just after the string. Show an ID for the string 00.

Ans. We have to design a Turing Machine which performs copy paste operation

The machine is designed in the following way.

(a) Replace each ‘0’ of the given string by X.

(b) Go to right and find the blank and traverse left and replace the right most X by 0 again.

(c) Then traverse to right and replace the first ‘B’ after the right most ‘0’ by ‘0’ and traverse left. Repeat the last two steps until there are no more X.

The transitional functions are:

ID for the string 00

Q. Design a Turing Machine which performs 1's complement operation on binary string.

Ans. Complement operation means ‘0’ is converted to ‘1’ and ‘1’ is converted to ‘0’.

The transitional functions for the Turing Machine are:

Q. Design a Turing Machine to perform 2's Complement operation on binary string. Show IDs for the string 010 and 101

Ans. To calculate 2's complement, first a binary string is converted into 1's complement then with that 1's complement 1 is added to get 2's complement. If in the 1's complement the rightmost bit is ‘0’, that ‘0’ is converted into ‘1’. If the rightmost bit is ‘1’,that ‘1’ is converted into ‘0’ and traverses left to find a ‘0’. If it gets ‘1’ that ‘1’ is converted into ‘0’ again. If it gets ‘0’ that ‘0’ is converted into ‘1’ and traverses left to find the leftmost symbol of the string.

The Turing Machine is designed in the following way.

Starting from state q₁ if the machine gets ‘1’ or ‘0’ that is converted into ‘0’ or ‘1’, respectively and the machine traverses right. When the machine gets B, it changes its state from q₁ to q₂ and traverse left. If it gets ‘0’, that is converted into ‘1’ with state changed from q₂ to q₃ and traverses left to find the leftmost symbol.

ID for 010

ID for 101

Q. Design a Turing Machine for set of all strings with equal number of ‘a’ and ‘b’.

Ans. The machine is designed as follows.

The machine first finds an ‘a’, replace this by X and moves left. When it gets blank again moves right to search for ‘b’ and replace it by Y. Again traverse left to search for ‘a’. The process continues till right side Blank symbol is traversed in state q₀

The transitional functions are:

Q. Design a Turing Machine to accept the language L = aⁿb²ⁿ n >0

Ans. Number of ‘b’ is equal to twice the number of ‘a’. In the language, all ‘a’ appear before ‘b’. The Turing machine is designed as follows.

Replace one ‘a’ by X and traverse right to search for the end of the string. After getting ‘B’ traverse left and replace two ‘b’s by Y. In the state q₀ if the machine gets Y as input it halts.

The transitional functions are.

7.3 TRANSITIONAL REPRESENTATION OF TURING MACHINE

Q. How a Turing Machine can be denoted by graphical notation?

Ans. The mathematical notation for a Turing Machine is (Q, Σ, Γ, d, q₀, B, F). In a Turing Machine the transitional function δ consists is in the form Q X Γ → (Q X Γ X {L, R, H}), where first is a present state, second is present input (Single character ∈ Γ). The transition produces a state, a symbol ∈ G written on the input tape and the head moves either left or right or halts.

In the graphical notation of Turing Machine there are states. Among them a circle with an arrow indicates a beginning state and a state with double circle indicates a final state, where the machine halts finally. The state transitions are denoted by arrow. The labels of the state transitions consists of input symbol, symbol written on the tape after traversal and the direction of movement of the read-write head (Left, Right or Halt).

 

Q. Design a Turing Machine by transitional notation for the language
          L = aⁿbⁿ, where n> 0.

Ans. When the machine traverses ‘a’, replace that ‘a’ by X and traverse right to find the leftmost ‘b’. Replace that ‘b’ by ‘Y’ and traverse left to find the second ‘a’. The second ‘a’ exists after ‘X’, which was replaced first for the first ‘a’. By this process when n number of ‘a’ and n number of ‘b’ are traversed and replaced by X and Y, respectively then by getting a blank (B) the machine halts.

The transitional representation of the Turing machine:

Q. Design a Turing Machine by transitional notation for the language

     L = {set of all palindrome over a,b}.

Ans. Palindrome can be of two types Odd palindrome and Even palindrome. Null string is also a palindrome. There are three paths to reach to the final state with Halt from q₁, the beginning state.

WHAT WE HAVE LEARNED SO FAR

1. Turing Machine was proposed by A.M. Turing in 1936 as a model of any possible combination. Any computational process carried out by present day's computer can be done on Turing machine.

2. Turing Machine is the machine format of unrestricted language, i.e. all types of languages are accepted by Turing Machine.

3. Indecisive problems are not solved by computer as no Turing machine can be developed for these problems.

4. Mathematical description of Turing Machine consists of 7 touples (Q, Σ, Γ, δ, q₀, B, F), where Q: Finite set of states, Σ: Finite set of input alplabets, Γ: Finite set of allowable tape symbol, d: Transitional function, q₀: Initial state, B: is blank symbol, and F: Final state.

5. The transitional functions of Turing Machine is in the form Q X Γ, → (Q X Γ X {L, R, H}), i.e. from one state by getting one input from the input tape the machine moves to a state, writing a symbol on the tape and moves to left, right, or halts.

6. The mechanical diagram of Turing machine consists of input tape, finite control and read-write head.

7. Upon execution of a transitional function the machine goes to some state, writes a symbol in the cell of the input tape from where the input symbol was scanned and moves the reading head in left or right or halts.

8. The ID of a Turing Machine remembers the contents of all cells from right most to atleast leftmost, the cell currently being scanned by the read write head and the state of the machine at a given instance of time.

SOLVED PROBLEMS

1. Design a Turing Machine to test a string of balanced parenthesis. Show an ID for ( )(( )).

Ans. There are two types of parentheses-open parentheses and close parentheses. Balanced parenthesis means for each open parenthesis there is a close parenthesis. It may be nested like ( ( ( ) ) ) or may be non nested like ( ( ) ( ) ) or ( )( )( ) or any other form. However, for each open parenthesis there is a close parenthesis. [The definition that balanced parenthesis means equal number of open and close parentheses is wrong.

As an example, ) ( )( ) ( is not a balanced parenthesis]. The string must start with an open parenthesis and after that open parenthesis or close parenthesis can appear, but for any position of the string, number of open parenthesis is greater than or equal to number of close parenthesis.

The Turing Machine is designed as follows. Start from the left most symbol and traverse right to find the first close parenthesis. The transitional function:

Upon getting the first close parenthesis replace it by ‘X’, change the state to q₁ and move left to find the open parenthesis for the replaced close parenthesis. The transitional function:

Getting the open parenthesis replace it by ‘X’ and change the state to q₀. The transitional function

Then traverse towards right to find the close parenthesis. Here the machine may have to traverse X, which is the replaced symbol of close parenthesis. The transitional function for traversing this is

For a nested parenthesis like (( )), the machine have to traverse X, which is the replaced symbol of open parenthesis at the time of finding open parenthesis. The transitional function for traversing this is

Traversing right if B appears as input then there is no parenthesis (Open or close) left at the right side. Then traverse left to find if any parenthesis left at the left side or not. The transitional function is

At the time of left traversing the machine have to traverse X by the following transitional function

At the left hand side if it gets B, the machine halts.

ID for ( ) (( ))

2. Design a Turing Machine to perform n mod 2 (Or checking whether a number is odd or even) From here by instantaneous description check whether the number 5 is odd or even.

Ans. An n is any number of same input alphabets. Let take n number of ‘0’s. The machine is in state q₀ and the read-write head is on the beginning input symbol of the input tape. Getting input ‘0’ it moves towards right replacing ‘0’ by ‘B’ and changes state to q₁. The transitional function:

In state q₁ by getting input ‘0’ it moves towards right replacing ‘0’ by ‘B’ and changes state to q₀. The transitional function

By the previous two transitional functions all the ‘0’s are replaced by ‘B’. If number of ‘0’ is even then the machine will reach to the end of the string with state q₀. At the end it will get ‘B’ and traversing that the machine will halt. (Means the number is even)

The transitional function

If number of ‘0’ is even then the machine will reach to the end of the string with state q₁. With getting input symbol ‘B’ it will traverse left by changing state to q_3. The transitional function:

In state q₃ by getting input B the machine halts by replacing ‘B’ to ‘0’. (Means the number is odd). The transitional function

ID for n = 5: The string is 00000

3. Design a Turing Machine to perform reverse of a string, where the string ∈ (a, b)*.

Ans. The string consists of ‘a’ and ‘b’. The string may start with ‘a’ or may start with ‘b’. If the string starts with ‘a’, the reverse of the string will ends with ‘a’. Same for ‘b’ also.

If the beginning state is q₁ and if the string starts with ‘a’, the TM will traverse right replacing ‘a’ by ‘X’ and changing state to q₂. (This q₂ specifies that the symbol was ‘a’). The transitional function:

At the time of traversing right the machine can get ‘a’ or ‘b’. The transitional functions for traversing ‘a’ and ‘b’ are

If it gets ‘B’, means the string is end. The TM changes the state to q₃ and traverses left by the transitional function

The string may ends with ‘a’ or may ends with ‘b’. As the beginning symbol was ‘a’ (Which is memorized by the machine by state q₂, then q₃) the end symbol will be replaced by X, whatever it may be. However, the end symbol will be the beginning symbol. So, what the end symbol is – it will be memorized by different states. In this case if the end symbol is ‘a’, it will be memorized by changing state q₃ to q₆ and if the end symbol is ‘b’, it will be memorized by changing q₃ to q₇. The transitional functions are:

Traversing left the TM has to traverse ‘a’ or ‘b’. It the state is q₆, the transitional functions are:

At the time of traversing left the TM may get ‘X’ or ‘Y’, the replaced symbols of ‘a’ or ‘b’. The machine is in state q₆, which means the right most symbol of the string was ‘a’. Upon getting ‘X’ or ‘Y’ at the left end the TM replaces it by ‘X’ and changes the state to q₁. The transitional functions are:

If the string starts with ‘b’ the transitions are same as the string starts with ‘a’, but only some changes of states. The transitional functions are:

If the end symbol is ‘b’ at the time of traversing left the transitional functions are:

By the above mentioned transitional functions the total string is traversed and reversed but in the place of ‘a’ and ‘b’ there are ‘X’ and ‘Y’.

From the second time of traversing the string, the TM needs not to find the symbol ‘B’ to mark the right end of the string. In the state q₂ or q₅, it will get ‘X’ or ‘Y’, which are representations of already traversed symbol. The transitional functions are

The string may be of even length or odd length. For odd length string the middle element may be ‘a’ or ‘b’. If the middle element is ‘a’, then after replacing the middle element by ‘X’ the TM moves right but it finds either ‘X’ or ‘Y’ (Because all the other symbols are already replaced). It backs left by changing the state to q₃ or q₅ using the transitional functions mentioned above. At the left again it gets either ‘X’ or ‘Y’. The TM changes the state to q₈ and moves right by the following transitional functions:

If the string is of even length then the machine gets ‘X’ or ‘Y’ in the state q₁ after replacing all the ‘a’ and ‘b’. The transitional functions are:

The machine traverses right to find the end of the string consists of ‘X’ and ‘Y’. When it gets ‘B’, it traverses left by changing the state from q₈ to q₉.

In the state q₉ at the time of traversing left the TM replaces all ‘X’s by ‘a’ and all ‘Y’s by ‘b’.

By this process when it gets the symbol ‘B at the left it halts.

If the string is a blank string (No ‘a’ and/or ‘b’), the machine gets ‘B’ in the state q₁ and halts.

The transitional functions are represented in the tabular format.

MULTIPLE CHOICE QUESTIONS

1. Turing Machine is the machine format of———language

(a) Type 0,

(b) Type 1,

(c) Type 2,

(d) Type 3.

2. Which is not a part of the mechanical diagram of Turing Machine?

(a) Input tape,

(b) Read-write head,

(c) Finite Control,

(d) Stack.

3. Difference between Turing Machine and Two way FA is in

(a) Input Tape,

(b) Read-write head,

(c) Finite Control,

(d) All of these.

4. Difference between Turing Machine & Push down automata is in

(a) Input Tape,

(b) Finite Control,

(c) Stack,

(d) All of these.

5. Which is not true for mechanical diagram of Turing Machine

The head moves in both directions.

The head reads as well as writes.

Input string is surrounded by infinite number of blank in both side.

Some symbols are pushed into the stack.

6. In Turing Machine transitional function δ is in the form

(where Q is the finite set of states, Σ is the finite set of input alphabets, Γ is the allowable tape symbol, L means left, R means right and H means halt)

7. Which of the strings is accepted by Turing Machine?

(a) L = aⁿc^mbⁿ, where m, n > 0,

(b) L = aⁿbⁿcⁱ, where n, i > 0,

(c) L = aⁿbⁿcⁿ , where n > 0,

(d) All of the above.

8. Which is not true for Instantaneous Description (ID) of Turing Machine.

(a) It remembers the state of the machine

(b) It remembers the cell currently being scanned by the read write head

(c) The contents of all the cells of the tape.

(d) The content of the cell on which the head previously be in.

Ans: 1. a 2. d 3. b 4. c 5. d 6. a 7. d 8. d

EXERCISES

1. Construct a Turing machine for the followings

2. Design a Turing Machine which acts as a eraser.
[Hints: Starts from left-hand-side, scan each symbol from left to right and replace it of these by blank. Halts if gets blank.]

3. Design a Turing Machine which replaces ‘0’ by ‘1’ and ‘1’ by ‘0’ of the string traversed.

4. Design a Turing Machine to accept the string L = {aⁿb^mc^n+m, where n > 0, m > 0}
[Hints: Traverse an ‘a’, replace it by X and moves right tofind thefirst ‘c’ and replace it by Y. Then traverse left to find the second ‘a’. By this process replace n number of ‘a’ by X and n number of ‘b’ by Y. By the same process replace m number of ‘b’ by Z and last m number of ‘c’ by Z ]

5. Design a Turing Machine to accept the string L = {a^mb^m+nc“, where m, n > 0}

6. Design a Turing Machine by transitional notation for the following languages

(a) L = aⁿbⁿ, n > 0,

(b) L = {aⁿbⁿc^md^m, where m,n ≥ 1},

(c) L = {aⁿbnc^m, where n,m ≥ 1}.

FILL IN THE BLANKS

1. All types of languages are accepted by———

2. According to Chomsky hierarchy Type 0 language is called———

3. Diagram of Turing Machine is like Finite Automata but here the head moves———

4. The head of Turing machine is called———

5. The string aⁿbⁿcⁿ, n > 0 is accepted by———

6. Turing Machine is called———

ANSWERS

1. Turing Machine

2. Unrestricted Language

3. In both direction

4. Read Write Head

5. Turing Machine

6. Universal Machine