1 of 30

Session 1: The Turing Machine Model, Language accepted by Turing machine�Session 2: Design of TM

By

Dr. Ashok Kumar

Amity School of Engineering & Technology

2 of 30

�The Turing Machine Model, Language accepted by Turing machine�

Amity School of Engineering & Technology

3 of 30

Introduction

Turing machine was invented in 1936 by Alan Turing. It is an accepting device which accepts Recursive Enumerable Language generated by type 0 grammar.

There are various features of the Turing machine:
It has an external memory which remembers arbitrary long sequence of input.
It has unlimited memory capability.
The model has a facility by which the input at left or right on the tape can be read easily.
The machine can produce a certain output based on its input. Sometimes it may be required that the same input has to be used to generate the output.

Amity School of Engineering & Technology

4 of 30

The Language Hierarchy

Regular Languages

Context-Free Languages

?

Amity School of Engineering & Technology

5 of 30

Regular Languages

Context-Free Languages

Languages accepted by

Turing Machines

Amity School of Engineering & Technology

6 of 30

Formal Definition

Turing Machine:

States

Input

alphabet

Tape

alphabet

Transition

function

Initial

state

blank

Final

states

Amity School of Engineering & Technology

7 of 30

Transition Function

Amity School of Engineering & Technology

8 of 30

Transition Function

Amity School of Engineering & Technology

9 of 30

A Turing Machine

......

Tape

Read-Write head

Control Unit

Amity School of Engineering & Technology

10 of 30

The Tape

......

Read-Write head

No boundaries -- infinite length

The head moves Left or Right

Amity School of Engineering & Technology

11 of 30

......

Read-Write head

The head at each time step:

1. Reads a symbol

2. Writes a symbol

3. Moves Left or Right

Amity School of Engineering & Technology

12 of 30

......

Example:

Time 0

......

Time 1

1. Reads

2. Writes

3. Moves Left

Amity School of Engineering & Technology

13 of 30

......

Time 1

......

Time 2

1. Reads

2. Writes

3. Moves Right

Amity School of Engineering & Technology

14 of 30

The Input String

......

Blank symbol

head

Head starts at the leftmost position

of the input string

Input string

Amity School of Engineering & Technology

15 of 30

States & Transitions

Read

Write

Move Left

Move Right

Amity School of Engineering & Technology

16 of 30

Example:

......

Time 1

current state

Amity School of Engineering & Technology

17 of 30

......

Time 1

......

Time 2

Amity School of Engineering & Technology

18 of 30

......

Time 1

......

Time 2

Example:

Amity School of Engineering & Technology

19 of 30

Determinism

Allowed

Not Allowed

No lambda transitions allowed

Turing Machines are deterministic

Amity School of Engineering & Technology

20 of 30

Halting

The machine halts if there are

no possible transitions to follow

Amity School of Engineering & Technology

21 of 30

Example:

......

No possible transition

HALT!!!

Amity School of Engineering & Technology

22 of 30

Final States

Allowed

Not Allowed

Final states have no outgoing transitions

In a final state the machine halts

Amity School of Engineering & Technology

23 of 30

Acceptance

Accept Input

If machine halts

in a final state

Reject Input

If machine halts

in a non-final state

or

If machine enters

an infinite loop

Amity School of Engineering & Technology

24 of 30

Turing Machine Example

A Turing machine that accepts the language:

Amity School of Engineering & Technology

25 of 30

Another Turing Machine Example

Turing machine for the language

Amity School of Engineering & Technology

26 of 30

Another Turing Machine Example

Turing machine for the language

q₀

q₁

q₂

q₃

a🡪x, R

a🡪a, R

b🡪y, R

b🡪b, R

c🡪z, L

z🡪z, L

b🡪b, L

y🡪y, L

a🡪a, L

q₄

q₅

y🡪y,R

z🡪z,R

Amity School of Engineering & Technology

27 of 30

Amity School of Engineering & Technology

28 of 30

Amity School of Engineering & Technology

29 of 30

Amity School of Engineering & Technology

30 of 30

Amity School of Engineering & Technology