Push Down Automata Questions

MCQ bookmark_border

21.

Define for a context free language L ? {0, 1}* ,  init(L)={u ? uv ? L for some v in {0,1}?} ( in other words, init(L) is the set of prefixes of L) Let L = {w ? w is nonempty and has an equal number of 0

A

the set of all binary strings with unequal number of 0's and 1's

B

the set of all binary strings including null string

C

the set of all binary strings with exactly one more 0 than the number of 1

D

None of the above

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

22.

Pushdown automata can recognize language generated by_________.

A

Only context free grammar

B

Only regular grammar

C

Context free grammar or rergular gramma

D

Only context sensitive grammar

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

23.

To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of productions to be used is:

A

2n - 1

B

2n

C

n + 1

D

n ²

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

24.

Consider the following two Grammars : G1 : S ? SbS|a G2 : S ? aB|ab, A?GAB|a, B?ABb|b Which of the following option is correct ?

A

Only G₁ is ambiguous

B

Only G₂ is ambiguous

C

Both G₁ and G ₂are ambiguous

D

Both G₁ and G₂are not ambiguous

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

25.

In a pushdown automaton P=(Q,?,?,?,q0,F), a transition of the form,

where p,q?Q, a???{?}, X,Y,???{?}, represents

(q,Y) ? ?(p,a,X)

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

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

A

50

B

100

C

55

D

45

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

26.

Push down automata accepts which language?

A

Context sensitive language

B

Context free language

C

Recursive language

D

None of the mentioned

Correct Answer: B

PDA accepts CFG.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

27.

A regular Grammar is a _________

A

CFG

B

Non CFG

C

English Grammar

D

None of the mentioned

Correct Answer: A

Regular grammar is CFG. It restricts its rules to a single non terminal on left hand side.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

28.

The transition a Push down automaton makes is additionally dependent upon the:

A

stack

B

input tape

C

terminals

D

none of the mentioned

Correct Answer: A

A PDA is a finite machine which has an additional stack storage. Its transitions are based not only on input and the correct state but also on the stack.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

29.

A PDA machine configuration (p, w, y) can be correctly represented as:

A

(current state, unprocessed input, stack content)

B

(unprocessed input, stack content, current state)

C

(current state, stack content, unprocessed input)

D

none of the mentioned

Correct Answer: A

A machine configuration is an element of K

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

30.

|-* is the __________ closure of |-

A

symmetric and reflexive

B

transitive and reflexive

C

symmetric and transitive

D

none of the mentioned

Correct Answer: B

A string w is accepted by a PDA if and only if (s,w, e) |-* (f, e, e)

Check Answer report_problem Report forum Discussion