Question 1 |

Consider the pushdown automaton (PDA) P below, which runs on the input alphabet \{a,b\}, has stack alphabet \{ \perp ,A\}, and has three states \{s,p,q\}, with s being
the start state. A transition from state u to state v , labelled c/X/\gamma , where c is
an input symbol or , X is a stack symbol, and \gamma is a string of stack symbols,
represents the fact that in state u, the PDA can read c from the input, with X on
the top of its stack, pop X from the stack, push in the string \gamma on the stack, and
go to state v. In the initial configuration, the stack has only the symbol \perp in it.
The PDA accepts by empty stack.

Which one of the following options correctly describes the language accepted by P?

Which one of the following options correctly describes the language accepted by P?

\{ a^mb^n |1\leq m\text{ and }n \lt m \} | |

\{ a^mb^n |0 \leq n \leq m \} | |

\{ a^mb^n |0\leq m\text{ and } 0 \lt n \} | |

\{ a^m |0\leq m \} \cup \{b^n|0 \leq n \} |

Question 1 Explanation:

Question 2 |

In a pushdown automaton P=(Q, \Sigma, \Gamma, \delta, q_0, F), a transition of the form,

where p,q \in Q \; a \in \sigma \cup \{ \epsilon \} ,\;X,Y, \in \Gamma \cup \{ \epsilon \}, represents

(q,Y) \in \delta(p,a,X)

Consider the following pushdown automaton over the input alphabet \Sigma = \{a,b\} and stack alphabet \Gamma = \{ \#, A\}.

The number of strings of length 100 accepted by the above pushdown automaton is ___________

where p,q \in Q \; a \in \sigma \cup \{ \epsilon \} ,\;X,Y, \in \Gamma \cup \{ \epsilon \}, represents

(q,Y) \in \delta(p,a,X)

Consider the following pushdown automaton over the input alphabet \Sigma = \{a,b\} and stack alphabet \Gamma = \{ \#, A\}.

The number of strings of length 100 accepted by the above pushdown automaton is ___________

50 | |

49 | |

101 | |

100 |

Question 2 Explanation:

Question 3 |

Which one of the following is FALSE?

There is a unique minimal DFA for every regular language | |

Every NFA can be converted to an equivalent PDA. | |

Complement of every context-free language is recursive. | |

Every nondeterministic PDA can be converted to an equivalent deterministic PDA. |

Question 3 Explanation:

Question 4 |

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

Which one of the following is TRUE?

Which one of the following is TRUE?

L=\{a^{n}b^{n}|m\geq 0\} is not accepted by any finite automata | |

L=\{a^{n}|n\geq 0\}\cup \{a^{n}b^{n}|m\geq 0\} is not accepted by any deterministic PDA | |

L is not accepted by any Turing machine that halts one very input | |

L=\{a^{n}|n\geq 0\}\cup \{a^{n}b^{n}|m\geq 0\} is deterministic context-free |

Question 4 Explanation:

Question 5 |

Consider the NPDA \langle Q=\{q_{0},q_{1},q_{2}\}, \Sigma =\{0,1\}, \Gamma =\{0,1,\perp \},\delta ,q_{0},\perp , F=\{q_{2}\} \rangle, where (as per usual convention) Q is the set of states, \Sigma is the input alphabet, \Gamma is the stack alphabet, \delta is the state transition function, q_{0} is the initial state, \perp is the initial stack symbol, and F is the set of accepting states. The state transition is as follows:

Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?

Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?

10110 | |

10010 | |

01010 | |

01001 |

Question 5 Explanation:

There are 5 questions to complete.

check question 8 in GO answer is bab

Thank you subaru natsuki,

We have updated the answer.