EECS2001:
Introduction to Theory of Computation
Summer 2019
Ali Mahmoodi
amahmoodi@cse.yorku.ca
Office: Lassonde 2015 Course page: Moodle
Notes based on work by Professor Suprakash Datta
6/26/2019 EECS2001, Summer 2019 1
Additional Notes
•Chapter 2:
• Equivalence of CFG and PDA
6/26/2019 EECS2001, Summer 2019 2
PDAs and CFL
Theorem 2.20 (2.12 in 2nd Ed):
A language L is context-free if and only if there is a pushdown automata M that recognizes L.
Two step proof:
1) Given a CFG G, construct a PDA MG 2) Given a PDAM, make a CFG GM
6/26/2019 EECS2001, Summer 2019 3
Converting a CFL to a PDA
• Lemma 2.21 in 3rd Ed
• The PDA should simulate the derivation of a word in the CFG and accept if there is a derivation.
• Need to store intermediate strings of terminals and variables. How?
6/26/2019 EECS2001, Summer 2019 4
1. 2.
Informal description PDA
Place marker $ and start variable on stack
Repeat forever
a) If top of stack is variable A, non-deterministically select a rule for A and substitute A by right hand side
b) If top of stack is terminal a, read the next symbol from the input and compare to a. Repeat if there is a match and reject for this branch otherwise
c) If top of stack is $, enter accept state. It will accept input if all has been read
6/26/2019
EECS2001, Summer 2019 5
More of CFG to PDA
• Convention
6/26/2019 EECS2001, Summer 2019 6
CFG to PDA conversion
• P has three states 𝑞𝑠𝑡𝑎𝑟𝑡 , 𝑞𝑙𝑜𝑜𝑝 , 𝑞𝑎𝑐𝑐𝑒𝑝𝑡 plus others needed to implement the shorthand
6/26/2019 EECS2001, Summer 2019
7
Example (Sipser 2nd Ed)
• Example 2.25: convert the following CFG to a PDA
6/26/2019 EECS2001, Summer 2019 8
Construction for
6/26/2019 EECS2001, Summer 2019 9
Converting a PDA to a CFG
• Lemma 2.27 in 3rd Ed
• Design a grammar equivalent to a PDA
• Idea: For each pair of states p,q we have a variable Apq that generates all strings that take the automaton from p to q (empty stack to empty stack).
6/26/2019 EECS2001, Summer 2019 10
Assume
Some details
– Single accept state
– Stack emptied before accepting
– Each transition either pops or pushes a symbol
• Can create rules for all the possible cases (p 122 in 3rd Ed)
6/26/2019 EECS2001, Summer 2019 11
PDA to CFG conversion (1)
6/26/2019 EECS2001, Summer 2019 12
PDA to CFG (2)
6/26/2019 EECS2001, Summer 2019 13
PDA to CFG (3)
6/26/2019 EECS2001, Summer 2019 14