pushdown automation and turing machine PDF

Preview

Summary

this document covers concepts of pushdowm automation and turing machine with their formal description, abstract model, various examples and applications....

Description

PUSHDOWM AUTOMATION A pushdown automaton is similar to finite automata but with an extra memory called stack. It is the automation corresponding to context free grammar (type 1). The stack or pushdown store helps PDA to recognize context free languages. Abstract model of PDA

Pushdown automation contains 1. 2. 3. 4.

Input tape of finite length Read only head which is unidirectional Finite state control(FSC) A stack of infinite size

FORMAL DEFINITION OF PDA

Applications of PDA 1. 2. 3. 4.

Compiler design Tower of Hanoi Online transaction processing system Context free languages(CFL)

PDA for {anbn |n>=0}

Examples of accepted strings: ab, aabb, aaabbb, aaaabbbb…and so on Examples of rejected strings: aab, aab,bbaa,abab etc.

PDA for language L = {wcw’ | w={a, b}*} where w’ is the reverse of w.

Examples of the string accepted: aabbcbbaa, ababacababa,abaabcbaaba etc

PDA FOR

L ={wϵ {a,b}*| w contains equal no. of a’s and b’s}

Examples of strings accepted: ab, aabb, abba, aababb, bbabaa, baaababb, .......

TURING MACHINE Turing Machine was invented by Alan Turing in 1936 and it is used to accept Recursive Enumerable Languages generated by unrestricted (type 0) Grammar. A turing machine consists of an infinite memory tape divided into discrete cells. Read and write operations can be performed on the tape using read/write head which points to cell currently being read and can move in both directions left and right(bidirectional).

A TM can be formally described as a 7-tuple where,

Turing machine for anbn | n ≥ 1 1. APPROACH: 1) 2) 3) 4) 5)

Mark 'a' as ‘x’ then move right. Mark 'b' as ‘y’ then move left. Come to far left till we get 'x’. Repeat above steps till all 'a' and 'b' are marked. At last if everything is marked that means string is accepted. Example for string “aabb”:

2-TRANSITION DIAGRAM:

3-STEPS:

5-TRANSITION TABLE:

Turing machine for anbncn | n ≥ 1 1. APPROACH: 1. 2. 3. 4. 5. 6.

Mark 'a' as ‘x’ then move right. Mark 'b' as ‘y’ then move right Mark 'c' as ‘z’ then move left Come to far left till we get 'X' Repeat above steps till all 'a', 'b' and 'c' are marked At last if everything is marked that means string is accepted. Example for string “aaabbbccc”:

2- TRANSITION DIAGRAM:

3- TRANSITION STEPS:

4-TRANSITION TABLE:...