Push Down Automata Questions

MCQ bookmark_border

11.

Which one of the following statements is FALSE?

A

There exist context-free languages such that all the context-free grammars generating them are ambiguous

B

An unambiguous context free grammar always has a unique parse tree for each string of the language generated by it.

C

Both deterministic and non-deterministic pushdown automata always accept the same set of languages

D

A finite set of string from one alphabet is always a regular language.
 

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

12.

If we use internal data forwarding to speed up the performance of a CPU (R1, R2 and R3 are registers and M[100] is a memory reference), then the sequence of operations

A

A

B

B

C

C

D

D

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

13.

Consider the following context-free grammars:

Which one of the following pairs of languages is generated by G1 and G2, respectively

A

A

B

B

C

C

D

D

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

14.

Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z₀, X} where Z₀ is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) ? (t, XZ₀) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z₀ and X (in that order) on the stack.
(s, a, Z₀) ? (s, XXZ₀)
(s, ?, Z₀) ? (f, ?)
(s, a, X) ? (s, XXX)
(s, b, X) ? (t, ?)
(t, b, X) ? (t,.?)
(t, c, X) ? (u, ?)
(u, c, X) ? (u, ?)
(u, ?, Z₀) ? (f, ?)
The language accepted by the PDA is

A

{a^lb^mcⁿ | l = m = n}

B

{a^lb^mcⁿ | l = m}

C

{a^lb^mcⁿ | 2l = m+n}

D

{a^lb^mcⁿ | m=n}

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

15.

Consider the following languages.

L₁ = {aⁱ b^j c^k | i = j, k ? 1}
L₁ = {aⁱ b^j | j = 2i, i ? 0}
Which of the following is true?

A

L1 is not a CFL but L2 is

B

	L1 ? L2 = ? and L1 is non-regular

C

	L1 ? L2 = ? and L1 is non-regular

D

There is a 4-state PDA that accepts L1, but there is no DPDA that accepts L2

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

16.

Let L_D  be the set of all languages accepted by a PDA by final state and L_F  the set of all languages accepted by empty stack. Which of the following is true?

A

A

B

B

C

C

D

D

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

17.

If L1 is a context free language and L2 as a regular language, which of the following is/are False? a.  L1-L2 is not context free b.  L1 ? L2 is context free c.  ~L1 is context free d.  ~L2 is regular

A

Only b

B

Only c

C

Both a and c

D

Both b and c

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

18.

Regarding the power of recognition of languages, which of the following statement is false?

A

The non-deterministic finite state automata are equivalent to deterministic finite state automata

B

Non-deterministic pushdown automata is equivalent to deterministic pushdown automata.

C

Non-deterministic Turing machines are equivalent to deterministic Turing machines.

D

Multi-tape Turing machines are equivalent to Single-tape Turing machines.

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

19.

Which of the following languages over {a,b,c} is accepted by a deterministic pushdown automata?\a. {wcw^R ? w? {a,b}* } b. {ww^R ? w? {a,b,c}* }c. {aⁿbⁿcⁿ ? n ? 0 } d. {w ? w is a palindrome over {a,b,c} } Note: w^R  is the string obtained by reversing 'w'

A

A

B

B

C

C

D

D

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

20.

If L1 and L2 are context free languages and R a regular set, one of the languages below is not necessarily a context free language, which one?

A

L1 . L2

B

L1 ? L2

C

L1 ? R

D

L1 ? L2

Correct Answer: B

Check Answer report_problem Report forum Discussion