## Push-Down-Automata

Question 1 |

Consider the transition diagram of a PDA given below with input alphabet Σ = {a,b} and stack alphabet Γ = {X,Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA.

Which one of the following is **TRUE**?

L = {a ^{n} b^{n}│n ≥ 0} and is not accepted by any ﬁnite automata | |

L = {a ^{n} |n≥0} ∪ {a^{n}b^{n}|n ≥ 0} and is not accepted by any deterministic PDA | |

L is not accepted by any Turing machine that halts on every input | |

L = {a ^{n} |n ≥ 0} ∪ {a^{n} b^{n} |n ≥ 0} and is deterministic context-free |

Question 1 Explanation:

In this PDA, we can give labels to state as q

where q

This PDA accepts the string by both ways i.e. by using q

Since q

Hence, L = {a

_{0}, q_{1}, q_{2}where q

_{0}and q_{2}are final states.This PDA accepts the string by both ways i.e. by using q

_{0}accepts as final state and by using q_{2}it accepts as empty stack.Since q

_{0}is initial as well as final state, so it can accept any number of a’s (including zero a’s) and by using q_{2}as empty stack it accept strings which has equal number of a’s and b’s (b’s comes after a’s).Hence, L = {a

^{n}| n≥0} ∪ { a^{n}b^{n}| n≥0}.Question 2 |

Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA?

{a ^{n}b^{n}c^{n} ∣ n≥0} | |

{a ^{l}b^{m}c^{n} ∣ l≠m or m≠n} | |

{a ^{n}b^{n} ∣ n≥0} | |

{a ^{m}b^{n}∣ m,n≥0} |

Question 2 Explanation:

At a time, the DPDA can compare 'a' and 'b' or 'b' and 'c' but not both.

To compare both conditions at the same time, we need a NPDA.

To compare both conditions at the same time, we need a NPDA.

Question 3 |

{a ^{l}b^{m}c^{n} | l = m = n} | |

{a ^{l}b^{m}c^{n} | l = m} | |

{a ^{l}b^{m}c^{n} | 2l = m+n} | |

{a ^{l}b^{m}c^{n} | m=n} |

Question 3 Explanation:

For every 'a' we put two X in stacks [at state S].

After that for every 'b' we pop out one X [reach to state t].

After that for every 'c' we pop out one X [reach to state u].

If all X are popped out then reached to final state f, means for every 'b' and 'c' there is 'a'. 'a' is followed by 'b' and 'b' is followed by 'c'.

Means,

Sum of no. of b's and no. of c's = twice of no. of a's

i.e., {a

^{l}b

^{m}c

^{n}| 2l = m+n}

Question 4 |

Let L

_{D}be the set of all languages accepted by a PDA by final state and L_{E}the set of all languages accepted by empty stack. Which of the following is true?L _{D} = L_{E} | |

L _{D} ⊃ L_{E} | |

L _{E} = L_{D} | |

None of the above |

Question 4 Explanation:

For any PDA which can be accepted by final state, there is an equivalent PDA which can also be accepted by an empty stack and for any PDA which can be accepted by an empty stack, there is an equivalent PDA which can be accepted by final state.

Question 5 |

{w⊂w ^{R}|w ∈ {a,b}*} | |

{ww ^{R}|w ∈ {a,b,c}*} | |

{a ^{n}b^{n}c^{n}|n ≥ 0} | |

{w|w is a palindrome over {a,b,c}} |

Question 5 Explanation:

(A) w⊂w

(B) ww

(C) {a

(D) {w | w is palindrome over {a,b,c}},

is realized by NPDA because we can't find deterministically the center of palindrome string.

^{R}, can be realized using DPDA because we know the center of the string that is c here.(B) ww

^{R}, is realized by NPDA because we can't find deterministically the center of palindrome string.(C) {a

^{n}b^{n}c^{n}| n ≥ 0} is CSL.(D) {w | w is palindrome over {a,b,c}},

is realized by NPDA because we can't find deterministically the center of palindrome string.

Question 6 |

Give a deterministic PDA for the language L = {a

^{n}cb^{2n}|n ≥ 1} over the alphabet Σ = {a,b,c}. Specify the acceptance state.Theory Explanation is given below. |

There are 6 questions to complete.