Theory of Computation (3160704) MCQs

MCQs of Pushdown Automata, CFL And NCFL

Showing 11 to 20 out of 30 Questions
1 2 3
11.
Push down automata accepts _________ languages.
(a) Type 3
(b) Type 2
(c) Type 1
(d) Type 0
Answer:

Option (b)

12.
Every context free grammar can be transformed into an equivalent push down automata.
(a) True
(b) False
(c) May be
(d) Can't say
Answer:

Option (a)

13.
A PDA machine configuration (q, a, X) can be correctly represented as:
(a) (unprocessed input, stack content, current state)
(b) (current state, unprocessed input, stack content)
(c) (current state, stack content, unprocessed input)
(d) none of the mentioned
Answer:

Option (b)

14.
A DPDA is a PDA in which:
(a) No state has two outgoing transitions
(b) More than one state can have two or more outgoing transitions
(c) At least one state has more than one transitions
(d) None of the mentioned
Answer:

Option (a)

15.
The push down automata accepts the input string in form of
(a) Finial state
(b) Empty stack
(c) Both (a) and (b)
(d) None of these
Answer:

Option (c)

16.
If the PDA does not stop on an accepting state and the stack is not empty, the string is:
(a) Accepted
(b) Rejected
(c) Goes into loop forever
(d) None of the mentioned
Answer:

Option (b)

17.
Which of the following is analogous to the following? :NFA and NPDA
(a) Regular language and Context Free language
(b) Regular language and Context Sensitive language
(c) Context free language and Context Sensitive language
(d) None of the mentioned
Answer:

Option (a)

18.
The following move of a PDA is on the basis of:
(a) Present state
(b) Input Symbol
(c) Both (a) and (b)
(d) None of the mentioned
Answer:

Option (c)

19.
The symbol Z0 in formal definition of PDA is used for
(a) Input symbol
(b) Initial Stack symbol
(c) Unprocessed input
(d) Transition function
Answer:

Option (b)

20.
PDA works as Finite Automata when the number of auxiliary memory it has is
(a) 3
(b) 2
(c) 1
(d) 0
Answer:

Option (d)

Showing 11 to 20 out of 30 Questions
1 2 3