Document From Er Shubham Marotkar ?

Theory of Computation
Class- TY-BTech CSE Semester-I

Multiple Choice Questions
MCQ’s (Options in bold are the answers for respective MCQ)
UNIT-V
1. The transition a Push down automaton makes is additionally dependent upon the:
a) stack
b) input tape
c) terminals
d) none of the mentioned
2. 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)
3. With reference of a PDA, which among the following do we perform from the start state
with an empty stack?
a) process the whole string
b) end in final state
c) end with an empty stack
d) all of the mentioned
4. A DPDA is a PDA in which:

a) No state p has two outgoing transitions
b) More than one state can have two or more outgoing transitions
c) Atleast one state has more than one transitions
d) None of the mentioned
5. If the PDA does not stop on an accepting state and the stack is not empty, the string is:
a) rejected
b) goes into loop forever
c) both (a) and (b)
6. A language accepted by Deterministic Push down automata is closed under which of the
following?
a) Complement
b) Union
c) Both (a) and (b)
7. The instantaneous PDA is has the following elements
a) State
b) Unconsumed input
c) Stack content
d) All of the mentioned
8. A push down automata can represented using:

a) Transition diagram
b) Transition table
c) ID
9. State true or false:

Statement: Every context free grammar can be transformed into an equivalent non
deterministic push down automata.
a) true
b) false
10. Which of the following are the actions that operates on stack top?
a) Pushing
b) Popping
c) Replacing
11. A push down automata is said to be _________ if it has atmost one transition around all
configurations.
a) Finite
b) Non regular
c) Non-deterministic
d) Deterministic
12. A push down automata is different than finite automata by:

a) Its memory
b) Number of states
c) Both (a) and (b)
d) None of these
13. PDA is more powerful than
a) Turing machine
b) Multi tape Turing machine
c) Finite automata
d) All of these
14. A push down automaton employs ________ data structure.
a) Queue
b) Linked List
c) Hash Table
d) Stack
15. State true or false: Statement: The operations of PDA never work on elements, other
than the top.
a) true
b) false
16. Push down automata accepts _________ languages.
a) Type 3
b) Type 2
c) Type 1
d) Type 0
17. A string is accepted by a PDA when
a) Stack is empty
b) Acceptance state
c) Both (a) and (b)
18. The following move of a PDA is on the basis of:
a) Present state
b) Input Symbol
c) Both (a) and (b)
19. 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
20. 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
21. Pumping Lemma is generally used for proving
a) Given grammar is regular

b) Given grammar is not regular
c) Given regular expressions are equivalent
d) None of these.
22. Pumping lemma for context free grammar is used for

a) Proving certain languages are not context free
b) Proving language is infinite
c) Both (a) and (b)
d) None of these
23. The pumping lemma is often used to prove that a language is:
a) Context free
b) Regular
c) Not context free
d) None of the these
24. Which of the expressions correctly is an requirement of the pumping lemma for the
context free languages?
a) uvmw
b) uvmwm
c) uv2mw
25. Using pumping lemma, which of the following cannot be proved as ‘not a CFL’?
a) {aibici|i>=0}
b) {ss|s∈{a,b}*}
c) The set legal C programs
26. Which of the following cannot be filled in the blank below?
Statement: There are CFLs L1 and L2 so that ___________is not a CFL.
a) L1∩L2
b) L1′
c) L1*
27. If L1 and L2 are context free language then
a) Their union is also a context free language

b) There concatenation is also context free language
c) Both (a) and (b)
d) None of these
28. Which of the following statement is false?
a) If L is context free language then L* is also a context free language

b) If L1 and L2 are context free language then there intersection is not a context
free language
c) If L1 and L2 are context free language then there union is also a context free
language
d) None of these
29. In pumping lemma for context free language
a) We start by assuming the given language is context free and then we get
contradict
b) We first convert the given language into regular language and then apply
steps on
c) Both (a) and (b)
d) None of these

Document From Er Shubham Marotkar ?

Uploaded by

Copyright:

Available Formats

Document From Er Shubham Marotkar ?

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Document From Er Shubham Marotkar ?

Uploaded by

Copyright:

Available Formats

Theory of Computation

Class- TY-BTech CSE Semester-I

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

4. A DPDA is a PDA in which:

8. A push down automata can represented using:

9. State true or false:

12. A push down automata is different than finite automata by:

a) Given grammar is regular

22. Pumping lemma for context free grammar is used for

27. If L1 and L2 are context free language then

a) Their union is also a context free language

a) If L is context free language then L* is also a context free language

You might also like