Final Presentation

PUSHDOWN AUTOMATA

BY SURYA PRAKASH PANDIT 232/05

DEFINITION •

• 4. 5. 6.

The pushdown automata is essentially a finite automata with control of both an input tape and a stack to store what it has read. FORMALISE THE CONCEPT OF PDA :The PDA will have 3 things , An input tape A finite control A stack

FORMAL DEFINITION OF PUSHDOWN AUTOMATA • A pushdown automata is a 6-tuple M= ( Q,Σ, Γ, δ, s, F) where • Q :non-empty finite set of states • Σ :non-empty finite set of input symbols • Γ :is finite set of pushdown symbols • s :is the initial state ,s Є Q • F :is the set of final states and F belongs to Q • δ :It is a transition function or transition relation which maps

• ﴾ QxΣ*xΓ* ﴿ →﴾ QxΓ* ﴿

1: Design a pda for the language L= {wcw R /w:w Є {a,b}*} Solution :Let pushdown automata be P P = (Q,Σ, Γ, δ, s, F) where Q={s ,f } Σ={a,b,c} Γ={a,b} F={f} transition relation δ is defined as follows :(1)((s, a, Є),(s, a)) (2)((s, b, Є),(s, b)) (3)((s, c, Є),(f, Є))

(4) ((f, a, a), (f, Є)) (5) ((f, b, b), (f, Є)) • As PDA reads the first half of its input, it remains in initial state and uses transition 1 and 2 to transfer symbols from the input string on to the pushdown store. • When machine sees a ‘c’ in the input string, it switches from state s to state f without operating on the stack. • Thereafter only transition 4 and 5 are operative; these permit the removal of the top symbol on the stack provided that it is the same as the next input symbol.

The operation of P can be seen by following table, taking string abacaba for example S.No.

State

Unread input

Stack

1 2 3 4 5 6 7 8

s s s s f f f f

abacaba bacaba acaba caba aba ba a Є

Є a ba aba aba ba a Є

Transition 1 2 1 3 4 5 4

2. Design a pda for the regular expression + r=0*1 . Solution :The language for given regular expression is, L= {0 m1n /m ≥0, n ≥1 } Let PDA be P P = (Q,Σ, Γ, δ, s, F) Q = {s, f} F = {f} Σ = {0,1}

•

Transition relations are defined as follows : (2) ((s, 0, Є ), (s, Є )) (3) ((s, 1, Є ), (f, Є )) (4) ((f, 1, Є ), (f, Є )) • Initially machine is at state s when it reads 0’s then it does nothing. • As soon as 1 is encountered then state changes to final state.

3. Design a pda for the language L= { a nb 2n /n>0} Solution : Let PDA be P = (Q,Σ, Γ, δ, S, F) Where Q = (p, q, f, r ) S = {p} F = {f} transition relations are : (1) ((p, a, Є), (p, a)) (2) ((p, a, a), (p, a)) (3) ((p, b, a), (q, b))

(4) ((q, b, ba), (r, Є)) (5) ((r, b, a), (q, ba)) Here two transitions 4 and 5 represent the looping and works on the value of n. (6) ((r, Є, Є), (f, Є)) Example: aaabbbbbb • First, we pushed all the a’s by the help of moves 1 and 2.

• As first b is encountered then it is pushed on the stack by move 3. • When next b is encountered then we pop the ba from the stack and change the state from q to r. • Finally when input becomes empty and stack also becomes empty then state r changes to final state f ,i.e. string is accepted.

4. Design a pda for the regular expression r=0*1* . Solution : Let pushdown automata be P P = (Q,Σ, Γ, δ, s, F) Q = {s, p, r} F = {s, p} Σ = {0,1} Γ = {Є} transition relations δ are defined as : (8) ((s, Є, Є), (s, Є)) (9) ((s, 0, Є), (s, Є))

(3) ((s, 1, Є), (p, Є)) (4) ((p, 1, Є), (p, Є)) (5) ((p, 0, Є), (r, Є)) • First, any number of 0’s can be accepted by move 2. • As soon as 1 is encountered state s is changed to p from s by move 3. • Now any number of 1 can be accepted by the machine with move 4.

5. Design a pda for the language L= {a n b m /n>m≥0} • Solution : Let PDA for the language is P P = (Q,Σ, Γ, δ, S, F) Where Q = {s0,s1,s2,s3,f) S = {s0} F = {f} Σ = {a, b}

(1) (( s0, a, Є), (s1, a)) (2) ((s1, a, a),(s1, a)) (3) ((s1, b, a),(s2, Є)) (4) ((s2, b, a),(s3, Є)) (5) ((s3, b, a),(s2, Є)) (6) ((s2, Є, a),(s2, Є)) (7) ((s2, Є, Є),(f, Є)) (8) ((s1, Є, a),(s1, Є)) (9) ((s1, Є, Є),(f, Є)) Example :aaabb

• Move 1 and 2 provides us to push all the a’s on the stack. • As soon as b is encountered an a is poped up and state is changed to s2, move 4 and 5 are showing loop for poping a’s when b’s are encountered. • Move 6 helps us to empty stack from the a since there is no the input tape. • Finally move 7 makes the string acceptable.