COSC 3340: Introduction to Theory of Computation University of Houston Dr. Verma Lecture 14 1 Lecture 14 UofH - COSC 3340 - Dr. Verma PDAs and CFGs

For every CFG G there is a PDA M such that L(G) = L(M) For every PDA M there is a CFG G such that L(M) = L(G) 2 Lecture 14 UofH - COSC 3340 - Dr. Verma

CFG PDA Given CFG G = (V, , R, S) Let PDA M = (Q, , V {$}, , qstart, {qaccept}) contains transitions for the form 1. 2.

3. 4. 3 Q = {qstart, qloop,qaccept} , S$ ((qstart,, ), (qloop, S$)) For each rule A w R(G) there is a transition ((qloop,, A),(qloop, w)) ***

For each symbol ((qloop, , ), (qloop, )) , $ ((qloop,, $), (qaccept, )) Lecture 14 qstart qloop , , A w

qaccept UofH - COSC 3340 - Dr. Verma CFG PDA 1. 2. The PDA simulates a leftmost derivation of the string. Place the marker symbol $ and the start variable on the stack. Repeat the following steps forever (a) If the top of stack is a variable symbol A, nondeterministically

select on of the rules for A and substitute A by the string on the right-hand side of the rule. (b) If the top of stack is terminal symbol , read the next symbol from the input and compare it to . If they match, repeat. If they do not match, reject on this branch of the nondeterminism. (c) If the top of stack is the symbol $, enter the accept state. Doing so accepts the input if it has all been read. 4 Lecture 14 UofH - COSC 3340 - Dr. Verma

Example: S aSb | Z is used instead of $ Instead of q0 = qstart q1 = qloop q2 = qaccept 5 Lecture 14

UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 6 Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION

7 Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 8 Lecture 14 UofH - COSC 3340 - Dr. Verma

JFLAP SIMULATION 9 Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 10

Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 11 Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION

12 Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 13 Lecture 14

UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 14 Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 15

Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 16 Lecture 14 UofH - COSC 3340 - Dr. Verma

JFLAP SIMULATION 17 Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 18 Lecture 14

UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 19 Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION

20 Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 21 Lecture 14 UofH - COSC 3340 - Dr. Verma

JFLAP SIMULATION 22 Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 23

Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 24 Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION

25 Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 26 Lecture 14

UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 27 Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 28

Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 29 Lecture 14 UofH - COSC 3340 - Dr. Verma

JFLAP SIMULATION 30 Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 31 Lecture 14

UofH - COSC 3340 - Dr. Verma Idea of PDA CFG First, we simplify our task by modifying P slightly to give it the following three features 1. It has a single accept state, qaccept. 2.

It empties its stack before accepting. Each transition either pushes a symbol onto the stack (a push move) or pops one off the stack (a pop move), but does not do both at the same time. 3. 32 Lecture 14

UofH - COSC 3340 - Dr. Verma PDA CFG Suppose P = {Q, , , , q0, {qaccept}} to construct G. The variables of G are {Apq | p, q Q}. Apq generates all the strings that can take P from p with an empty stack to q with an empty stack. Two possibilities occur during Ps computation on x.

Either the symbol popped at the end is the symbol pushed at the beginning or not. First, simulated by Type 1 rules on next slide and the second by Type 2 rules. 33 Lecture 14 UofH - COSC 3340 - Dr. Verma

PDA CFG The start variable is Aq0qaccept. Now we describe Gs rules. 34 [Type 1] For each p, q, r, s Q, t , and a, b , if ((p, a, ), (r, t)) is in and ((s, b, t), (q, )) is in , put

the rule Apq aArsb in G. In other words, find pairs of transitions in the PDA such that the first transition in the pair pushes a symbol t and the second transition pops the same symbol t. Each such pair of transitions gives a Type 1 rule. The states p, q, r, s, and the symbols a, b are determined by looking at the transitions in the pair. Lecture 14 UofH - COSC 3340 - Dr. Verma PDA CFG

35 [Type 2] For each p, q, r Q put the rule Apq AprArq in G. [Type 3] Finally, for each p Q put the rule App in G. Lecture 14

UofH - COSC 3340 - Dr. Verma Example Let M be the PDA for {anbn | n > 0} Note that n cannot be 0, which makes the example a little simpler. M = {{p, q}, {a, b}, {a}, , p, {q}}, where = {((p, a, ),(p, a)),((p, b, a), (q, )),((q, b, a),(q, ))}

p 36 q Lecture 14 UofH - COSC 3340 - Dr. Verma Example: contd.

CFG, G = (V, {a, b}, Apq, R) corresponding to M has V = {App, Apq, Aqp, Aqq}. R contains the following rules: Type I: Type II:

We can discard all rules containing the variables Aqq and Aqp. And we can also simplify the rules containing App and get the grammar with just two rules Apq ab and Apq aApqb. App App App | Apq Aqp

Apq App Apq | Apq Aqq Aqp Aqp App | Aqq Aqp Aqq Aqp Apq | Aqq Aqq Type III: 37 Apq aAppb Apq aApqb

App Aqq Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 38 Lecture 14 UofH - COSC 3340 - Dr. Verma

JFLAP SIMULATION 39 Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 40

Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 41 Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION

42 Lecture 14 UofH - COSC 3340 - Dr. Verma JFLAP SIMULATION 43 Lecture 14

UofH - COSC 3340 - Dr. Verma