## 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 |

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. |

Question 3 |

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 3 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.

There are 3 questions to complete.