Design a Turing machine for each of the following languages. First, give a high

Question

Design a Turing machine for each of the following languages. First, give a high level description of the Turing machine (8 marks) then give formal description of the TM and draw state diagram (10 marks). a) {w | w is a string over alphabet {0, 1} and, either (i) w contains more 0s than 1s if it starts with a 0, or (ii) w contains more 1s than 0s if it starts with a 1} Some examples words in the language are as follows: 00, 01010, 1110, 0011100, 1010111, 1111, 11001011 Some examples of strings NOT in the language are as follows: 10, 01, 1000, 01011, 0001010111, 110100

Explanation / Answer

high level description of the Turing machine:

The TM is then viewed as a string-function which takes initial tape contents u to whatever the non blank portion of the tape is when reaching qhalt . If v is the tape content upon halting, the notation fM (u) = v is used.
If M crashes during the computation, or enters into an infinite loop, M is said to be undefined on u.
A Turing Machine (TM) has finite-state control and an infinite read-write tape. The tape serves as both input and unbounded storage device.
The tape is divided into cells, and each cell holds one symbol from the tape alphabet.
There is a special blank symbol B. At any instant, all but finitely many cells hold B.
Tape head sees only one cell at any instant. The contents of this cell and the current state determine the next move of the TM
A move consists of:
replacing the contents of the scanned cell repositioning of the tape head to the nearest cell
on the left, or on the right changing the state.
The input alphabet is a subset of the tape alphabet. Initially,the tape holds a string of input symbols (the input), starting on the left of the tape, with in infinite sequence of blanks to
the right after the input . The initial position of the head is the leftmost symbol.

A high-level description of a Turing machine is a
description of the form
M = “On input x:
Do something with x.”
Example1:
M = “On input x:
Repeat the following:
If |x| 1, accept.
If the first and last symbols of x aren't
the same, reject.
Remove the first and last characters of x

Example2:
M = “On input x:
Construct y, the reverse of x.
If x = y, accept.
Otherwise, reject.
Example3:
M = “On input x:
If x is a palindrome, accept.
Otherwise, reject.”
Example4:
M = “On input x:
Check that x has the form 0
n1
m2
p
.
If not, reject.
If nm = p, accept.
Otherwise, reject.”

Formal Definition
A TM is a 7-tuple M=(Q,,,,q0,qaccept,qreject), where
Q is a finite set of states
is the input alphabet (does not contain B the blank symbol)
is the tape alphabet, where
(the input alphabet is a subset of the tape alphabet)
B (Blank is in the tape alphabet)
q0 Q is the start state
Qaccept Q is the accepting state
Qreject Q is the rejecting state
: Q × Q × × {L,R} is a partial function. The value of (q,X) is either undefined, or is a triple consisting of the new state,
the replacement symbol, and direction (left/right) for the head motion.

example:
Here is a TM that checks its third symbol is 0,
accepts if so, and runs forever, if not (note it never rejects).
M=({p,q,r,s,t,d},{0,1,},{0,1,B},p,s,d)
(p,X) = (q,X,R) for X=0,1
(q,X) = (r,X,R) for X=0,1
(r,0) = (s,0,L)
(r,1) = (t,1,R)
(t,X) = (t,X,R) for X=0,1,B

A simple program

With the symbols "1 1 0" printed on the tape, let's attempt to convert the 1s to 0s and vice versa. This is called bit inversion, since 1s and 0s are bits in binary. This can be done by passing the following instructions to the Turing machine, utilising the machine's reading capabilities to decide its subsequent operations on its own. These instructions make up a simple program.

Symbol read   Write instruction   Move instruction
Blank   None   None
0   Write 1   Move tape to the right
1   Write 0   Move tape to the right
The machine will first read the symbol under the head, write a new symbol accordingly, then move the tape left or right as instructed, before repeating the read-write-move sequence again.

Let's see what this program does to our tape from the previous end point of the instructions:

A Turing Machine (TM) has three components:
An infinite tape divided into cells. Each cell
contains one symbol.
A head that accesses one cell at a time, and
which can both read from and write on the
tape, and can move both left and right.
A memory that is in one of a fixed finite number
of states.
Instruction set can also be expressed using a State Transition Diagram.
In a State Transition Diagram:

Circle represents a state,
Arrows represent state transitions.
Each arrow also represents one instruction.
Arrow is labeled with: current symbol, new symbol and direction.

construct turing machine:

Construct a TM that accepts the language L of words over alphabet {a,b} that end with an a. More formally, this language is L = {w : w in {a,b}*, w ends with at least one a}. In lexicographical order, L = {a, aa, ba, aaa, aba, baa, bba, aaaa,...}. Your TM should halt in state 99 if and only if wis in L. If w is in not in L,

Write a TM that accepts the language L = {w1w : w in {0}*}. To accept a word the TM

So, in lexicographical order, L = {1, 010, 00100, 0001000, 000010000,...}. Also, note that because the question doesn't specifically ask us not to delete the input, it is OK for us to delete it if we want.

Sample solution (in pseudocode).

On input word w:
1) Remove a 0 from the left end of the word and a 0 from the right end of the word
2) Keep repeating this as long as you can, making the word shorter and shorter
3) If you are left with a single 1, then accept
This sample solution again (this time in TM code). The start state is 00.

#Si,R, Sf, W, M
#--------------
00, 0, 01, _, R # remove a 0 from the left end
01, 0, 01, 0, R # move to end of word
01, 1, 01, 1, R # move to end of word
01, _, 02, _, L # at end of word step left
02, 0, 03, _, L # remove a 0 from the right end
03, 0, 03, 0, L # move back to beginning of word
03, 1, 03, 1, L # move back to beginning of word
03, _, 00, _, R # at beginning of word, start all over again
00, 1, 04, _, R # no more zeros on the left, so check on right
04, _, 99, _, R # no more zeros on right either, so accept

example2:

Example Machine 2.B Write a TM that accepts the language L = {w : w in {0,1}*, |w|>=1, w begins and ends with the same symbol}. In lexicographical order, L = {0, 1, 00, 11, 000, 010, 101, 111, 0000, 0010, 0100, 0110,...}. To accept a word the TM should go into state 99.

Sample solution (in pseudocode).

This sample solution again (this time in TM code). The start state is 00.

#Si,R, Sf, W, M
#--------------
00, 0, 01, 0, R # state 01 means we read a 0
00, 1, 02, 1, R # state 02 means we read a 1
01, 0, 01, 0, R # move to end, remembering we read 0
01, 1, 01, 1, R # move to end, remembering we read 0
01, _, 03, _, L # move to final symbol, remembering we read 0
02, 0, 02, 0, R # move to end, remembering we read 1
02, 1, 02, 1, R # move to end, remembering we read 1
02, _, 04, _, L # move to final symbol, remembering we read 1
03, 0, 99, 0, R # it was the appropriate symbol, so accept
04, 1, 99, 1, R # it was the appropriate symbol, so accept

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.