Unit 4 | unit 4 push down automata

TOC

Unit - 4

Push Down Automata

Q1) Introduce PDA?

A1) It is a way to implement a context-free grammar as we design DFA for a regular grammar. A DFA can remember a finite amount of information, but a PDA can remember an infinite amount of information.

Basically a pushdown automaton is -

“Finite state machine” + “a stack”

A pushdown automaton has three components −

● an input tape,

● a control unit, and

● a stack with infinite size.

The stack head scans the top symbol of the stack.

A stack does two operations −

● Push − a new symbol is added at the top.

● Pop − the top symbol is read and removed.

A PDA may or may not read an input symbol, but it has to read the top of the stack in every transition.

Fig1: Basic structure of PDA

A PDA can be formally described as a 7-tuple (Q, ∑, S, δ, q 0 , I, F) −

Where,

● Q is the finite number of states

● ∑ is input alphabet

● S is stack symbols

● δ is the transition function: Q × (∑ ∪ {ε}) × S × Q × S* )

● q 0 is the initial state (q 0 ∈ Q)

● I is the initial stack top symbol (I ∈ S)

● F is a set of accepting states (F ∈ Q)

The following diagram shows a transition in a PDA from a state q 1 to state q 2 , labeled as a,b → c −

Fig 2: Example

This means at state q1, if we encounter an input string ‘a’ and the top symbol of the stack is ‘b’, then we pop ‘b’, push ‘c’ on top of the stack and move to state q2 .

Q2) What is a non - deterministic pushdown automata?

A2) The non-deterministic pushdown automata is very much similar to NFA. We will discuss some CFGs which accept NPDA.

The CFG which accepts deterministic PDA accepts non-deterministic PDAs as well.

Similarly, there are some CFGs which can be accepted only by NPDA and not by DPDA. Thus NPDA is more powerful than DPDA.

● Non-deterministic pushdown automata are quite similar to the NFA.

● Non-deterministic PDAs are also approved by the CFG that accepts deterministic PDAs.

● Similarly, there are several CFGs that only NPDA and not DPDA can consider. Therefore, NPDA is more efficient than DPDA.

● Non deterministic pushdown automata is basically a non finite automata (nfa) with a stack added to it.

Nondeterministic pushdown automaton or npda is a 7-tuple -

M = (Q, ∑, T, δ , q0, z, F)

Where

● Q is a finite set of states,

● ∑ is a the input alphabet,

● T is the stack alphabet,

● δ is a transition function,

● q0 ∈ Q is the initial state,

● z ∈ T is the stack start symbol, and

● F ⊆ Q is a set of final states.

Moves

The three groups of loop transitions in state q represent these respective functions:

● input a with no b’s on the stack: push a

● input b with no a’;s on the stack: push b

● input a with b’s on the stack: pop b; or, input b with a’s on the stack: pop a

For example if we have seen 5 b’s and 3 a’s in any order, then the stack should be “bbc”. The transition to the final state represents the only non-determinism in the PDA in that it must guess when the input is empty in order to pop off the stack bottom.

Q3) Design PDA for Palindrome strips?

A3) Suppose the language consists of string L = {aba, aa, bb, bab, bbabb, aabaa, ......].

The string can be odd palindrome or even palindrome. The logic for constructing PDA is that we will push a symbol onto the stack till half of the string then we will read each symbol and then perform the pop operation. We will compare to see whether the symbol which is popped is similar to the symbol which is read. Whether we reach the end of the input, we expect the stack to be empty.

This PDA is a non-deterministic PDA because finding the mid for the given string and reading the string from left and matching it with from right (reverse) direction leads to non-deterministic moves.

Here is the ID.

Simulation of abaaba

1. δ(q1, abaaba, Z) Apply rule 1

2. δ(q1, baaba, aZ) Apply rule 5

3. δ(q1, aaba, baZ) Apply rule 4

4. δ(q1, aba, abaZ) Apply rule 7

5. δ(q2, ba, baZ) Apply rule 8

6. δ(q2, a, aZ) Apply rule 7

7. δ(q2, ε, Z) Apply rule 11

8. δ(q2, ε) Accept

Q4) What is acceptance by final state?

A4) Acceptance by final state

When a PDA accepts a string in final state acceptability, the PDA is in a final state after reading the full string. We can make moves from the starting state to a final state with any stack values. As long as we end up in a final state, the stack values don't matter.

If the PDA enters any final state in zero or more moves after receiving the complete input, it is said to accept it by the final state.

Let P =(Q, ∑, Γ, δ, q0, Z, F) be a PDA. The language acceptable by the final state can be defined as:

L(PDA) = {w | (q0, w, Z) ⊢* (p, ε, ε), q ∈ F}

Q5) Write about acceptance by empty stack?

A5) Acceptance by empty stack

The stack of PDAs becomes empty after reading the input string from the initial setup for some PDA.

When a PDA has exhausted its stack after reading the entire string, it accepts a string.

Let P =(Q, ∑, Γ, δ, q0, Z, F) be a PDA. The language acceptable by empty stack can be defined as:

N(PDA) = {w | (q0, w, Z) ⊢* (p, ε, ε), q ∈ Q}

Q6) Construct a PDA that accepts L = {0n 1n | n ≥ 0}

A6)

This language accepts L = {ε, 01, 0011, 000111, ............................. }

The number of ‘a' and ‘b' in this example must be the same.

● We began by inserting the special symbol ‘$' into the empty stack.

● If we encounter input 0 and top is Null at state q2, we push 0 into the stack. It's possible that this will happen again. We pop this 0 if we meet input 1 and top is 0.

● If we encounter input 1 at state q3 and the top is 0, we pop this 0. It's possible that this will continue to iterate. We pop the top element if we meet input 1 and top is 0.

● If the special symbol '$' appears at the top of the stack, it is popped out, and the stack eventually moves to the accepting state q4.

Q7) Write Algorithm to find the PDA corresponding to a given CFG?

A7) Input − A CFG, G = (V, T, P, S)

Output − Equivalent PDA, P = (Q, ∑, S, δ, q0, I, F)

Step1 - Convert the CFG's productions into GNF.

Step2 - There will be only one state q on the PDA.

Step3 - The CFG's start symbol will be the PDA's start sign.

Step4 - The PDA's stack symbols will be all of the CFG's non-terminals, and the PDA's input symbols will be all of the CFG's terminals.

Step5 - For each production in the form A → aX where a is terminal and A, X are a combination of terminal and non-terminals, make a transition δ (q, a, A).

Problem

Construct a PDA using the CFG below.

G = ({S, X}, {a, b}, P, S)

Where are the productions?

S → XS | ε , A → aXb | Ab | ab

Solution

Let's say you have a PDA that's equivalent to that.

P = ({q}, {a, b}, {a, b, X, S}, δ, q, S)

Where δ −

δ(q, ε , S) = {(q, XS), (q, ε )}

δ(q, ε , X) = {(q, aXb), (q, Xb), (q, ab)}

δ(q, a, a) = {(q, ε )}

δ(q, 1, 1) = {(q, ε )}

Q8) Write Algorithm to find CFG corresponding to a given PDA?

A8) Input − A CFG, G = (V, T, P, S)

Output − Equivalent PDA, P = (Q, ∑, S, δ, q0, I, F) such that the non- terminals of the grammar G will be {Xwx | w,x ∈ Q} and the start state will be Aq0,F.

Step1 − For every w, x, y, z ∈ Q, m ∈ S and a, b ∈ ∑, if δ (w, a, ε) contains (y, m) and (z, b, m) contains (x, ε), add the production rule Xwx → a Xyzb in grammar G.

Step2 − For every w, x, y, z ∈ Q, add the production rule Xwx → XwyXyx in grammar G.

Step3 − For w ∈ Q, add the production rule Xww → ε in grammar G.

Q9) Write the Equivalence of PDA and CFG?

A9) The power of a CFG and a PDA is the same: a CFG generates context-free language, while a PDA recognizes context-free language.

We demonstrate how to transform a CFG into a PDA that recognizes the CFG's language and vice versa.

Application: Because of this equivalence, a CFG can be used to specify a programming language, and the equivalent PDA can be used to construct the language's compiler.

Theorem: If a pushdown automaton recognizes a language, it is context-free.

This means that:

1. If a language L is context-free, it is recognized by a PDA ML.

2. If a PDA ML recognizes a language L, there is a CFG GL that generates L.

Lemma: If a language is context-free, it will be recognized by a pushdown automaton.

Proof concept:

1. Let's A pretend to be a CFL. We know from the definition that A has a CFG G that it generates.

2. We'll demonstrate how to transform G, PDA P into one that accepts strings ພ if G it creates ພ.

3. P will start by figuring out a derivation ພ.

Q10) Write the difference between PDA and CFL?

A10) Difference between PDA and CFL

Q11) Convert the following grammar to a PDA that accepts the same language.

S → 0S1 | A and A → 1A0 | S | ε

A11) The CFG can be first simplified by eliminating unit productions:

S → 0S1 | 1S0 | ε

Now we will convert this CFG to GNF:

S → 0SX | 1SY | ε
X → 1
Y → 0

The PDA can be:

R1: δ(q, ε, S) = {(q, 0SX) | (q, 1SY) | (q, ε)}

R2: δ(q, ε, X) = {(q, 1)}

R3: δ(q, ε, Y) = {(q, 0)}

R4: δ(q, 0, 0) = {(q, ε)}

R5: δ(q, 1, 1) = {(q, ε)}

Q12) Construct a PDA for the given CFG, and test whether 0104 is acceptable by this PDA.

S → 0BB and B → 0S | 1S | 0

A12) The PDA can be given as:

A = {(q), (0, 1), (S, B, 0, 1), δ, q, S, ?}

The production rule δ can be:

R1: δ(q, ε, S) = {(q, 0BB)}

R2: δ(q, ε, B) = {(q, 0S) | (q, 1S) | (q, 0)}

R3: δ(q, 0, 0) = {(q, ε)}

R4: δ(q, 1, 1) = {(q, ε)}

Testing 0104 i.e. 010000 against PDA:

δ(q, 010000, S) ⊢ δ(q, 010000, 0BB)

⊢ δ(q, 10000, BB) R1

⊢ δ(q, 10000,1SB) R3

⊢ δ(q, 0000, SB) R2

⊢ δ(q, 0000, 0BBB) R1

⊢ δ(q, 000, BBB) R3

⊢ δ(q, 000, 0BB) R2

⊢ δ(q, 00, BB) R3

⊢ δ(q, 00, 0B) R2

⊢ δ(q, 0, B) R3

⊢ δ(q, 0, 0) R2

⊢ δ(q, ε) R3

Thus 0104 is accepted by the PDA.

Q13) Draw a PDA for the CFG given below:

S → aSb
S → a | b | ε

A13) The PDA can be given as:

P = {(q), (a, b), (S, a, b, z0), δ, q, z0, q}

The mapping function δ will be:

R1: δ(q, ε, S) = {(q, aSb)}

R2: δ(q, ε, S) = {(q, a) | (q, b) | (q, ε)}

R3: δ(q, a, a) = {(q, ε)}

R4: δ(q, b, b) = {(q, ε)}

R5: δ(q, ε, z0) = {(q, ε)}

Simulation: Consider the string aaabb

δ(q, εaaabb, S) ⊢ δ(q, aaabb, aSb) R3
⊢ δ(q, εaabb, Sb) R1
⊢ δ(q, aabb, aSbb) R3
⊢ δ(q, εabb, Sbb) R2
⊢ δ(q, abb, abb) R3
⊢ δ(q, bb, bb) R4
⊢ δ(q, b, b) R4
⊢ δ(q, ε, z0) R5
⊢ δ(q, ε)
ACCEPT

Q14) Design a PDA for accepting a language {0n1m0n | m, n>=1}?

A14) In this PDA, n number of 0's are followed by any number of 1's followed n number of 0's. Hence the logic for design of such PDA will be as follows:

Push all 0's onto the stack on encountering first 0's. Then if we read 1, just do nothing. Then read 0, and on each read of 0, pop one 0 from the stack.

For instance:

This scenario can be written in the ID form as:

δ(q0, 0, Z) = δ(q0, 0Z)
δ(q0, 0, 0) = δ(q0, 00)
δ(q0, 1, 0) = δ(q1, 0)
δ(q0, 1, 0) = δ(q1, 0)
δ(q1, 0, 0) = δ(q1, ε)
δ(q0, ε, Z) = δ(q2, Z) (ACCEPT state)

Now we will simulate this PDA for the input string "0011100".

δ(q0, 0011100, Z) ⊢ δ(q0, 011100, 0Z)
⊢ δ(q0, 11100, 00Z)
⊢ δ(q0, 1100, 00Z)
⊢ δ(q1, 100, 00Z)
⊢ δ(q1, 00, 00Z)
⊢ δ(q1, 0, 0Z)
⊢ δ(q1, ε, Z)
⊢ δ(q2, Z)
ACCEPT

Q15) Design a PDA for accepting a language {anb2n | n>=1}?

A15) In this language, n number of a's should be followed by 2n number of b's. Hence, we will apply a very simple logic, and that is if we read single 'a', we will push two a's onto the stack. As soon as we read 'b' then for every single 'b' only one 'a' should get popped from the stack.

The ID can be constructed as follows:

δ(q0, a, Z) = (q0, aaZ)
δ(q0, a, a) = (q0, aaa)

Now when we read b, we will change the state from q0 to q1 and start popping corresponding 'a'. Hence,

δ(q0, b, a) = (q1, ε)

Thus this process of popping 'b' will be repeated unless all the symbols are read. Note that popping action occurs in state q1 only.

δ(q1, b, a) = (q1, ε)

After reading all b's, all the corresponding a's should get popped. Hence when we read ε as input symbol then there should be nothing in the stack. Hence the move will be:

δ(q1, ε, Z) = (q2, ε)

Where

PDA = ({q0, q1, q2}, {a, b}, {a, Z}, δ, q0, Z, {q2})

We can summarize the ID as:

δ(q0, a, Z) = (q0, aaZ)
δ(q0, a, a) = (q0, aaa)
δ(q0, b, a) = (q1, ε)
δ(q1, b, a) = (q1, ε)
δ(q1, ε, Z) = (q2, ε)

Now we will simulate this PDA for the input string "aaabbbbbb".

δ(q0, aaabbbbbb, Z) ⊢ δ(q0, aabbbbbb, aaZ)

⊢ δ(q0, abbbbbb, aaaaZ)

⊢ δ(q0, bbbbbb, aaaaaaZ)

⊢ δ(q1, bbbbb, aaaaaZ)

⊢ δ(q1, bbbb, aaaaZ)

⊢ δ(q1, bbb, aaaZ)

⊢ δ(q1, bb, aaZ)

⊢ δ(q1, b, aZ)

⊢ δ(q1, ε, Z)

⊢ δ(q2, ε)

Q16) Write the closure property of CFL?

A16) They are closed under −

● Union

● Concatenation

● Kleene Star operation

Union of the languages A1 and A2 , A = A1 A2 = { anbncmdm }

The additional development would have the corresponding grammar G, P: S → S1 S2

Union

Let A1 and A2 be two context free languages. Then A1 ∪ A2 is also context free.

Example

Let A1 = { xn yn , n ≥ 0}. Corresponding grammar G 1 will have P: S1 → aAb|ab

Let A2 = { cm dm , m ≥ 0}. Corresponding grammar G 2 will have P: S2 → cBb| ε

Union of A1 and A2 , A = A1 ∪ A2 = { xn yn } ∪ { cm dm }

The corresponding grammar G will have the additional production S → S1 | S2

Note - So under Union, CFLs are closed.

Concatenation

If A1 and A2 are context free languages, then A1 A2 is also context free.

Example

Union of the languages A 1 and A 2 , A = A 1 A 2 = { an bn cm dm }

The corresponding grammar G will have the additional production S → S1 S2

Note - So under Concatenation, CFL are locked.

Kleene Star

If A is a context free language, so that A* is context free as well .

Example

Let A = { xn yn , n ≥ 0}. G will have corresponding grammar P: S → aAb| ε

Kleene Star L 1 = { xn yn }*

The corresponding grammar G 1 will have additional productions S1 → SS 1 | ε

Note - So under Kleene Closure, CFL's are closed.

Context-free languages are not closed under −

● Intersection − If A1 and A2 are context free languages, then A1 ∩ A2 is not necessarily context free.

● Intersection with Regular Language − If A1 is a regular language and A2 is a context free language, then A1 ∩ A2 is a context free language.

● Complement − If A1 is a context free language, then A1’ may not be context free.

Unit - 4

Push Down Automata

Q1) Introduce PDA?

Basically a pushdown automaton is -

“Finite state machine” + “a stack”

A pushdown automaton has three components −

● an input tape,

● a control unit, and

● a stack with infinite size.

The stack head scans the top symbol of the stack.

A stack does two operations −

● Push − a new symbol is added at the top.

● Pop − the top symbol is read and removed.

A PDA may or may not read an input symbol, but it has to read the top of the stack in every transition.

Fig1: Basic structure of PDA

A PDA can be formally described as a 7-tuple (Q, ∑, S, δ, q 0 , I, F) −

Where,

● Q is the finite number of states

● ∑ is input alphabet

● S is stack symbols

● δ is the transition function: Q × (∑ ∪ {ε}) × S × Q × S* )

● q 0 is the initial state (q 0 ∈ Q)

● I is the initial stack top symbol (I ∈ S)

● F is a set of accepting states (F ∈ Q)

The following diagram shows a transition in a PDA from a state q 1 to state q 2 , labeled as a,b → c −

Fig 2: Example

This means at state q1, if we encounter an input string ‘a’ and the top symbol of the stack is ‘b’, then we pop ‘b’, push ‘c’ on top of the stack and move to state q2 .

Q2) What is a non - deterministic pushdown automata?

A2) The non-deterministic pushdown automata is very much similar to NFA. We will discuss some CFGs which accept NPDA.

The CFG which accepts deterministic PDA accepts non-deterministic PDAs as well.

Similarly, there are some CFGs which can be accepted only by NPDA and not by DPDA. Thus NPDA is more powerful than DPDA.

● Non-deterministic pushdown automata are quite similar to the NFA.

● Non-deterministic PDAs are also approved by the CFG that accepts deterministic PDAs.

● Similarly, there are several CFGs that only NPDA and not DPDA can consider. Therefore, NPDA is more efficient than DPDA.

● Non deterministic pushdown automata is basically a non finite automata (nfa) with a stack added to it.

Nondeterministic pushdown automaton or npda is a 7-tuple -

M = (Q, ∑, T, δ , q0, z, F)

Where

● Q is a finite set of states,

● ∑ is a the input alphabet,

● T is the stack alphabet,

● δ is a transition function,

● q0 ∈ Q is the initial state,

● z ∈ T is the stack start symbol, and

● F ⊆ Q is a set of final states.

Moves

The three groups of loop transitions in state q represent these respective functions:

● input a with no b’s on the stack: push a

● input b with no a’;s on the stack: push b

● input a with b’s on the stack: pop b; or, input b with a’s on the stack: pop a

Q3) Design PDA for Palindrome strips?

A3) Suppose the language consists of string L = {aba, aa, bb, bab, bbabb, aabaa, ......].

This PDA is a non-deterministic PDA because finding the mid for the given string and reading the string from left and matching it with from right (reverse) direction leads to non-deterministic moves.

Here is the ID.

Simulation of abaaba

1. δ(q1, abaaba, Z) Apply rule 1

2. δ(q1, baaba, aZ) Apply rule 5

3. δ(q1, aaba, baZ) Apply rule 4

4. δ(q1, aba, abaZ) Apply rule 7

5. δ(q2, ba, baZ) Apply rule 8

6. δ(q2, a, aZ) Apply rule 7

7. δ(q2, ε, Z) Apply rule 11

8. δ(q2, ε) Accept

Q4) What is acceptance by final state?

A4) Acceptance by final state

If the PDA enters any final state in zero or more moves after receiving the complete input, it is said to accept it by the final state.

Let P =(Q, ∑, Γ, δ, q0, Z, F) be a PDA. The language acceptable by the final state can be defined as:

L(PDA) = {w | (q0, w, Z) ⊢* (p, ε, ε), q ∈ F}

Q5) Write about acceptance by empty stack?

A5) Acceptance by empty stack

The stack of PDAs becomes empty after reading the input string from the initial setup for some PDA.

When a PDA has exhausted its stack after reading the entire string, it accepts a string.

Let P =(Q, ∑, Γ, δ, q0, Z, F) be a PDA. The language acceptable by empty stack can be defined as:

N(PDA) = {w | (q0, w, Z) ⊢* (p, ε, ε), q ∈ Q}

Q6) Construct a PDA that accepts L = {0n 1n | n ≥ 0}

A6)

This language accepts L = {ε, 01, 0011, 000111, ............................. }

The number of ‘a' and ‘b' in this example must be the same.

● We began by inserting the special symbol ‘$' into the empty stack.

● If we encounter input 0 and top is Null at state q2, we push 0 into the stack. It's possible that this will happen again. We pop this 0 if we meet input 1 and top is 0.

● If we encounter input 1 at state q3 and the top is 0, we pop this 0. It's possible that this will continue to iterate. We pop the top element if we meet input 1 and top is 0.

● If the special symbol '$' appears at the top of the stack, it is popped out, and the stack eventually moves to the accepting state q4.

Q7) Write Algorithm to find the PDA corresponding to a given CFG?

A7) Input − A CFG, G = (V, T, P, S)

Output − Equivalent PDA, P = (Q, ∑, S, δ, q0, I, F)

Step1 - Convert the CFG's productions into GNF.

Step2 - There will be only one state q on the PDA.

Step3 - The CFG's start symbol will be the PDA's start sign.

Step4 - The PDA's stack symbols will be all of the CFG's non-terminals, and the PDA's input symbols will be all of the CFG's terminals.

Step5 - For each production in the form A → aX where a is terminal and A, X are a combination of terminal and non-terminals, make a transition δ (q, a, A).

Problem

Construct a PDA using the CFG below.

G = ({S, X}, {a, b}, P, S)

Where are the productions?

S → XS | ε , A → aXb | Ab | ab

Solution

Let's say you have a PDA that's equivalent to that.

P = ({q}, {a, b}, {a, b, X, S}, δ, q, S)

Where δ −

δ(q, ε , S) = {(q, XS), (q, ε )}

δ(q, ε , X) = {(q, aXb), (q, Xb), (q, ab)}

δ(q, a, a) = {(q, ε )}

δ(q, 1, 1) = {(q, ε )}

Q8) Write Algorithm to find CFG corresponding to a given PDA?

A8) Input − A CFG, G = (V, T, P, S)

Output − Equivalent PDA, P = (Q, ∑, S, δ, q0, I, F) such that the non- terminals of the grammar G will be {Xwx | w,x ∈ Q} and the start state will be Aq0,F.

Step1 − For every w, x, y, z ∈ Q, m ∈ S and a, b ∈ ∑, if δ (w, a, ε) contains (y, m) and (z, b, m) contains (x, ε), add the production rule Xwx → a Xyzb in grammar G.

Step2 − For every w, x, y, z ∈ Q, add the production rule Xwx → XwyXyx in grammar G.

Step3 − For w ∈ Q, add the production rule Xww → ε in grammar G.

Q9) Write the Equivalence of PDA and CFG?

A9) The power of a CFG and a PDA is the same: a CFG generates context-free language, while a PDA recognizes context-free language.

We demonstrate how to transform a CFG into a PDA that recognizes the CFG's language and vice versa.

Application: Because of this equivalence, a CFG can be used to specify a programming language, and the equivalent PDA can be used to construct the language's compiler.

Theorem: If a pushdown automaton recognizes a language, it is context-free.

This means that:

1. If a language L is context-free, it is recognized by a PDA ML.

2. If a PDA ML recognizes a language L, there is a CFG GL that generates L.

Lemma: If a language is context-free, it will be recognized by a pushdown automaton.

Proof concept:

1. Let's A pretend to be a CFL. We know from the definition that A has a CFG G that it generates.

2. We'll demonstrate how to transform G, PDA P into one that accepts strings ພ if G it creates ພ.

3. P will start by figuring out a derivation ພ.

Q10) Write the difference between PDA and CFL?

A10) Difference between PDA and CFL

Q11) Convert the following grammar to a PDA that accepts the same language.

S → 0S1 | A and A → 1A0 | S | ε

A11) The CFG can be first simplified by eliminating unit productions:

S → 0S1 | 1S0 | ε

Now we will convert this CFG to GNF:

S → 0SX | 1SY | ε
X → 1
Y → 0

The PDA can be:

R1: δ(q, ε, S) = {(q, 0SX) | (q, 1SY) | (q, ε)}

R2: δ(q, ε, X) = {(q, 1)}

R3: δ(q, ε, Y) = {(q, 0)}

R4: δ(q, 0, 0) = {(q, ε)}

R5: δ(q, 1, 1) = {(q, ε)}

Q12) Construct a PDA for the given CFG, and test whether 0104 is acceptable by this PDA.

S → 0BB and B → 0S | 1S | 0

A12) The PDA can be given as:

A = {(q), (0, 1), (S, B, 0, 1), δ, q, S, ?}

The production rule δ can be:

R1: δ(q, ε, S) = {(q, 0BB)}

R2: δ(q, ε, B) = {(q, 0S) | (q, 1S) | (q, 0)}

R3: δ(q, 0, 0) = {(q, ε)}

R4: δ(q, 1, 1) = {(q, ε)}

Testing 0104 i.e. 010000 against PDA:

δ(q, 010000, S) ⊢ δ(q, 010000, 0BB)

⊢ δ(q, 10000, BB) R1

⊢ δ(q, 10000,1SB) R3

⊢ δ(q, 0000, SB) R2

⊢ δ(q, 0000, 0BBB) R1

⊢ δ(q, 000, BBB) R3

⊢ δ(q, 000, 0BB) R2

⊢ δ(q, 00, BB) R3

⊢ δ(q, 00, 0B) R2

⊢ δ(q, 0, B) R3

⊢ δ(q, 0, 0) R2

⊢ δ(q, ε) R3

Thus 0104 is accepted by the PDA.

Q13) Draw a PDA for the CFG given below:

S → aSb
S → a | b | ε

A13) The PDA can be given as:

P = {(q), (a, b), (S, a, b, z0), δ, q, z0, q}

The mapping function δ will be:

R1: δ(q, ε, S) = {(q, aSb)}

R2: δ(q, ε, S) = {(q, a) | (q, b) | (q, ε)}

R3: δ(q, a, a) = {(q, ε)}

R4: δ(q, b, b) = {(q, ε)}

R5: δ(q, ε, z0) = {(q, ε)}

Simulation: Consider the string aaabb

δ(q, εaaabb, S) ⊢ δ(q, aaabb, aSb) R3
⊢ δ(q, εaabb, Sb) R1
⊢ δ(q, aabb, aSbb) R3
⊢ δ(q, εabb, Sbb) R2
⊢ δ(q, abb, abb) R3
⊢ δ(q, bb, bb) R4
⊢ δ(q, b, b) R4
⊢ δ(q, ε, z0) R5
⊢ δ(q, ε)
ACCEPT

Q14) Design a PDA for accepting a language {0n1m0n | m, n>=1}?

A14) In this PDA, n number of 0's are followed by any number of 1's followed n number of 0's. Hence the logic for design of such PDA will be as follows:

Push all 0's onto the stack on encountering first 0's. Then if we read 1, just do nothing. Then read 0, and on each read of 0, pop one 0 from the stack.

For instance:

This scenario can be written in the ID form as:

δ(q0, 0, Z) = δ(q0, 0Z)
δ(q0, 0, 0) = δ(q0, 00)
δ(q0, 1, 0) = δ(q1, 0)
δ(q0, 1, 0) = δ(q1, 0)
δ(q1, 0, 0) = δ(q1, ε)
δ(q0, ε, Z) = δ(q2, Z) (ACCEPT state)

Now we will simulate this PDA for the input string "0011100".

δ(q0, 0011100, Z) ⊢ δ(q0, 011100, 0Z)
⊢ δ(q0, 11100, 00Z)
⊢ δ(q0, 1100, 00Z)
⊢ δ(q1, 100, 00Z)
⊢ δ(q1, 00, 00Z)
⊢ δ(q1, 0, 0Z)
⊢ δ(q1, ε, Z)
⊢ δ(q2, Z)
ACCEPT

Q15) Design a PDA for accepting a language {anb2n | n>=1}?

The ID can be constructed as follows:

δ(q0, a, Z) = (q0, aaZ)
δ(q0, a, a) = (q0, aaa)

Now when we read b, we will change the state from q0 to q1 and start popping corresponding 'a'. Hence,

δ(q0, b, a) = (q1, ε)

Thus this process of popping 'b' will be repeated unless all the symbols are read. Note that popping action occurs in state q1 only.

δ(q1, b, a) = (q1, ε)

After reading all b's, all the corresponding a's should get popped. Hence when we read ε as input symbol then there should be nothing in the stack. Hence the move will be:

δ(q1, ε, Z) = (q2, ε)

Where

PDA = ({q0, q1, q2}, {a, b}, {a, Z}, δ, q0, Z, {q2})

We can summarize the ID as:

δ(q0, a, Z) = (q0, aaZ)
δ(q0, a, a) = (q0, aaa)
δ(q0, b, a) = (q1, ε)
δ(q1, b, a) = (q1, ε)
δ(q1, ε, Z) = (q2, ε)

Now we will simulate this PDA for the input string "aaabbbbbb".

δ(q0, aaabbbbbb, Z) ⊢ δ(q0, aabbbbbb, aaZ)

⊢ δ(q0, abbbbbb, aaaaZ)

⊢ δ(q0, bbbbbb, aaaaaaZ)

⊢ δ(q1, bbbbb, aaaaaZ)

⊢ δ(q1, bbbb, aaaaZ)

⊢ δ(q1, bbb, aaaZ)

⊢ δ(q1, bb, aaZ)

⊢ δ(q1, b, aZ)

⊢ δ(q1, ε, Z)

⊢ δ(q2, ε)

Q16) Write the closure property of CFL?

A16) They are closed under −

● Union

● Concatenation

● Kleene Star operation

Union of the languages A1 and A2 , A = A1 A2 = { anbncmdm }

The additional development would have the corresponding grammar G, P: S → S1 S2

Union

Let A1 and A2 be two context free languages. Then A1 ∪ A2 is also context free.

Example

Let A1 = { xn yn , n ≥ 0}. Corresponding grammar G 1 will have P: S1 → aAb|ab

Let A2 = { cm dm , m ≥ 0}. Corresponding grammar G 2 will have P: S2 → cBb| ε

Union of A1 and A2 , A = A1 ∪ A2 = { xn yn } ∪ { cm dm }

The corresponding grammar G will have the additional production S → S1 | S2

Note - So under Union, CFLs are closed.

Concatenation

If A1 and A2 are context free languages, then A1 A2 is also context free.

Example

Union of the languages A 1 and A 2 , A = A 1 A 2 = { an bn cm dm }

The corresponding grammar G will have the additional production S → S1 S2

Note - So under Concatenation, CFL are locked.

Kleene Star

If A is a context free language, so that A* is context free as well .

Example

Let A = { xn yn , n ≥ 0}. G will have corresponding grammar P: S → aAb| ε

Kleene Star L 1 = { xn yn }*

The corresponding grammar G 1 will have additional productions S1 → SS 1 | ε

Note - So under Kleene Closure, CFL's are closed.

Context-free languages are not closed under −

● Intersection − If A1 and A2 are context free languages, then A1 ∩ A2 is not necessarily context free.

● Intersection with Regular Language − If A1 is a regular language and A2 is a context free language, then A1 ∩ A2 is a context free language.

● Complement − If A1 is a context free language, then A1’ may not be context free.

Unit - 4

Push Down Automata

Q1) Introduce PDA?

Basically a pushdown automaton is -

“Finite state machine” + “a stack”

A pushdown automaton has three components −

● an input tape,

● a control unit, and

● a stack with infinite size.

The stack head scans the top symbol of the stack.

A stack does two operations −

● Push − a new symbol is added at the top.

● Pop − the top symbol is read and removed.

A PDA may or may not read an input symbol, but it has to read the top of the stack in every transition.

Fig1: Basic structure of PDA

A PDA can be formally described as a 7-tuple (Q, ∑, S, δ, q 0 , I, F) −

Where,

● Q is the finite number of states

● ∑ is input alphabet

● S is stack symbols

● δ is the transition function: Q × (∑ ∪ {ε}) × S × Q × S* )

● q 0 is the initial state (q 0 ∈ Q)

● I is the initial stack top symbol (I ∈ S)

● F is a set of accepting states (F ∈ Q)

The following diagram shows a transition in a PDA from a state q 1 to state q 2 , labeled as a,b → c −

Fig 2: Example

This means at state q1, if we encounter an input string ‘a’ and the top symbol of the stack is ‘b’, then we pop ‘b’, push ‘c’ on top of the stack and move to state q2 .

Q2) What is a non - deterministic pushdown automata?

A2) The non-deterministic pushdown automata is very much similar to NFA. We will discuss some CFGs which accept NPDA.

The CFG which accepts deterministic PDA accepts non-deterministic PDAs as well.

Similarly, there are some CFGs which can be accepted only by NPDA and not by DPDA. Thus NPDA is more powerful than DPDA.

● Non-deterministic pushdown automata are quite similar to the NFA.

● Non-deterministic PDAs are also approved by the CFG that accepts deterministic PDAs.

● Similarly, there are several CFGs that only NPDA and not DPDA can consider. Therefore, NPDA is more efficient than DPDA.

● Non deterministic pushdown automata is basically a non finite automata (nfa) with a stack added to it.

Nondeterministic pushdown automaton or npda is a 7-tuple -

M = (Q, ∑, T, δ , q0, z, F)

Where

● Q is a finite set of states,

● ∑ is a the input alphabet,

● T is the stack alphabet,

● δ is a transition function,

● q0 ∈ Q is the initial state,

● z ∈ T is the stack start symbol, and

● F ⊆ Q is a set of final states.

Moves

The three groups of loop transitions in state q represent these respective functions:

● input a with no b’s on the stack: push a

● input b with no a’;s on the stack: push b

● input a with b’s on the stack: pop b; or, input b with a’s on the stack: pop a

Q3) Design PDA for Palindrome strips?

A3) Suppose the language consists of string L = {aba, aa, bb, bab, bbabb, aabaa, ......].

This PDA is a non-deterministic PDA because finding the mid for the given string and reading the string from left and matching it with from right (reverse) direction leads to non-deterministic moves.

Here is the ID.

Simulation of abaaba

1. δ(q1, abaaba, Z) Apply rule 1

2. δ(q1, baaba, aZ) Apply rule 5

3. δ(q1, aaba, baZ) Apply rule 4

4. δ(q1, aba, abaZ) Apply rule 7

5. δ(q2, ba, baZ) Apply rule 8

6. δ(q2, a, aZ) Apply rule 7

7. δ(q2, ε, Z) Apply rule 11

8. δ(q2, ε) Accept

Q4) What is acceptance by final state?

A4) Acceptance by final state

If the PDA enters any final state in zero or more moves after receiving the complete input, it is said to accept it by the final state.

Let P =(Q, ∑, Γ, δ, q0, Z, F) be a PDA. The language acceptable by the final state can be defined as:

L(PDA) = {w | (q0, w, Z) ⊢* (p, ε, ε), q ∈ F}

Q5) Write about acceptance by empty stack?

A5) Acceptance by empty stack

The stack of PDAs becomes empty after reading the input string from the initial setup for some PDA.

When a PDA has exhausted its stack after reading the entire string, it accepts a string.

Let P =(Q, ∑, Γ, δ, q0, Z, F) be a PDA. The language acceptable by empty stack can be defined as:

N(PDA) = {w | (q0, w, Z) ⊢* (p, ε, ε), q ∈ Q}

Q6) Construct a PDA that accepts L = {0n 1n | n ≥ 0}

A6)

This language accepts L = {ε, 01, 0011, 000111, ............................. }

The number of ‘a' and ‘b' in this example must be the same.

● We began by inserting the special symbol ‘$' into the empty stack.

● If we encounter input 0 and top is Null at state q2, we push 0 into the stack. It's possible that this will happen again. We pop this 0 if we meet input 1 and top is 0.

● If we encounter input 1 at state q3 and the top is 0, we pop this 0. It's possible that this will continue to iterate. We pop the top element if we meet input 1 and top is 0.

● If the special symbol '$' appears at the top of the stack, it is popped out, and the stack eventually moves to the accepting state q4.

Q7) Write Algorithm to find the PDA corresponding to a given CFG?

A7) Input − A CFG, G = (V, T, P, S)

Output − Equivalent PDA, P = (Q, ∑, S, δ, q0, I, F)

Step1 - Convert the CFG's productions into GNF.

Step2 - There will be only one state q on the PDA.

Step3 - The CFG's start symbol will be the PDA's start sign.

Step4 - The PDA's stack symbols will be all of the CFG's non-terminals, and the PDA's input symbols will be all of the CFG's terminals.

Step5 - For each production in the form A → aX where a is terminal and A, X are a combination of terminal and non-terminals, make a transition δ (q, a, A).

Problem

Construct a PDA using the CFG below.

G = ({S, X}, {a, b}, P, S)

Where are the productions?

S → XS | ε , A → aXb | Ab | ab

Solution

Let's say you have a PDA that's equivalent to that.

P = ({q}, {a, b}, {a, b, X, S}, δ, q, S)

Where δ −

δ(q, ε , S) = {(q, XS), (q, ε )}

δ(q, ε , X) = {(q, aXb), (q, Xb), (q, ab)}

δ(q, a, a) = {(q, ε )}

δ(q, 1, 1) = {(q, ε )}

Q8) Write Algorithm to find CFG corresponding to a given PDA?

A8) Input − A CFG, G = (V, T, P, S)

Output − Equivalent PDA, P = (Q, ∑, S, δ, q0, I, F) such that the non- terminals of the grammar G will be {Xwx | w,x ∈ Q} and the start state will be Aq0,F.

Step1 − For every w, x, y, z ∈ Q, m ∈ S and a, b ∈ ∑, if δ (w, a, ε) contains (y, m) and (z, b, m) contains (x, ε), add the production rule Xwx → a Xyzb in grammar G.

Step2 − For every w, x, y, z ∈ Q, add the production rule Xwx → XwyXyx in grammar G.

Step3 − For w ∈ Q, add the production rule Xww → ε in grammar G.

Q9) Write the Equivalence of PDA and CFG?

A9) The power of a CFG and a PDA is the same: a CFG generates context-free language, while a PDA recognizes context-free language.

We demonstrate how to transform a CFG into a PDA that recognizes the CFG's language and vice versa.

Application: Because of this equivalence, a CFG can be used to specify a programming language, and the equivalent PDA can be used to construct the language's compiler.

Theorem: If a pushdown automaton recognizes a language, it is context-free.

This means that:

1. If a language L is context-free, it is recognized by a PDA ML.

2. If a PDA ML recognizes a language L, there is a CFG GL that generates L.

Lemma: If a language is context-free, it will be recognized by a pushdown automaton.

Proof concept:

1. Let's A pretend to be a CFL. We know from the definition that A has a CFG G that it generates.

2. We'll demonstrate how to transform G, PDA P into one that accepts strings ພ if G it creates ພ.

3. P will start by figuring out a derivation ພ.

Q10) Write the difference between PDA and CFL?

A10) Difference between PDA and CFL

Q11) Convert the following grammar to a PDA that accepts the same language.

S → 0S1 | A and A → 1A0 | S | ε

A11) The CFG can be first simplified by eliminating unit productions:

S → 0S1 | 1S0 | ε

Now we will convert this CFG to GNF:

S → 0SX | 1SY | ε
X → 1
Y → 0

The PDA can be:

R1: δ(q, ε, S) = {(q, 0SX) | (q, 1SY) | (q, ε)}

R2: δ(q, ε, X) = {(q, 1)}

R3: δ(q, ε, Y) = {(q, 0)}

R4: δ(q, 0, 0) = {(q, ε)}

R5: δ(q, 1, 1) = {(q, ε)}

Q12) Construct a PDA for the given CFG, and test whether 0104 is acceptable by this PDA.

S → 0BB and B → 0S | 1S | 0

A12) The PDA can be given as:

A = {(q), (0, 1), (S, B, 0, 1), δ, q, S, ?}

The production rule δ can be:

R1: δ(q, ε, S) = {(q, 0BB)}

R2: δ(q, ε, B) = {(q, 0S) | (q, 1S) | (q, 0)}

R3: δ(q, 0, 0) = {(q, ε)}

R4: δ(q, 1, 1) = {(q, ε)}

Testing 0104 i.e. 010000 against PDA:

δ(q, 010000, S) ⊢ δ(q, 010000, 0BB)

⊢ δ(q, 10000, BB) R1

⊢ δ(q, 10000,1SB) R3

⊢ δ(q, 0000, SB) R2

⊢ δ(q, 0000, 0BBB) R1

⊢ δ(q, 000, BBB) R3

⊢ δ(q, 000, 0BB) R2

⊢ δ(q, 00, BB) R3

⊢ δ(q, 00, 0B) R2

⊢ δ(q, 0, B) R3

⊢ δ(q, 0, 0) R2

⊢ δ(q, ε) R3

Thus 0104 is accepted by the PDA.

Q13) Draw a PDA for the CFG given below:

S → aSb
S → a | b | ε

A13) The PDA can be given as:

P = {(q), (a, b), (S, a, b, z0), δ, q, z0, q}

The mapping function δ will be:

R1: δ(q, ε, S) = {(q, aSb)}

R2: δ(q, ε, S) = {(q, a) | (q, b) | (q, ε)}

R3: δ(q, a, a) = {(q, ε)}

R4: δ(q, b, b) = {(q, ε)}

R5: δ(q, ε, z0) = {(q, ε)}

Simulation: Consider the string aaabb

δ(q, εaaabb, S) ⊢ δ(q, aaabb, aSb) R3
⊢ δ(q, εaabb, Sb) R1
⊢ δ(q, aabb, aSbb) R3
⊢ δ(q, εabb, Sbb) R2
⊢ δ(q, abb, abb) R3
⊢ δ(q, bb, bb) R4
⊢ δ(q, b, b) R4
⊢ δ(q, ε, z0) R5
⊢ δ(q, ε)
ACCEPT

Q14) Design a PDA for accepting a language {0n1m0n | m, n>=1}?

A14) In this PDA, n number of 0's are followed by any number of 1's followed n number of 0's. Hence the logic for design of such PDA will be as follows:

Push all 0's onto the stack on encountering first 0's. Then if we read 1, just do nothing. Then read 0, and on each read of 0, pop one 0 from the stack.

For instance:

This scenario can be written in the ID form as:

δ(q0, 0, Z) = δ(q0, 0Z)
δ(q0, 0, 0) = δ(q0, 00)
δ(q0, 1, 0) = δ(q1, 0)
δ(q0, 1, 0) = δ(q1, 0)
δ(q1, 0, 0) = δ(q1, ε)
δ(q0, ε, Z) = δ(q2, Z) (ACCEPT state)

Now we will simulate this PDA for the input string "0011100".

δ(q0, 0011100, Z) ⊢ δ(q0, 011100, 0Z)
⊢ δ(q0, 11100, 00Z)
⊢ δ(q0, 1100, 00Z)
⊢ δ(q1, 100, 00Z)
⊢ δ(q1, 00, 00Z)
⊢ δ(q1, 0, 0Z)
⊢ δ(q1, ε, Z)
⊢ δ(q2, Z)
ACCEPT

Q15) Design a PDA for accepting a language {anb2n | n>=1}?

The ID can be constructed as follows:

δ(q0, a, Z) = (q0, aaZ)
δ(q0, a, a) = (q0, aaa)

Now when we read b, we will change the state from q0 to q1 and start popping corresponding 'a'. Hence,

δ(q0, b, a) = (q1, ε)

Thus this process of popping 'b' will be repeated unless all the symbols are read. Note that popping action occurs in state q1 only.

δ(q1, b, a) = (q1, ε)

After reading all b's, all the corresponding a's should get popped. Hence when we read ε as input symbol then there should be nothing in the stack. Hence the move will be:

δ(q1, ε, Z) = (q2, ε)

Where

PDA = ({q0, q1, q2}, {a, b}, {a, Z}, δ, q0, Z, {q2})

We can summarize the ID as:

δ(q0, a, Z) = (q0, aaZ)
δ(q0, a, a) = (q0, aaa)
δ(q0, b, a) = (q1, ε)
δ(q1, b, a) = (q1, ε)
δ(q1, ε, Z) = (q2, ε)

Now we will simulate this PDA for the input string "aaabbbbbb".

δ(q0, aaabbbbbb, Z) ⊢ δ(q0, aabbbbbb, aaZ)

⊢ δ(q0, abbbbbb, aaaaZ)

⊢ δ(q0, bbbbbb, aaaaaaZ)

⊢ δ(q1, bbbbb, aaaaaZ)

⊢ δ(q1, bbbb, aaaaZ)

⊢ δ(q1, bbb, aaaZ)

⊢ δ(q1, bb, aaZ)

⊢ δ(q1, b, aZ)

⊢ δ(q1, ε, Z)

⊢ δ(q2, ε)

Q16) Write the closure property of CFL?

A16) They are closed under −

● Union

● Concatenation

● Kleene Star operation

Union of the languages A1 and A2 , A = A1 A2 = { anbncmdm }

The additional development would have the corresponding grammar G, P: S → S1 S2

Union

Let A1 and A2 be two context free languages. Then A1 ∪ A2 is also context free.

Example

Let A1 = { xn yn , n ≥ 0}. Corresponding grammar G 1 will have P: S1 → aAb|ab

Let A2 = { cm dm , m ≥ 0}. Corresponding grammar G 2 will have P: S2 → cBb| ε

Union of A1 and A2 , A = A1 ∪ A2 = { xn yn } ∪ { cm dm }

The corresponding grammar G will have the additional production S → S1 | S2

Note - So under Union, CFLs are closed.

Concatenation

If A1 and A2 are context free languages, then A1 A2 is also context free.

Example

Union of the languages A 1 and A 2 , A = A 1 A 2 = { an bn cm dm }

The corresponding grammar G will have the additional production S → S1 S2

Note - So under Concatenation, CFL are locked.

Kleene Star

If A is a context free language, so that A* is context free as well .

Example

Let A = { xn yn , n ≥ 0}. G will have corresponding grammar P: S → aAb| ε

Kleene Star L 1 = { xn yn }*

The corresponding grammar G 1 will have additional productions S1 → SS 1 | ε

Note - So under Kleene Closure, CFL's are closed.

Context-free languages are not closed under −

● Intersection − If A1 and A2 are context free languages, then A1 ∩ A2 is not necessarily context free.

● Intersection with Regular Language − If A1 is a regular language and A2 is a context free language, then A1 ∩ A2 is a context free language.

● Complement − If A1 is a context free language, then A1’ may not be context free.

Sign Up