Push Down Automata Questions

MCQ bookmark_border

1.

PDA is more powerful than

A

Turing machine

B

 Finite automata

C

Both (a) and (b)

D

None of these

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

2.

PDA can be represented with the help of

A

Instantaneous description

B

Transition diagram

C

Transition table

D

All of these

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

3.

Which of the following statement is false?

A

Let L is a language accepted by a PDA P then there exist a CFG G L such that L(G) =N(P)

B

If L is a CFL then there exists a push down automata P accepting CFL L by empty stack i.e. L = N(P)

C

If L is a language accepted by PDA A by final state there exist a PDA B that accepts L by empty stack such that L =L(A) = N(B)

D

All of these

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

4.

A push down automata is different than finite automata by

A

Its memory (stack)

B

Number of states

C

Both (a) and (b)

D

 None of these

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

5.

The instantaneous description is PDA shows

A

Present state

B

Stack symbol

C

String to be processed

D

All of these

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

6.

The symbol Z0 in formal definition of PDA is used for

A

Stack symbol

B

Input symbol

C

Both (a) and (b)

D

None of these

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

7.

The language accepted by a Pushdown Automation in which the stack is limited to 10 items is best described as

A

Context Free

B

Regular

C

Deterministic Context Free

D

Recursive

Correct Answer: B

Pushdown automata is used for context free languages, i.e., languages in which the length of elements is unrestricted and length of one element is related to other. To resolve this problem, we use a stack with no restrictions on length. But in the given case, length of stack is restricted. Thus, this pushdown automata can only accept languages which can also be accepted by finite state automata and a finite state automata accepts only regular languages. Thus, B is the correct choice. Please comment below if you find anything wrong in the above post.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

8.

Which of the following statements is true?

A

If a language is context free it can always be accepted by a deterministic push-down automaton

B

The union of two context free languages is context free

C

The intersection of two context free languages is context free

D

The complement of a context free language is context free

Correct Answer: B

Refer http://en.wikipedia.org/wiki/Context-free_language#Closure_properties

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

9.

Consider the NPDA ?Q = {q0, q1, q2}, ? = {0, 1}, ? = {0, 1, ?}, ?, q0, ?, F = {q2}?, where (as per usual convention) Q is the set of states, ? is the input alphabet, ? is stack alphabet, ? is the state transition function, q0 is the initial state, ? is the initial stack symbol, and F is the set of accepting states, The state transition is as following

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

A

10110

B

10010

C

01010

D

01001

Correct Answer: B

In q0 state for '1', a '1' is pushed and for a '0' a '0' is pushed. In q1 state, for a '0' a '1' is popped and for a '1' a '0' is popped. So, the given PDA is accepting all strings of of the form x0x'r or x1x'r or xx'r, where x'r is the reverse of the 1's complement of x. The given string 101100 has 6 letters and we are given 5 letter strings. So, x0 is done, with x = 10110. So, x'r = (01001)r = 10010. Hence option B is correct.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

10.

Which of the following languages are context-free?

L1 = {ambnanbm ? m, n ? 1}
L2 = {ambnambn ? m, n ? 1}
L3 = {ambn ? m = 2n + 1} 

A

L1 and L2 only

B

L1 and L3 only

C

L2 and L3 only

D

L3 only

Correct Answer: B

Check Answer report_problem Report forum Discussion