[SOLVED] theory EECS2001:

EECS2001:
Introduction to Theory of Computation
Summer 2019
Ali Mahmoodi
[email protected]
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 1s and 0s}
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