Progress over Perfection

Turing Machine: Acceptor & Transducer

nikhil

We have studied two types of languages from the Chomsky hierarchy: regular languages and context-free languages. These languages can describe many practically important systems and so they are heavily used in practice. They are, however, of limited capability and there are many languages that they can not process. Here we are going to study the most general of the languages in Chomsky hierarchy, the phrase structure languages (also called Type 0 languages), and the machines that can process them: Turing machines.

Turing_Machine_Model_Davey_2012

Turing machines were invented of by the English mathematician Alan Turing as a model of human “computation”. Later Alonzo Church says that any computation done by humans or computers can be carried out by some Turing machine. This statement is known as Church’s thesis and today it is generally accepted as true. Computers we use today are as powerful as Turing machines except that computers have finite memory while Turing machines have infinite memory.

Turing Machines can be represented using a 7-tuple:

tm00

TM as ACCEPTOR

A Turing machine halts when it no longer has any available moves. If it halts in a final state, it accepts its input; otherwise, it rejects its input.

Turing machine accepts its input if it halts in a final state. There are two ways of rejecting the input string in case of TM:

  1. The Turing machine could halt in a nonfinal state, or
  2. The Turing machine could never stop i.e hang (in which case we say it is in an infinite loop. )

L = {1m | m is odd}

The Transition δ(q0, 1) = δ(q1, 1, R) means Initially q0 will read the input 1 from  Tape, move to state q1,1 is replaced by 1 and read/write head moves to right.

δ(q0, 1) = δ(q1, 1, R)
δ(q1, 1) = δ(q0, 1, R)
δ(q1, β) = δ(qf, β, L/R)

If Blank is reached in q1 state then input string contain odd no. of 1’s. because on reading odd 1’s machine moves to qstate.

L-Odd

L = {0m | m is even}

δ(q0 , 0) = δ(q1 , 0, R)

δ(q1 , 0) = δ(q0 , 0, R)

δ(q0 , β) = δ(qf , β, L/R)
L-Even1

L = {anbn| n > 0}

There is no concept of minimal TM, change state only if needed. Do not think about ∈ in TM.

Strings Accepted by language = {ab, aabb, aaabbb, …}

δ(q0 , a) = (q1 , x, R)

δ(q1 , a) = (q1 , a, R)

δ(q1 , b) = (q2 , y, L)

δ(q2 , a) = (q2 , a, L)

δ(q2 , x) = (q0 , x, R)

δ(q1 , y) = (q1 , y, R)

δ(q2 , y) = (q2 , y, L)

δ(q0 , y) = (q3 , y, R)

δ(q3 , y) = (q3 , y, R)

δ(q3 , β) = (qf , β, R/L)
L-anbn-11

TM as TRANSDUCER

A Turing machine can be used as a transducer. The most obvious way to do this is to treat the entire non-blank portion of the initial tape as input, and to treat the entire non-blank portion of the tape when the machine halts as output.

Qus 1: Design TM to calculate m – n, where m, n are positive integer and m > n.

f(m,n) = m – n

Here suppose m is 5 and n is 3 then we can represent m by 5 o’s and n by 3 o’s. Both m and n are separated by 1.

53 = 2

000001000 = 00

The transition’s for this TM is as below –

δ(q0 , 0) = (q1 , β, R)

δ(q1 , 0) = (q1 , 0, R)

δ(q1 , 1) = (q2 , 1, R)

δ(q2 , 0) = (q2 , 0, R)

δ(q2 , β) = (q3 , β, L)

δ(q3 , 0) = (q4 , β, L)           // when all 0’s are over at q3 , it receive 1 at end.

δ(q4 , 0) = (q4 , 0, L)

δ(q4 , 1) = (q5 , 1, L)

δ(q5 , 0) = (q5 , 0, L)

δ(q5 , β) = (q6 , β, R)

δ(q6 , 0) = (q1 , β, R)         // See Note 1 below

δ(q3 , 1) = (qf , 0, L)

Note 1: Beginning of next cycle for cancellation of 0 by 0. This process continues till all 0’s in n are cancelled by an equal no of 0’s in m. In the next cycle a 0 is cancelled in m but n has no more 0’s so read/write head receives the separator 1 in q3 state and replace it with 0 and enters in final state qf.TM-Ex-2

Qus 2: Design TM to calculate m + n, where m, n are positive integer

f(m,n) = m + n

Here suppose m is 3 and n is 4 then we can represent m by 3 1’s and n by 4 1’s. Both m and n are separated by 0.

3 + 4 = 7

11101111 = 1111111 

The transition’s for this TM is as below –

Logic: When 0 is encountered, it is changed to 1 and last 1 is replaced by β.

δ(q0 , 1) = (q0 , 1, R)

δ(q0 , 1) = (q1 , 1, R)

δ(q1 , 1) = (q1 , 1, R)

δ(q1 , β ) = (q2 , β, L)

δ(q2 , 1) = (qf , β, L)

1 Comment

  1. January 14, 2017    

    Hello, you used to write magnificent, but the last several posts have been kinda boring… I miss your great writings. Past few posts are just a little bit out of track! come on!

Leave a Reply

Your email address will not be published. Required fields are marked *


CAPTCHA Image
Reload Image

Subscribe

May 2015
M T W T F S S
« Apr   Jul »
 123
45678910
11121314151617
18192021222324
25262728293031