Push-Down Automata
1.

PDA is more powerful than

A.

Turing machine

B.

Finite automata

C.

Both (a) and (b)

D.

None of these

2.

PDA can be represented with the help of

A.

Instantaneous description

B.

Transition diagram

C.

Transition table

D.

All of these

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

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

5.

The instantaneous description is PDA shows

A.

Present state

B.

Stack symbol

C.

String to be processed

D.

All of these

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

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

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

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

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