Unformatted text preview:

Pushdown Automaton (PDA)Slide 2PDA Example:PDA for LwwrA Graphical Notation for PDA’sGraphical Notation for PDA of LwwrExercise 1Exercise 2Pushdown Automaton (PDA)A Pushdown Automaton is a nondeterministic finite state automaton (NFA) that permits ε-transitions and a stack.Pushdown Automaton (PDA)  FqqaqQPnkmi , , ,),...,(),,( , , ,00Q: A finite set of states. : A finite set of input symbols.: A finite stack alphabet.: The transition function with input:qi is a state in Q.a is a symbol in  or a =  (the empty string).m is a stack symbol, m   and the output is a finite set of pairs:qk the new state.n is the string of stack symbols that replaces m at the top of the stack. If n = , then the stack is popped. q0: The start state.0 : Initially, the PDA’s stack consists this symbol and nothing else.F : The set of accepting states.PDA Example:}1)(0 |{* wwwLRwwrThe language, Lwwr, is the even-length palindromes over alphabet {0,1}.Lwwr is a Context-Free Language (CFL) generated by the grammar:|11|00 SSS One PDA for Lwwr is given on the following slide...PDA for Lwwr)1,(),1,()0,(),0,()100000000qqqq )11,()1,1,()10,()0,1,()01,()1,0,()00,()0,0,()200000000qqqqqqqq)1,()1,,()0,()0,,(),(),,()310100100qqqqqq ),()1,1,(),()0,0,()41111qqqq ),(),,()50201qq ),(),utEnd_Of_InpRead_Past_,()60302qq }{},1,0{}1,0{},,,{303210qFqqqqQ  FqQP , , , , , ,00A Graphical Notation for PDA’s1. The nodes correspond to the states of the PDA.2. An arrow labeled Start indicates the unique start state.3. Doubly circled states are accepting states.4. Edges correspond to transitions in the PDA as follows: 5. An edge labeled (ai, m)/n from state q to state p means that (q, ai, m) contains the pair (p, n), perhaps among other pairs.Graphical Notation for PDA of Lwwrq0q1q2q3start(ε, 0) / 0(ε, ) / (ε, 1) / 1(0,0)/ε(1,1)/ε(ε,0) / 0(EOF,0) / 0All possibilities that do not have explicit edges, have implicit edges that go to an implicit reject state.•This is a nondeterministic machine. •Think of the machine as following all possible paths. •Kill a path if it leads to a reject state. •If any path leads to an accept state, then the machine accepts.(0, 0)/00(0, 1)/01(1, 0)/10(1, 1)/11(0, 0)/00(1, 0)/10Exercise 1Design a PDA that recognizes legal sequences of ‘if’ and ‘else’ statements in a C program.In the PDA, let ‘i’ stands for ‘if’ and ‘e’ stands for ‘else’.Hint: There is a problem whenever the number of ‘else’ statements in any prefix exceeds the number of ‘if’ statements in that prefix.Exercise 2Design a PDA to accept the language:}or |{


View Full Document

UNM CS 401 - Pushdown Automaton

Documents in this Course
Load more
Download Pushdown Automaton
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Pushdown Automaton and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Pushdown Automaton 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?