UNM CS 401 - Pushdown Automaton (8 pages)

Previewing pages 1, 2, 3 of 8 page document View the full content.
View Full Document

Pushdown Automaton



Previewing pages 1, 2, 3 of actual document.

View the full content.
View Full Document
View Full Document

Pushdown Automaton

63 views

Lecture Notes


Pages:
8
School:
University of New Mexico
Course:
Cs 401 - Theoretical Foundations Of Computer Science
Theoretical Foundations Of Computer Science Documents
Unformatted text preview:

Pushdown Automaton PDA A Pushdown Automaton is a nondeterministic finite state automaton NFA that permits transitions and a stack Pushdown Automaton PDA P Q qi a m qk n q0 0 F 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 R L ww w 0 1 PDA Example wwr The language Lwwr is the even length palindromes over alphabet 0 1 Lwwr is a Context Free Language CFL generated by the grammar S 0S 0 1S1 One PDA for Lwwr is given on the following slide PDA for Lwwr P Q q0 0 F Q q0 q1 q2 q3 0 1 0 1 0 F q3 1 q0 0 0 q0 0 0 q0 1 0 q0 1 0 2 q0 0 0 q0 00 q0 0 1 q0 01 q0 1 0 q0 10 q0 1 1 q0 11 3 q0 0 q1 0 q0 0 q1 0 q0 1 q1 1 4 q1 0 0 q1 q1 1 1 q1 5 q1 0 q2 0 6 q2 Read Past End Of Input 0 q3 0 A Graphical Notation for PDA s 1 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 Lwwr 0 0 00 0 1 01 1 0 10 1 1 11 0 0 0 0 1 0 1 0 start q0 0 0 1 1 q1 0 0 1 1 All possibilities that do not have explicit edges have implicit edges that go to an implicit reject state 0 0 q2 EOF 0 0 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 q3 Exercise 1 Design 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 2 Design a PDA to accept the language i j k a b c i j or j k


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

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 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?