Lec07 PushdownAutomata

Pushdown Automata
BBM401 Automata Theory and Formal Languages 1

Pushdown Automata
• Pushdown automatons accept exactly context free languages.
• A pushdown automaton (PDA) is essentially an NFA with a stack.

• On a transition, a PDA:
1. Consumes an input symbol (or -transition).
2. Goes to a new state (or stays in the old).
3. Replaces the top of the stack item by any string (does nothing, pops the
stack, or pushes a string onto the stack)

Pushdown Automata – Formal Definition
A pushdown Automata (PDA) is a seven-tuple:
P = (Q,,,,q0,Z0,F),
where
– Q is a finite set of states,
–  is a finite input alphabet,
–  is finite stack alphabet,
– : Q x {} x   2Qx* is the transition function,
– q0 is a start state,
– Z0 is the start symbol for the stack, and
– F is the set of accepting states.

Pushdown Automata – Example
• Consider a CFL Lwwr = { wwr : w∈{0,1}* }
• A pushdown automaton P for the language Lwwr is as follows:
P = ( {q0,q1,q2}, {0,1}, {0,1,Z0} , ,q0 ,Z0, {q2} )

Table Representation of Transition Function
• Consider a CFL Lwwr = { wwr : w∈{0,1}* }
• A pushdown automaton P for the language Lwwr = { wwr : w∈{0,1}* } is as actually a seven
tuple:
P = ( {q0,q1,q2}, {0,1}, {0,1,Z0} , ,q0 ,Z0, {q2} )
where its transition function can be also shown by a table.

A path for the input 0110
State Input Stack Transition

q0 0110 Z0 0, Z0 /0Z0
q0 110 0Z0 1, 0 /10
q0 10 10Z0 , 1 /1
q1 10 10Z0 1, 1 / 
q1 0 0Z0 0, 0 / 
q1  Z0 , Z0 /Z0
q2  Z0

Instantaneous Descriptions (ID) of a PDA
• A PDA goes from configuration to configuration when consuming input.
• The configuration of a PDA is represented by a triple (q,w,) where

1. q is a the state,
2. w is the remaining input, and
3.  is the stack contents
• A configuration triple is called an instantaneous description, or ID, of the

pushdown automaton.

PDA Move - turnstile ⊢ Notation
• We need a notation that describes changes in the state, the input, and stack.
• Let P = (Q,,,,q0,Z0,F) be a PDA. We define a move ⊢ as follows.
• If (p,)(q,a,X) where qQ, a{}, X and *. Then for all strings
w* and *, we have a move (transition):
(q,aw,X) ⊢ (p,w,) )
• This move reflects the idea that, by consuming a (which may be ) from the input and
replacing X on top of the stack by  we can go from state q to state p.
– Note that what remains on the input, w, and what is below the top of the stack,  ,do not
influence the action of the PDA, they are merely carried along.

PDA Moves - turnstile ⊢* Notation
Computation
• To represent a sequence of zero or more moves of the PDA, we use ⊢*.
• A sequence of moves is also called as computation.
BASIS:
I ⊢* I for any ID I.
INDUCTION:
If I ⊢* J if there exists ID K such that I ⊢ K and K ⊢* J.

PDA Move - Example
• On input 1111 the PDA has the following computation sequences:
Arrows represent move ⊢ relation.

PDA Move - Example
• A sequence of moves (a computation):

(q0,1111,Z0) ⊢ (q0,111,1Z0) ⊢ (q0,11,11Z0) ⊢ (q1,11,11Z0) ⊢ (q1,1,1Z0) ⊢ (q1,,Z0) ⊢ (q2,,Z0)
• Thus, (q0,1111,Z0) ⊢* (q2,,Z0)

Actions of Example PDA
• Initial configuration (initial ID): (q0,1111,Z0)
1111
q0
Z0

(q0,1111,Z0) ⊢ (q0,111,1Z0)
1111 111
q0 q0
Z0 1
Z0

(q0,1111,Z0) ⊢ (q0,111,1Z0) ⊢ (q0,11,11Z0)
1111 111 11
q0 q0 q0
Z0 1 1
Z0 1
Z0
(q0,1111,Z0) ⊢ (q0,111,1Z0) ⊢ (q0,11,11Z0)
⊢ (q1,11,11Z0)
1111 111 11 11
q0 q0 q0 q1
Z0 1 1 1
Z0 1 1
Z0 Z0
(q0,1111,Z0) ⊢ (q0,111,1Z0) ⊢ (q0,11,11Z0)
⊢ (q1,11,11Z0) ⊢ (q1,1,1Z0)
1111 111 11 11 1
q0 q0 q0 q1 q1
Z0 1 1 1 1
Z0 1 1 Z0
Z0 Z0
(q0,1111,Z0) ⊢ (q0,111,1Z0) ⊢ (q0,11,11Z0)
⊢ (q1,11,11Z0) ⊢ (q1,1,1Z0) ⊢ (q1,,Z0)
1111 111 11 11 1
q0 q0 q0 q1 q1 q1
Z0 1 1 1 1 Z0
Z0 1 1 Z0
Z0 Z0
(q0,1111,Z0) ⊢ (q0,111,1Z0) ⊢ (q0,11,11Z0)
⊢ (q1,11,11Z0) ⊢ (q1,1,1Z0) ⊢ (q1,,Z0) ⊢ (q2,,Z0)
1111 111 11 11 1
q0 q0 q0 q1 q1 q1 q2
Z0 1 1 1 1 Z0 Z0
Z0 1 1 Z0
Z0 Z0
PDA Move - Example
• On input 01 the PDA has the following computation sequences:
(q0,01,Z0)
(q0,1,0Z0) (q1,01,Z0) (q2,01,Z0)
(q0,,10Z0) (q1,1,0Z0) (q2,1,0Z0)
(q1,,10Z0)
• All computations end with an ID whose state is NOT a final state or the input string is NOT
consumed. Thus, 01 is NOT accepted by this PDA.
– (q1,,10Z0) q1 is NOT a final state, and q1 does not have any move.
– (q2,01,Z0) the input (01) is NOT consumed, and q2 does not have any move.
– (q2,1,0Z0) the input (1) is NOT consumed, and q2 does not have any move.

Languages of PDA

The Languages of a PDA
• In our example, we have assumed that a PDA accepts its input by consuming it
and entering an accepting state.
• This approach is called as "Acceptance By Final State".
• There is a second approach known as "Accepted By Empty Stack".

– The set of strings that cause the PDA to empty its stack, starting from the
initial ID.
• These two methods are equivalent:

– A language L has a PDA A that accepts it by final state if and only if
L has a PDA B that accepts it by empty stack.

Acceptance By Final State
Let P = (Q,,,,q0,Z0,F) be a PDA. Then L(P), the language of P which accepts by

final state, is:
L(P) = { w : (q0,w,Z0) ⊢* (q,,) }
for some state q in F and any stack string .
• Starting in the initial ID with w waiting on the input, P consumes w from the input and
enters an accepting state.
– The contents of the stack at that time is irrelevant.

Acceptance By Empty Stack
Let P = (Q,,,,q0,Z0) be a PDA. Then L(P), the language of P which accepts by

empty stack, is:
L(P) = { w : (q0,w,Z0) ⊢* (q,,) }
for any state q.
• Since final states are irrelevant for PDAs that accept by empty stack, we do not define
final states for those PDAs.
– That is, a PDA that accepts by empty stack is 6 tuple (not 7 tuple).
• L(P) is the set of inputs w that P can consume and at the same time empty its stack.
– Final states are irrelevant.

A PDA Accepts By Empty Stack
• A PDA PN = ({q},{0,1},{P,0,1},,q,P) which accepts by empty stack.
• The language of this PDA is { wwr : w∈{0,1}* }.
,P/0P0
,P/1P1
,P/ 
0,0/ 
1,1/ 
q
• A computation sequence for 0110:

(q,0110,P) ⊢ (q,0110,0P0) ⊢ (q,110,P0) ⊢ (q,110,1P10) ⊢ (q,10,P10) ⊢ (q,10,10)
⊢ (q,0,0) ⊢ (q,,)
• Since there is a computation starts with initial ID and ends with empty stack and empty string
for the string 0110, the string 0110 is recognized by this PDA.
A PDA Accepts By Empty Stack
• A PDA PN = ({q},{0,1},{P,0,1},,q,P) which accepts by empty stack.
• The language of this PDA is { wwr : w∈{0,1}* }.
(q,01,P) (q,01,)
,P/0P0
(q,01,0P0) (q,01,1P1)
,P/1P1
,P/ 
0,0/  (q,1,P0) (q,1,0)
1,1/ 
q (q,1,1P10) (q,1,0P00)
(q,,P10) (q,,10)
(q,,0P010) (q,,1P110)
• Since all computations do NOT end with an ID containing empty stack and empty string, the
string 01 is NOT accepted by this PDA.

Equivalence of Language Definitions
Theorem:
• If L=L(PF) for some PDA PF = (Q,,,,q0,Z0,F) which accepts by final state, then
there exists another PDA PN which accepts by empty stack such that L=L(PN).
• If L=L(PN) for some PDA PN = (Q,,,,q0,Z0) which accepts by empty stack,

then there exists another PDA PF which accepts by final state such that L=L(PF).

Creating an Equivalent PDA Accepting by Empty
Stack from a PDA Accepting by Final State
Proof: We will construct a PDA PN which accepts by empty stack from a given PDA
PF = (Q,,,,q0,Z0,F) which accepts by final state.
• Let PN = (Q∪{p0,e}, , ∪{X0}, N, p0, X0)
– The states of PN will contain two new extra states p0 and e.
• The state p0 is the start state of PN.
• The state e is an erase state which will empty the stack.
– PN will have a new stack symbol X0, and X0 will be the initial stack symbol of PN.
• The new stack symbol X0 is to guard the stack bottom against accidental emptying.
– The transition function N will contain everything in the transition function  of PF and the
following new transitions:
• N(p0,,X0)={(q0,Z0X0)} i.e. The new start state p0 pushes the initial stack symbol Z0 of
PF into the stack and moves to the state q0 which is the start state of PF.
• For any final state f of PF, N(f,,Y)={(e,)} for any stack symbol Y. i.e. A final state of
PF can move to the new erase e state by erasing the top of stack symbol.
• N(e,,Y)={(e,)} i.e. The new erase state e erases all symbols from the stack.
Creating an Equivalent PDA Accepting by Empty
Stack from a PDA Accepting by Final State
Proof (continued):
• From PF = (Q,,,,q0,Z0,F) construct PN = (Q∪{p0,e},,∪{X0},N,p0,X0) as follows:
• Now, we must prove that L(PN)=L(PF).

– If wL(PF) then wL(PN). i.e. if (q0,w,Z0) ⊢∗𝑷𝑭 (f,,) then (p0,w,X0) ⊢∗𝑷𝑵 (e,,)
– If wL(PN) then wL(PF). i.e. if (p0,w,X0) ⊢∗𝑷𝑵 (e,, ) then (q0,w,Z0) ⊢∗𝑷𝑭 (f,,)

From a PDA Accepting by Final State to a PDA
Accepting by Empty Stack : Example

Creating an Equivalent PDA Accepting by Final
State from a PDA Accepting by Empty Stack
Proof: We will construct a PDA PF which accepts by final state from a given PDA
PN = (Q,,,,q0,Z0) which accepts by empty stack.
• Let PF = (Q∪{p0,pf}, , ∪{X0}, F, p0, X0, {pf})
– The states of PF will contain two new extra states p0 and pf.
• The state p0 is the start state of PF.
• The state pf is only final state of PF.
– PF will have a new stack symbol X0, and X0 will be the initial stack symbol of PF.
• The new stack symbol X0 is to guard the stack bottom against accidental emptying.
– The transition function F will contain everything in the transition function  of PN and the
following new transitions:
• F(p0,,X0)={(q0,Z0X0)} i.e. The new start state p0 pushes the initial stack symbol Z0 of
PN into the stack and moves to the state q0 which is the start state of PN.
• For any state q of PN, F(q,,X0)={(pf,)}. i.e. Every state q of PN can move to the new
final state pf when the stack symbol is X0 and erases the top of stack symbol.

Creating an Equivalent PDA Accepting by Final
State from a PDA Accepting by Empty Stack
Proof (continued):
From PN=(Q,,,,q0,Z0) construct PF=(Q∪{p0,pf},,∪{X0},F,p0,X0,{pf}) as follows:
• Now, we must prove that L(PF)=L(PN).

– If wL(PF) then wL(PN). i.e. if (p0,w,X0) ⊢∗𝑷𝑭 (pf,,) then (q0,w,Z0) ⊢∗𝑷𝑵 (q,,) for any q
– If wL(PN) then wL(PF). i.e. if (q0,w,Z0) ⊢∗𝑷𝑵 (q,,) for any q then (p0,w,X0) ⊢∗𝑷𝑭 (pf,,)

From a PDA Accepting by Empty Stack to a PDA
Accepting by Final State : Example
,P/0P0
,P/1P1
,P/ 
0,0/ 
1,1/ 
q
,P/0P0
,P/1P1
,P/ 
0,0/ 
P 1,1/ 
p0 q pf

Equivalence of PDA's and CFG's

Equivalence of PDA's and CFG's
• The following three classes of languages are all the same class.
1. The context-free- languages, i.e.. the languages defined by CFG's.
2. The languages that are accepted by final state by some PDA.
3. The languages that are accepted by empty stack by some PDA.
• We have already shown that (2) and (3) are the same.
• It turns out to be easiest next to show that (1) and (3) are the same, thus Implying the
equivalence of all three.
From Grammars to Pushdown Automata
• Given a CFG G, we construct a PDA that simulates the leftmost derivations of G.
• Any left-sentential form that is not a terminal string can be written as xA, where
– A is the leftmost variable,
– x is whatever terminals appear to the left of A, and
–  is the string of terminals and variables that appear to the right of A.
– If a left-sentential form consists of terminals only, then A is .
• Let xA lm x be a derivation step from the left-sentential form xA.
– This derivation step corresponds to the PDA having consumed x and having A
on the top of the stack, and then the PDA on  it pops A and pushes  into the stack.

PDA Construction from CFG
PDA Construction from CFG:
• Let G = (V, T, R, S) be a CFG.
• Construct the PDA P that accepts L(G) by empty stack as follows:
P = ({q}, T, V∪T, , q, S)
where transition function  is defined by:
1. For each variable A,

(q,,A) = { (q, ) | A   is a production of G }
2. For each terminal a, (q,a,a) = {(q,)}

From CFG to PDA - Example
• Let CFG G = ({P}, {0,1}, {P  0P0, P  1P1, P }, P)
• L(G) is { wwr : w∈{0,1}* }
• We can construct PDA A = ( {q}, {0,1}, {0,1,P}, , q, P) with following transitions.
,P/0P0
,P/1P1 (q,,P) = { (q,0P0), (q,1P1), (q,) }
,P/
0,0/ (q,0,0) = { (q,) }
1,1/
q (q,1,1) = { (q,) }

From CFG to PDA – Example
PDA Moves vs Leftmost Derivations
,P/0P0
P  0P0 ,P/1P1
P  1P1 ,P/
0,0/
P 1,1/
q

(q,0110,P) ⊢ (q,0110,0P0) ⊢ (q,110,P0)
• A leftmost derivation sequence of 0111:

P  0P0

,P/0P0
P  0P0 ,P/1P1
P  1P1 ,P/
0,0/
P 1,1/
q

(q,0110,P) ⊢ (q,0110,0P0) ⊢ (q,110,P0) ⊢ (q,110,1P10) ⊢ (q,10,P10)

P  0P0  01P10

,P/0P0
P  0P0 ,P/1P1
P  1P1 ,P/
0,0/
P 1,1/
q

(q,0110,P) ⊢ (q,0110,0P0) ⊢ (q,110,P0) ⊢ (q,110,1P10) ⊢ (q,10,P10)
⊢ (q,10,10) ⊢ (q,0,0) ⊢ (q,,)

P  0P0  01P10  0110

Theorem: If PDA P is constructed from CFG G by the construction algorithm
then L(P) = L(G).
Proof:
• We have to show that (q,w,S) ⊢* (q,,) if and only if S ⇒* w
• We need to prove something more general:
– We need to show that (q,wx,S) ⊢* (q,x,) for any x if and only if S ⇒*lm w
– After this proof, we can let x== 
• Then (q,w,S) ⊢* (q,,) if and only if S ⇒* w
• That is, w is in L(P) if and only if w is in L(G).

Proof (Only-If Part):
– Suppose (q,wx,S) ⊢* (q,x,) for any x.
– We have to show that S ⇒*lm w
– Proof is an induction on the number steps made by P
Basis: 0 steps
• Then =S, w=, and S ⇒*lm S is surely true.
Induction:
• Consider n moves of P: (q,wx,S) ⊢* (q,x,) and assume the IH for sequences of
n-1 moves.
• There are two cases, depending on whether the last move uses a terminal or a variable
on the top of stack.

Induction (cont.):
Case 1: The move sequence must be of the form (q,yax,S) ⊢* (q,ax,a) ⊢ (q,x,),
where ya = w.
• By the IH applied to the first n-1 steps, S ⇒*lm ya.
• But ya = w, so S ⇒*lm w.
Case 2: The move sequence must be of the form (q,wx,S) ⊢* (q,x,A) ⊢ (q,x,),
where A   is a production and  = .
• By the IH applied to the first n-1 steps, S ⇒*lm wA.
• Thus, S ⇒*lm w = w.

Proof (If Part):
– Suppose S ⇒*lm w
– We have to show that (q,wx,S) ⊢* (q,x,) for any x.
– Proof is an induction on the length of the leftmost derivation.
• The proof is similar to Only-If part proof and it is in the book.

From a PDA Accepting with Empty Stack to a CFG
• Assume we have a PDA P=(Q,,,,q0,Z0) which accepts with empty stack.
• We’ll construct a CFG G such that L(P) = L(G).
• Intuition:
– G will have variables generating exactly the inputs that cause P to have the net
effect of popping a stack symbol X while going from state p to state q.
– P never gets below this X while doing so.

From a PDA to a CFG
Construct a CFG G=(V,T,R,S) from PDA P=(Q,,,,q0,Z0) such that L(P) = L(G).
Variables of G:
• G’s variables are of the form [pXq] where p∊Q, q∊Q, X∊,
– The variable [pXq] generates all and only the strings w such that
(p,w,X) ⊢* (q,,).
• In addition, G will also have a start symbol S.
• Thus, V = { [pXq] : p∊Q, q∊Q, X∊} ∪ {S}

From a PDA to a CFG
Construct a CFG G=(V,T,R,S) from PDA P=(Q,,,,q0,Z0) such that L(P) = L(G).
Productions of G:
• Each production for [pXq] comes from a move of P in state p with stack symbol X.
CASE 1: δ(p,a,X) contains (q,ε).

• G has the production [pXq]  a where a∊∪{ε}.
– [pXq] generates a, because reading a is one way to pop X and go from p to q.
CASE 2: δ(p,a,X) contains (r,Y) for some state r and a stack symbol Y.
• For each state q∊Q, G has the production [pXq]  a[rYq] where a∊∪{ε}.
– We can erase X and go from p to q by reading a (entering state r and replacing X by Y)
and then reading some w that gets P from r to q while erasing Y.
– Note: [pXq] ⇒* aw whenever [rYq] ⇒* w.

From a PDA to a CFG
Productions of G:
GENERAL CASE: δ(p,a,X) contains (r,Y1…Yk) for some state r and k2.
• Generate a family of productions (For all states q, s1, …, sk-1)
[pXq]  a [rY1s1] [s1Y2s2] … [sk-2Yk-1sk-2] [sk-1Ykq]
When k=2: δ(p,a,X) contains (r,YZ) for some state r

– Now, P has replaced X by YZ.
– To have the net effect of erasing X, P must erase Y, going from state r to some state s, and
then erase Z, going from s to q.
– Since we do not know state s, we must generate a family of productions:
[pXq]  a[rYs][sZq] for all states s.
– Note: [pXq] ⇒* awx whenever [rYs] ⇒* w and [sZq] ⇒* x.

From a PDA to a CFG
Completion of the Construction:
• We can prove that (q0,w,Z0) ⊢* (p,ε,ε) if and only if [q0Z0p] ⇒* w.
• But state p can be anything.
• Thus, add productions S  [q0Z0p] for each state p.

From a PDA to a CFG: Example
• Convert the PDA P=({p,q},{0,1},{X,Z0},,q,Z0) where  is given by:
• We get G=({[pXp],[pXq],[pZ0p],[pZ0q], [qXp],[qXq],[qZ0p],[qZ0q],S}, {0,1}, R, S)

From a PDA to a CFG: Example
G=({[pXp],[pXq],[pZ0p],[pZ0q], [qXp],[qXq],[qZ0p],[qZ0q], S}, {0,1}, R, S)
and productions in R are:
From
δ(p,a,X) contains (r,Y)
[pXq] --> a[rYq]
From
From
δ(p,a,X) contains (r,YZ)
[pXq] --> a[rYs][sZq]

From
From
From

Deterministic Pushdown Automata
(DPDA)

Deterministic Pushdown Automata (DPDA)
• While PDA's are by definition allowed to be nondeterministic, the deterministic
subcase is quite important.
• In particular, parsers generally behave like deterministic PDA's, so the class of
languages that can be accepted by these automata is interesting for the insights it gives
us into what constructs are suitable for use in programming languages.
A PDA P = (Q,,,,q0,Z0,F) is deterministic iff

1. (q,a,X) is always empty or a singleton where a, or a is .
2. If (q,a,X) is nonempty where a, then (q,,X) must be empty.

DPDA - Example
L = { wcwR : w∊{0,1}* }
• L is recognized by the following DPDA:

DPDA Properties
If L is a regular language, then L = L(P) for some DPDA P.
– regular languages  languages of DPDAs
There are languages that are not regular, but there are DPDAs for them.
– { wcwR : w∊{0,1}* } is a member of languages of DPDAs but it is not regular.
There are context free languages which are NOT members of languages of DPDAs.
– { wwR : w∊{0,1}* } is NOT a member of languages of DPDAs. i.e. there is NO
DPDA for the language { wwR : w∊{0,1}* }.
– languages of DPDAs  context free languages

DPDA Properties
There are NO DPDAs for inherently ambiguous CFLs.
For a given unambiguous grammar we may NOT find a DPDA.

– { wwR : w∊{0,1}* } has unambiguous grammar S  0S0 | 1S1 | 
– But { wwR : w∊{0,1}* } is NOT a member of languages of DPDAs.
We can always find an unambiguous grammar for the language of a given DPDA.
– The languages of DPDAs are equal to languages of deterministic context free
grammars.
– Each LR(k) grammar is an unambiguous grammar, but not all unambiguous
grammars are LR(k) grammars.
– The languages of LR(k) grammars (k1) are equal to languages of deterministic context
free grammars (languages of DPDAs).
– LR(k) grammars are widely used in the parsing of programming languages (LR parsers).

Formal Languages -- So far
Context Free Languages
Languages of unambiguous CFGs
Languages of DPDAs
Regular Languages

Lec07 PushdownAutomata

Uploaded by

Copyright:

Available Formats

Lec07 PushdownAutomata

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lec07 PushdownAutomata

Uploaded by

Copyright:

Available Formats

Pushdown Automata

BBM401 Automata Theory and Formal Languages 1

• A pushdown automaton (PDA) is essentially an NFA with a stack.

BBM401 Automata Theory and Formal Languages 2

BBM401 Automata Theory and Formal Languages 3

BBM401 Automata Theory and Formal Languages 4

where its transition function can be also shown by a table.

BBM401 Automata Theory and Formal Languages 5

State Input Stack Transition

BBM401 Automata Theory and Formal Languages 6

• The configuration of a PDA is represented by a triple (q,w,) where

• A configuration triple is called an instantaneous description, or ID, of the

BBM401 Automata Theory and Formal Languages 7

BBM401 Automata Theory and Formal Languages 8

BBM401 Automata Theory and Formal Languages 9

BBM401 Automata Theory and Formal Languages 10

• A sequence of moves (a computation):

BBM401 Automata Theory and Formal Languages 11

BBM401 Automata Theory and Formal Languages 12

BBM401 Automata Theory and Formal Languages 13

(q0,1,0Z0) (q1,01,Z0) (q2,01,Z0)

(q0,,10Z0) (q1,1,0Z0) (q2,1,0Z0)

BBM401 Automata Theory and Formal Languages 19

BBM401 Automata Theory and Formal Languages 20

• There is a second approach known as "Accepted By Empty Stack".

• These two methods are equivalent:

BBM401 Automata Theory and Formal Languages 21

Let P = (Q,,,,q0,Z0,F) be a PDA. Then L(P), the language of P which accepts by

BBM401 Automata Theory and Formal Languages 22

Let P = (Q,,,,q0,Z0) be a PDA. Then L(P), the language of P which accepts by

BBM401 Automata Theory and Formal Languages 23

• A computation sequence for 0110:

BBM401 Automata Theory and Formal Languages 25

• If L=L(PN) for some PDA PN = (Q,,,,q0,Z0) which accepts by empty stack,

BBM401 Automata Theory and Formal Languages 26

• Now, we must prove that L(PN)=L(PF).

BBM401 Automata Theory and Formal Languages 28

BBM401 Automata Theory and Formal Languages 29

BBM401 Automata Theory and Formal Languages 30

• Now, we must prove that L(PF)=L(PN).

BBM401 Automata Theory and Formal Languages 31

BBM401 Automata Theory and Formal Languages 32

BBM401 Automata Theory and Formal Languages 33

BBM401 Automata Theory and Formal Languages 35

where transition function  is defined by:

1. For each variable A,

2. For each terminal a, (q,a,a) = {(q,)}

BBM401 Automata Theory and Formal Languages 36

• We can construct PDA A = ( {q}, {0,1}, {0,1,P}, , q, P) with following transitions.

BBM401 Automata Theory and Formal Languages 37

• A computation sequence for 0110:

• A leftmost derivation sequence of 0111:

BBM401 Automata Theory and Formal Languages 38

• A computation sequence for 0110:

• A leftmost derivation sequence of 0111:

BBM401 Automata Theory and Formal Languages 39

• A computation sequence for 0110:

• A leftmost derivation sequence of 0111: