Push down automata

1. PUSH DOWN AUTOMATA

2. WHY PDA ? DFAs accept regular languages. We want to design machines similar to DFAs that will accept context-free languages and is regular. A finite automation cannot accept string of the form ( a^n,b^n ) as it has to remember the no. of a’s and so requires infinite no. of states.

3. POWERS OF PDA This difficulty is avoided by adding a auxiliary memory in form of stack. It has a read only input tape and input alphabet. Final state control Set of final states Initial state (as in FA) Read write push down store.

4. PDA MODEL

5. FORMAL DEFINATION Finite nonempty set of states Q. Finite non empty set of input symbols denoted by Finite non empty set of pushdown store Initial state q0. Initial symbol of push down store Z0. Set of final state  a transition function . A PDA IS A 7 TUPLE , NAMELY

6. FORMAL DEFINATION OF CFG A context-free grammar G is a 4-tuple (V,  , R, S), where:  V is a finite set; each element v  V  is called  a non-terminal character  or a  variable.  is a finite set of  terminal s, disjoint from , which make up the actual content of the sentence. R is a finite relation from V  to (V U )* . S, the start symbol , used to represent the whole sentence (or program). It must be an element of  V.

7. FORMAL CONTRUCTION Let G = (V, T,R, S) be a CFG. The PDA P = ({q}, T, V ∪ T, δ, q, S) where the δ is defined as follows: For each variable A, R1: δ(q, ǫ,A ) = {(q, β) | A → β is a production of R} For each terminal a R2: δ(q, a, a) = {(q, ǫ)} * Ǫ DENOTES NULL

8. PROJECT CONTRUCT PDA EQUIVALENT TO FOLLOWING GRAMMAR WITH PRODUCTIONS. S -> a A A S -> a S A -> b S A -> a Convert to PDA using LL. Show simulations

9. Step 1: Select GRAMMAR

10. STEP 2:Write the productions STEP 3 : Covert ->PDA ( LL)

11. OUTPUT :

12. Construct CFG TO PDA We define PDA A as is defined by following rules:

13. TEST FOR STRING ‘ aabaaa ’

14. THANK YOU