GATE Prev Year : Theory of Computation Test-9 for GATE & PSU CS Exams

Question 1

Consider the finite automaton in the following figure.

What is the set of reachable states for the input string 0011?

Question 2

Which of the following statements is/are FALSE?
(1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
(2) Turing recognizable languages are closed under union and complementation.
(3) Turing decidable languages are closed under intersection and complementation.
(4) Turing recognizable languages are closed under union and intersection.

Question 3

Consider the CFG with {S, A,B} as the non-terminal alphabet, {a,b}as the terminal alphabet, S as the start symbol and the following set of production rules:

Which of the following strings is generated by the grammar?

Question 4

Consider the CFG with {S, A,B} as the non-terminal alphabet, {a,b}as the terminal alphabet, S as the start symbol and the following set of production rules:

For the string “aabbab”, how many derivation trees are there?

Question 5

A push-down automation (pda) is given in the following extended notation of finite state diagram:

The nodes denote the states while the edges denote the moves of the pda. The edge labels are of form d, s/s' where d is the input symbol read and s, s' are the stack contents before and after the move. For example the edge labeled 1, s/1.s denotes the move from state q₀ to q₀ in which the input symbol 1 is read and pushed to the stack.

Introduce two edges with appropriate labels in the above diagram so that the resulting pda accepts the language ${x 2 x^{R} ∣ x \in {0, 1}^{*}, x^{R} denotes reverse of x}$ by empty stack.

Question 6

A push-down automation (pda) is given in the following extended notation of finite state diagram:

The nodes denote the states while the edges denote the moves of the pda. The edge labels are of form d, s/s' where d is the input symbol read and s, s' are the stack contents before and after the move. For example the edge labeled 1, s/1.s denotes the move from state q₀ to q₀ in which the input symbol 1 is read and pushed to the stack.

by given data can we design non-deterministic pda with three states in the above notation that accept the language {0ⁿ 1^m|n ≤m ≤2n}by empty stack