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/21/2019 EECS2001, Summer 2019 1
Next
•Chapter 2:
• Pushdown Automata
6/21/2019 EECS2001, Summer 2019 2
More examples of CFLs
• L(G) = {0n12n | n = 1,2,… }
• L(G) = {xxR | x is a string over {a,b}}
• L(G) = {x | x is a string over {1,0} with an equal number of 1’s and 0’s}
6/21/2019 EECS2001, Summer 2019 3
Next: Pushdown automata (PDA) Add a stack to a Finite Automaton
• Can serve as type of memory or counter
• More powerful than Finite Automata
• Accepts Context-Free Languages (CFLs)
• Unlike FAs, nondeterminism makes a difference for PDAs. We will only study non- deterministic PDAs and omit Sec 2.4 (3rd Ed) on DPDAs.
6/21/2019 EECS2001, Summer 2019 4
Pushdown Automata
Pushdown automata are for context-free languages what finite automata are for regular languages.
PDAs are recognizing automata that have a single stack (= memory):
Last-In First-Out pushing and popping
Non-deterministic PDAs can make non- deterministic choices (like NFA) to find accepting paths of computation.
6/21/2019 EECS2001, Summer 2019 5
Informal Description PDA (1)
input w = 00100100111100101
internal state set Q
The PDA M reads w and stack element. Depending on
– input wi ,
– stack sj , and – state qk Q
the PDA M:
– jumps to a new state, – pushes an element
(nondeterministically)
stack
6/21/2019
EECS2001, Summer 2019 6
x y y z x
Informal Description PDA (2)
input w = 00100100111100101
internal state set Q
After the PDA has read complete input, M will be in state Q
If possible to end in accepting state FQ, then M accepts w
stack
6/21/2019
EECS2001, Summer 2019 7
x y y z x
Formal Description of a PDA
A Pushdown Automata M is defined by a six tuple (Q,,,,q0,F), with
• Q finite set of states
• finite input alphabet
• finite stack alphabet
• q0 start state Q
• F set of accepting states Q • transition function
:Q P(Q)
6/21/2019 EECS2001, Summer 2019 8
PDA for L = { 0n1n | n0 }
Example:
The PDA first pushes “ $ 0n ” on stack. Then, while reading the 1n string, the
zeros are popped again.
If, in the end, $ is left on stack, then “accept”
0, 0 1, 0
1, 0
, $
, $ q3
q1
q
q2
6/21/2019
EECS2001, Summer 2019
9
4
Machine Diagram for 0n1n
0, 0 1, 0
1, 0
, $
, $ q3
q1
q
q2
4
On w = 000111 (state; stack) evolution:
(q1; ) (q2; $) (q2; 0$) (q2; 00$)
(q2; 000$) (q3; 00$) (q3; 0$) (q3; $) (q4; ) This final q4 is an accepting state
6/21/2019 EECS2001, Summer 2019 10
Machine Diagram for 0n1n
0, 0 1, 0
1, 0
, $
, $ q3
q1
q
q2
4
On w = 0101 (state; stack) evolution:
(q1; ) (q2; $) (q2; 0$) (q3; $) (q4; ) … But we still have part of input “01”.
There is no accepting path.
6/21/2019 EECS2001, Summer 2019 11
PDA Conventions 1
• “a, b->c”: PDA reads a from input and replaces b on top of the stack with c
• Anyofa,b,ccanbeε:PDAcanmake a transition without reading a symbol from input (i.e. a = ε) , or without reading/popping stack (i.e. b = ε), or pushing something (i.e. c = ε)
6/21/2019 EECS2001, Summer 2019 12
PDA Conventions 2
• No formal mechanism to detect empty stack
– However one can place a special symbol $, and check for it
• No explicit test for end of input
– However it achieves this effect because accept state takes effect only when machine is at the end of input.
6/21/2019 EECS2001, Summer 2019 13
Formal description (1) Sipser (2nd Ed)
6/21/2019 EECS2001, Summer 2019 14
Formal Description (2)
6/21/2019 EECS2001, Summer 2019 15
Important examples
• Can we have
• L = {aibjak| i=j or i=k }
• Try L = {wwR| w is any binary string }
6/21/2019 EECS2001, Summer 2019 16
Example 2.16 (Sipser 2nd Ed)
6/21/2019 EECS2001, Summer 2019 17
Example 2.18 (Sipser 2nd Ed)
6/21/2019 EECS2001, Summer 2019 18
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/21/2019 EECS2001, Summer 2019 19
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/21/2019 EECS2001, Summer 2019 20
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/21/2019
EECS2001, Summer 2019 21
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/21/2019 EECS2001, Summer 2019 22
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)
Assume
6/21/2019 EECS2001, Summer 2019 23