Unit – V MCQ

1. Which of the problems are unsolvable?

a) Halting problem
b) Boolean Satisfiability problem
c) Halting problem & Boolean Satisfiability problem
d) None of the mentioned
2. The decision problem is the function from string to ______________
a) char
b) int
c) boolean
d) none of the mentioned
3. A language L is said to be ____________ if there is a turing machine M such that L(M)=L
and M halts at every point.
a) Turing acceptable
b) decidable
c) undecidable
d) none of the mentioned
4. Which among the following are undecidable theories?
a) The first order theory of boolean algebra
b) The first order theory of Euclidean geomentry
c) The first order theory of hyperbolic geometry
d) The first order theory of the natural number with addition, multiplication, and equality
5. Rec-DFA = { | M is a DFA and M recognizes input w}.
Fill in the blank:
Rec-DFA is ___________
a) Undecidable
b) Decidable
c) Non finite
d) None of the mentioned
5. Which among the following are semi decidable?
a) Empty-DFA
b) Rec-NFA
c) Infinite-DFA
d) All of the mentioned
6. The language accepted by a turing machine is called ____________
a) Recursive Ennumerable
b) Recursive
c) Recursive Ennumerable and Recursive
d) None of the mentioned
7. Decidable can be taken as a synonym to:
a) recursive
b) non recursive
c) recognizable
d) none of the mentioned
8. The problems which have no algorithm, regardless of whether or not they are accepted by a
turing machine that fails to halts on some input are referred as:
a) Decidable
b) Undecidable
c) Computable
d) None of the mentioned
10. A problem is called __________ if its has an efficient algorithm for itself.
a) tractable
b) intractable
c) computational
d) none of the mentioned
11. A formal language is recursive if :
a) a total turing machine exists
b) a turing machine that halts for every input
c) turing machine rejects if the input does not belong to the language
d) all of the mentioned
12. Recursive languages are also known as:
a) decidable
b) undecidable
c) sometimes decidable
d) none of the mentioned
13. The class of recursive language is known as:
a) R
b) RC
c) RL
d) All of the mentioned
1. According to the rice’s theorem, If P is a non trivial property, Lp is :
a) infinite
b) decidable
c) undecidable
d) none of the mentioned
4. Which of the following set of computable functions are decidable?
a) The class of computable functions that are constant, and its complement
b) The class of indices for computable functions that are total
c) The class of indices for recursively enumerable sets that are cofinite
d) All of the mentioned
5. Which of the following statements are undecidable?
For a given Turing Machine M,
a) does M halt on an empty input tape
b) does M halt for anly inputs at all?
c) is L(M) regular? Context free? Turing decidable?
d) all of the mentioned
6. Post Correspondence problem is
a) decidable decision problem
b) undecidable decision problem
c) not a decision problem
d) none of the mentioned
8. PCP stands for?
a) Post Correspondence Problem
b) Post Corresponding Problem
c) Pre Correspondence problem
d) None of the mentioned
10. Consider three decision problem A, B, C. A is decidable and B is not. Which of the following
is a correct option?
a) C is undecidable if C is reducible to B
b) C is undecidable if B is reducible to C
c) C is decidable if A is reducible to C
d) C is decidable if C is reducible to B’s complement.
4. Which of the following remarks the given statement?
Statement: Any function whose values can be computed by an algorithm, can be computed by a
Turing machine.
a) Smn theorem
b) Structured Program theorem
c) Church-Turing thesis
d) None of the mentioned
5. Which of the following can be used to simulate any turing machine?
a) Finite State Automaton
b) Universal Turing Machine
c) Counter machines
d) All of the mentioned

Q. Church’s Thesis supports

A. a turing machine as a general-purpose computer system
B. a turing machine an algorithm and an algorithm as a turing machine
C. both tm is an general-purpose computer and tm is an algorithm and vice-versa are correct
D. none of them is correct

The class of recursively ennumerable language is known as:

A) Turing Class
B) Recursive Languages
C) Universal Languages
D) RE

.Which of the following statements are false?

A) Every recursive language is recursively ennumerable
B) Recursively ennumerable language may not be recursive
C) Recursive languages may not be recursively ennumerable
D) None of the mentioned
Choose the correct option:
Statement: If L1 and L2 are recursively enumerable languages over S, then the following is/are
recursively enumerable.
A) L1 U L2
B) L2 ∩ L2
C) Both (A) and (B)
D) None of the mentioned
If L is a recursive language, L’ is:
A) Recursive
B) Recursively Enumerable
C) Both (a) and (b)
D) None of the mentioned
Choose the appropriate option:
Statement: If a language L is recursive, it is closed under the following operations:
A) Union
B) Intersection
C) Complement
D) All of the mentioned
A recursively ennumerable language L can be recursive if:
A) L’ is recursively ennumerable
B) Every possible sequence of moves of T, the TM which accept L, causes it to halt
C) Both (a) and (b)
D) None of the mentioned
15. If a language is recursive then it is called ………………
A) Undecidable language
B) Decidable language
C) Enumerable language
D) None of Above
16. . If a language is not recursive then it is called ………………
A) Undecidable language
B) Decidable language
C) Enumerable language
D) None of Above
17. The class of solvable problems is known as
A) Decidable problems.
B) Undecidable problems
C) Intractable problems
D) None of Above
18. The …………………. are the class of problems that can be solved within polynomial time.
A) Decidable problems.
B) Undecidable problems
C) Intractable problems
D) None of Above
19. The undecidable problems about turing machine is given by …………….
A) Decidable problems.
B) Undecidable problems
C) Intractable problems
D) Halting problems
20. For every input (t, dT ) to M1 if T halt for input t, M1 also halts which is called ………………
A) Finite halt
B) Accept halt
C) Reject halt
D) None of Above
21. If T does not halt for input t then M1 will halt which is called …………
A) Finite halt
B) Accept halt
C) Reject halt
D) None of Above
22. Intersection of two recursive or Turing decidable language is ………………
A) Always recursive
B) Always non-recursive
C) May be recursive, may not be recursive
D) None of Above
23. Consider the language L = {G, w | w is in L(G)}, where G is an arbitrary context free
grammar and w is an arbitrary string. L is ……………..
A) Recursive
B) Recursively enumerable but non-recursive
C) Non-recursively enumerable
D) None of Above
24. If G is context sensitive grammar, then L(G) is ………………
A) Always recursive
B) Recursive enumerable but non-recursive
C) May be recursive
D) None of Above
25) If L can be generated in canonical order then L is : …………………
A) Recursive
B) Recursively enumerable but non-recursive
C) Non-recursively enumerable
D) None of Above
26) L = {an bn cn | n >= 1 } , is
A) Recursive
B) Recursively enumerable but non-recursive
C) Non-recursively enumerable
D) None of Above

Which of the following is undecidable.

a. TM prints a particular symbol ‘C’ on the tape.
b. TM computes a function
c. Both
d. None of Above
The solution for the PCP is
a. The sequence of integers whose strings are same from both sets.
b. The sequence of integers whose strings are different
c. both
d. None of the Above
The PCP having no solution is called
a. undecidability of PCP
b. Decidability of PCP
c. Semi Decidability of PCP
d. None of the Above
Sr.no Question Answer

1 Which of the following is not a part of 5-tuple d

finiteautomata?

a) Input alphabet b) Transition function c) Initial State d)

Output Alphabet

2 Dead state may be required in which of the following? c

(a) FA
(b) NFA
(c) DFA
(d) All of these

3 The output alphabet can be represented as: b

a) δ b) ∆ c) ∑ d) None of the mentioned

5 Given: ∑= {a, b}L= {xϵ∑*|x is a string combination}∑4 b

represents which among the following?

a) {aa, ab, ba, bb} b) {aaaa, abab, ε, abaa, aabb} c) {aaa, aab,
aba, bbb} d) All of the mentioned

4 The number of elements in the set for the Language a

L={xϵ(∑r) *|length if x is at most 2} and ∑={0,1} is

a) 7 b) 6 c) 8 d) 5

6 Consider NFA which starts with a and end with b ,then total d
number of states required in NFA are:
a)2 b)1 c)4 d)3

7 Given an arbitrary non-deterministic finite b

automaton (NFA) with N states, the maximum
number of states in an equivalent minimized DFA is
at least.
a) N^2
(b) 2^N
(c) 2N
(d) N!
8 Which of the following language is generated by given DFA d
 a)starts with 1 and ends with 0
b)starts with 1 ends with 1
c)containing 00 as substring
d)containing three consecutive zeros

9 Given the language L = {ab, aa, baa}, which of the c

following strings are in L*?
….1) abaabaaabaa
….2) aaaabaaaa
….3) baaaaabaaaab
….4) baaaaabaa
(A) 1, 2 and 3
(B) 2, 3 and 4
(C) 1, 2 and 4
(D) 1, 3 and 4
Explanation:Any combination of strings in set {ab, aa,
baa} will be in L*.
….1) “abaabaaabaa” can be partitioned as a
combination of strings in set {ab, aa, baa}. The
partitions are “ab aa baa ab aa”
….2) “aaaabaaaa” can be partitioned as a combination
of strings in set {ab, aa, baa}. The partitions are “aa ab
aa aa”
….3) “baaaaabaaaab” cannot be partitioned as a
combination of strings in set {ab, aa, baa}
….4) “baaaaabaa” can be partitioned as a combination
of strings in set {ab, aa, baa}. The partitions are “baa
aa ab aa”
10 1) The lexical analysis for a modern language such A
as Java needs the power of which one of the
following machine models in a necessary and
sufficient sense?
(A) Finite state automata
(B) Deterministic pushdown automata
(C) Non-deterministic pushdown automata
(D) Turing machine
 Lexical analysis is the first step in compilation. In lexical
analysis, program is divided into tokens. Lexical
analyzers are typically based on finite state automata.
Tokens can typically be expressed as different regular
expressions:
An identifier is given by [a-zA-Z][a-zA-Z0-9]*
The keyword if is given by if.
Integers are given by [+-]?[0-9]+.
11 4) Match all items in Group 1 with correct options B
from those given in Group 2.
Group 1 Group 2
P. Regular expression 1. Syntax
analysis
Q. Pushdown automata 2. Code
generation
R. Dataflow analysis 3. Lexical
analysis
S. Register allocation 4. Code
optimization
(A) P-4. Q-1, R-2, S-3
(B) P-3, Q-1, R-4, S-2
(C) P-3, Q-4, R-1, S-2
(D) P-2, Q-1, R-4, S-3
12 Moore Machine is an application of: b

a) Finite automata without input b) Finite automata with output c)

Non Finite automata with output d) None of the mentioned

13 In Moore machine is of length n then the output string b

length will be

A. n B. n+1 C. n + 2 D. n + n

14 Find the applications of Automata. D

(A) lexical analyzer of a typical compiler
(B) Software for scanning large bodies of text such as collection
of web pages
(C) Software for verifying systems of all types that have finite
number of states such
as communication protocols
(D) All of above

15 List out important notations or structural c

 representation of automata
(A) Grammars
(B) Regular expressions
(C) Both of above
(D) None of the mentioned

16 List out types of Finite state system c

(A) Deterministic Finite Automata and NonDeterminstic
Finite Automata
(B) Moore Machine and Mealy Machine
(C) Both of above
(D) None of them

17 In finite automata, Find the minimum number of states A

required to accept string end
with 101.
(A) 4
(B) 3
(C) 2
(D) can't be represented

18 Which is true about comparision of NFA and DFA B

(A) NFA and DFA have equal number of states for the same
regular language .
(B) NFA allow more than one transition for input symbol
from state but DFA allow
only one transition.
(C) NFA is more powerfull than DFA.
(D) All of the above mentioned

19 The set of all strings over the alphabet S = {a, b} A

(including e) is denoted by
A. (a + b)*
B. (a + b)+
C. a+b+
D. a*b*
ANSWER:A

20 B
The finite automata accept the following language------

A. context free language B. regular language

C. context sensitive language D. all of the above

 21)Reverse of a DFA can be formed by----

A. using PDA

B. making final state as non-final

C. making final as starting state and starting state as

final state

D. None of the above.

(C answer)

22 C
Which among the following is the missing transition in the given
DFA?

L= {xϵ∑= {a, b} | x starts with a and ends with b}

A. δ (q0, a) =q0
B. δ (F, a) =D
C. δ (F, a) =q1
D. δ (q1, a) =D

23 A
Which of the following does the given Mealy machine represents?
 A. 1’s Complement B.2’s Complement

C. 10’s Complement D. 9’s Complement

24 c
Two finite state machines are said to be equivalent if they-----

A. Have the same number of edges

B. Have the same number of states

C. Recognize the same set of tokens

D. Have the same number of states and edges

25 A
Which of the following will not be accepted by the following
DFA?

A. ababaabaa
B. abbbaa C. abbbaabb D. abbaabbaa
 MCQS on REGULAR EXPRESSION

1 Which among the following are incorrect regular identities? d

a) εR=R
b) ε*=ε
c) Ф*=ε
d) RФ=R

2 The string 1101 does not belong the set represented by: C and D
A. 110*(0+1)
B. 1(0+1)*101
C. (10)*(01)*(00+11)*
D. (00+(11)*0)*
Answer: C & D Explanation:- R.E of option C won’t generate 1101
as you can see the language will contain L(C) =
{epsilon,10,1010,1001,0101,00,11,0011,1100,………..} Also, R.E of
option D has ‘1’ but here two ’11’ are together hence it’s impossible
to generate 1101. L(D) =
{Epsilon,0,00,110,11110,11000,…………….} Here Option (C) and
(D) both are correct.

3 Regular expressions are closed under D

A. Union
B. Intersection
C. Kleen star
D. All of the mentioned

4 Regular expression for all the strings starts with ab and ends c
with ba is
A. aba*b*ba
B. ab(ab)*ba
C. ab(a+b)*ba
D. All of above
Answer: C Explanation:- Starts with ab then any number of a or b
and ends with ba.

5 A language is regular if and only if , A

:a) accepted by DFA b) accepted by PDA c) accepted by LBA d)
accepted by Turing machine

A language is regular if and only if it is accepted by a finite

automation'
If a language can be represented by a regular expression, it is
accepted by a non deterministic finite automaton.
Regular language in finite automata:-
A regular language satisfies the following equivalent properties: it
is the language of a regular expression (by the above definition) it
is the language accepted by a nondeterministic finite automaton
(NFA) it is the language accepted by a deterministic finite
 automaton (DFA) it can be generated by a regular grammar.
A regular language is a formal language that can be expressed
using a regular expression, in the strict sense of the latter notion
used in theoretical computer science.

6 Which of the following identity is wrong? D

A. R + R = R
B. (R*)* = R*
C. R = R = R ɛ ɛ
D. ØR = RØ = RR*
Answer: D
Explanation: ØR = RØ but not equal to RR*

7 13. Let the class of language accepted by finite state machine D

be L1 and the class of languages represented by regular
expressions be L2 then
LA. L1=L2
B.L1>=L2
C. L1 U L2
D. L1=L2
Answer: D Explanation: Finite state machine and regular
expression have same power to express a language.

8 Regular expression {0,1} is equivalent to D

a) 0 U 1 b) 0 / 1 c) 0 + 1 d) All of the mentioned
Explanation: All are equivalent to union operation.

9 While applying Pumping lemma over a language, we consider C

a string x that belong to L and fragment it into _________
parts.
A.2
B.5
C.3
D.6
Answer: C Explanation: Pumping Lemma for Regular Languages
For any regular language L, there exists an integer n, such that for
all x L with |x| ≥ n, there ∈ exists u, v, w Σ , such that x = uvw, and
∈ ∗ (1) |uv| ≤ n (2) |v| ≥ 1 (3) for all i ≥ 0: uv i w L ∈

10 Consider following regular expression D

i) (a/b)* ii) (a*/b*)* iii) ((ϵ/a)b*)* Which of the following statements
is correct:
a) i,ii are equal and ii,iii are not b) i,ii are equal and i,iii are not c)
ii,iii are equal and i,ii are not d) all are equal

Explanation :(D)All are equivalent to (a+b)*.

11 What is the language generated by this regular expression? D
a(a+b)*a
A. Always starts with b
B. Can have any number of ba and ab
C. Cannot have 2 b's together.
D. Starts and end with same symbol
Answer: D Explanation: a(a+b)*a Starts and end with same symbol

12 Which of the technique can be used to prove that a language b

is non regular?
a) Ardens theorem b) Pumping Lemma c) Ogden’s Lemma d)
None of the mentioned

13 If we select a string w such that x L, and x= x=uvw. Which of B

the following portions cannot be ∈ an empty string?
A. u
B. v
C. w
D. all of the mentioned
Answer: B Explanation: in uvw , v can not be empty

14 Which of the following language regular? b

a) {aibi|i>=0} b) {aibi|0<i<5} c) {aibi|i>=1} d) None of the mentioned

Answer:b

Here, i has limits i.e. the language is finite, contains few

elements and can be graphed using a deterministic finite
automata. Thus, it is regular. Others can be proved non
regular using Pumping lemma.

15 Regular expression (x/y)(x/y) denotes the set B

A.{xy,xy}
B. {xx,xy,yx,yy}
C. {x,y}
D. {x,y,xy}
Answer: B Explanation: Possible strings constructed from given
RE is {xx,xy,yx,yy}

16 The regular expression denote a language comprising all D

possible strings of even length over the alphabet (0, 1)
A. 1 + 0(1+0)*
 B. (0+1) (1+0)*
C. (1+0)
D. (00+0111+10)*
Answer: D Explanation: D generates all strings with even length.

17 A CFG is ambiguous if B
a) It has more than one rightmost derivations
b) It has more than one leftmost derivations
c) No parse tree can be generated for the CFG
d) None of the mentioned

18 Which of the following regular expression identity is true? C

A. (r+s)*=r*
B. (r+s)*= r*+s*
C. (r*s*)*=(r+s)*
D. r* s*= r *+s*
Answer:C Explanation: L(LHS)= {Є, r, s ,rr ,ss ,rs ,rrs ,rrss rss, …..
} L(RHS)= {Є ,r, s, rr , ss ,rs , rrs , rrss, rss,,,} L(LHS =L(RHS)

19 A push down automaton employs ________ data structure. D

a) Queue b) Linked List
c) Hash Table d) Stack

20 Push down automata accepts _________ languages.

a) Type 3 b)Type 2
c) Type 1 d)Type 0

21 (0+ε) (1+ε) represents A

A. {0, 1, 01, ε}
B. {0, 1, ε}
C. {0, 1, 01 ,11, 00, 10, ε}
D. {0, 1}
Answer: A
Explanation: The regular expression is fragmented and the set of
the strings eligible is formed. ‘+’ represents union while ‘.’
Represents concatenation. {0, 1, 01, ε}

22 Regular Expression denote precisely the ________ of Regular A

Language.
A. Class
B. Power Set
C. Super Set
D. None of the mentioned
Answer: A Explanation: Regular Expression denote precisely the
class of regular language. Given any regular expression, L(R) is a
regular language. Given any regular language L, there is a regular
expression R, such that L(R)=L.

23 (a+b)* is equivalent to B
A. b*a* B. (a*b*)* C. a*b* D. none of the mentioned
Answer: B Explanation: (a+b)* = (a*b*)*
24 Concatenation Operation refers to which of the following set B
operations:
A. Union
B. Dot
C. Kleene
D. Two of the options are correct
Answer: B Explanation: Two operands are said to be performing
Concatenation operation AB = A•B

25 Language accepted by the given RE is explained as a*b +b*a B

A. Any number of a's are followed by ba or Any number of b's are
followed by ab
B. Any number of a's are followed by b or Any number of b's are
followed by a
C. Any number of aa's are followed by b or Any number of ba's
are followed by a
D. Any number of aba's are followed by b or Any number of b's
are followed by a
Answer: B Explanation:- Language accepted by the given RE is
explained as a*b +b*a is Any number of a's are followed by b or
Any number of b's are followed by a

MCQs on GRAMMAR

1 The context free grammar S → SS | 0S1 | 1S0 | generates ɛ A

A. Equal number of 0’s and 1’s
B. Unequal number of 0’s and 1’s
C. Any number of 0’s followed by any number of 1’s
D. None of these
Ans: A Explanation:
S->SS
S->0S1S
S->0S11S0
S->0110.

2 Which type of grammar is it? S → abS S → a A

a) Right Linear Grammar b) Left Linear Grammar c) Right & Left
Linear Grammar d) None of the mentioned

3 A context free grammar G is in Chomsky normal form if B

every production is of the form
A. A → BC or A → A
B. A → BC or A → a
C. A → BCa or B → b
D. None of these
Ans: B Explanation: In formal language theory, a context-free
grammar, G, is said to be in Chomsky normal form if all of its
production rules are of the form: A → BC, or. A → a

4 A context free language is called ambiguous if C

A. It has two or more leftmost derivations for some terminal string
є L (G) ѡ
B. It has two or more rightmost derivations for some terminal
string є L (G) ѡ
 C. Both (a) and (b)
D. None of these
Ans: C Explanation: A context free language is called ambiguous
if there is no unambiguous grammar to define that language and
it is also called inherently ambiguous Context Free Languages. A
context free grammar is called ambiguous if there exists more
than one LMD or more than one RMD for a string which is
generated by grammar. There will also be more than one
derivation tree for a string in ambiguous grammar

5 What is the highest type number which can be applied to the C

following grammar ? S —> Aa, A —> Ba, B —> abc
A. Type 0
B. Type 1
C. Type 2
D. Type 3
Ans: C Explanation: Type-2 grammars generate context-free
languages. The productions must be in the form A -> γ where A N
(Non terminal) and γ (T N)* (String of terminals and non- ∈ ∈ ∪
terminals).

6 Consider the CFG with {S,A,B) as the non-terminal alphabet, C

{a,b) as theterminal alphabet, S as the start symbol and the
following set of productionrules
S --> aB
S --> bA
B --> b
A --> a
B --> bS
A --> aS
B --> aBB
A --> bAAWhich of the following strings is generated by the
grammar?
A. aaaabb
B. aabbbb
C. aabbab
D. abbbba
Explanation: Given below production rules.
S --> aB S --> bA B --> b A --> a B --> bS A --> aS B --> aBB A
--> bAA We can derive aabbab using below sequence
S -> aB [Using S --> aB] -> aaBB [Using B --> aBB] -> aabB
[Using B --> b] -> aabbS [Using B --> bS] -> aabbaB [Using S -->
aB] -> aabbab [Using B --> b]

7 In context to the process of removing useless symbols, C

which of the following is correct?
A. We remove the Nullable variables
B. We eliminate the unit productions
C. We eliminate products which yield no terminals
D. All of the mentioned
Ans: C
Explanation: In the process of removal of useless symbols, we
want to remove productions that can never take part in any
derivation. Useless symbols are symbols which don't generate
 string of terminals from start symbol. or they don't take part in
derivation process

8 The Grammar can be defined as: G=(V, ∑, p, S) In the given B

definition, what does S represents?
A. Accepting State
B. Starting Variable
C. Sensitive Grammar
D. None of these
Answer: B Explanation: G=(V, ∑, p, S), here V=Finite set of
variables, ∑= set of terminals, p= finite productions, S= Starting
Variable.

9 Which of the following statement is false? D

A. Context free language is the subset of context sensitive
language
B. Regular language is the subset of context sensitive language
C. Recursively enumerable language is the super set of regular
language
D. Context sensitive language is a subset of context free
language
Answer: D Explanation: Every regular language can be produced
by context free grammar and context free language can be
produced by context sensitive grammar and so on.

10 Which among the following cannot be accepted by a regular D

grammar?
A. L is a set of numbers divisible by 2
B. L is a set of binary complement
C. L is a set of string with odd number of 0
D. L is a set of 0n 1 n
Answer: D Explanation: There exists no finite automata to accept
the given language i.e. 0n 1 n . For other options, it is possible to
make a dfa or nfa representing the language set.

11 Which of the expression is appropriate? For production p: C

a->b where a V and b _______ ∈ ∈
a) V
b) S
c) (V+∑)*
d) V+ ∑
Answer: C Explanation: According to the definition, the starting
variable can produce another variable or any terminal or a
variable which leads to terminal.

12 For S->0S1|e for ∑={0,1}*, which of the following is wrong for D

the language produced?
a) Non regular language
b) 0n 1 n | n>=0
c) 0n 1 n | n>=1
d) None of the mentioned
Answer: D Explanation: L={e, 01, 0011, 000111, ……0n 1 n }. As
epsilon is a part of the set, thus all the options are correct
implying none of them to be wrong.
13 Are ambiguous grammar context free? A
a) Yes b) No
Answer: A Explanation: A context free grammar G is ambiguous
if there is atleast one string in L(G) which has two or more distinct
leftmost derivations.

14 Unrestricted grammar is also called_______ Grammar D

A. Type 3
B. Type 2
C. Type 1
D. Type 0
Answer: D Explanation: Type 0 grammar does not have any
restriction about productions.

15 . A CFG consist of : D
A. Set of Nonterminals
B. Start symbol
C. Set of terminals
D. All of these
Answer: D Explanation: G= {V, T, P, S} variables, Terminals,
Productions, start symbol

16 A grammar in which V represents A

A. Set of Nonterminal
B. Start symbol
C. Set of terminals
D. Production
Answer: A Explanation: V is set of nonterminals or variable

17 Context free grammar is called Type 2 grammar because of C

______________ hierarchy.
A. Greibach
B. Backus
C. Chomsky
D. None of the mentioned
Answer: C Explanation: Chomsky hierarchy defines 4 types of
grammar.

18 CFG for a+ D
A. S -> aS | a | ^
B. S → aS | b
C. S → aS | a
D. None of these
Answer: D
Explanation: S → aS | a L={a,aa, aaa, aaaa, ….}

19 S->aSa|bSb|a|b; The language generated by the above C

grammar over the alphabet {a,b} is the set of
A. All length palindrome
B. Even length palindrome
C. Odd length palindrome
D. String starts and end with different character
 Answer: C Explanation: L={a, b, abb, bbb, aaa, aba, bab, ….}

20 A CFG is ambiguous if D
A. It has more than one rightmost derivations
B. It has more than one leftmost derivations
C. No parse tree can be generated for the CFG
D. Both A & B
Answer: D Explanation: A context free grammar is ambiguous if it
has more than one parse tree generated or more than one leftmost
derivations. An unambiguous grammar is a context free grammar
for which every valid string has a unique leftmost derivation.

21 Which of the following are always unambiguous? A

A. Deterministic Context free grammars
B. Non-Deterministic Regular grammars
C. Context sensitive grammar
D. None of the mentioned
Answer : A Explanation: Deterministic CFGs are always
unambiguous , and are an important subclass of unambiguous
CFGs; there are non-deterministic unambiguous CFGs, however.

22 A CFG is not closed under D

A. Dot operation
B. Union Operation
C. Concatenation
D. Iteration
Answer: D Explanation: The closure property of a context free
grammar does not include iteration or kleene or star operation.

23 Non-Linear grammar has two non-terminals on the right-hand A

side.
A. True B. False
Answer: A Explanation: The above stated grammar is non-linear
because it has two non-terminals on the right-hand side.

24 Linear grammar has more than one non-terminal on the B

right-hand side.
A. True B. False
Answer: B Explanation: Grammar is linear because no rule has
more than one non terminal on the right hand side.

25 In Right-Linear grammars, all productions have the form: A → A

xB.
A. True B. False
Answer: A Explanation: Right-Linear grammars, following are the
form of productions: A → xB or A → x where x is some string of
terminals.

26 Regular Grammars generate Regular Languages. A

A. True B. False
Answer: A Explanation: Language generated by regular grammar
is called regular languages. 38. Match the following :

27 Which one of the following statement is false? D

A. Context-free languages are closed under union.
 B. Context-free languages are closed under concatenation.
C. Context-free languages are closed under intersection.
D. Context-free languages are closed under Kleene closure.
Answer: D Explanation: Context-free languages are closed under
Kleene

28 The production of the form A-> B , where A and B are non C

terminals is called
A. Null production
B. Greibach Normal Form
C. Unit production
D. Chomsky Normal Form
Answer: C Explanation: A unit production is a production A -> B
where both A and B are non-terminals. Unit productions are
redundant and hence should be removed.

29 The closure property of context free grammar includes : D

A. Kleene operation
B. Union
C. Concatenation
D. All of the mentioned
Answer: D
Explanation: CFL's are closed under union, concatenation, and
Kleene closure. Also, under reversal, homomorphisms and inverse
homomorphisms. But not under intersection or difference. Let L
and M be CFL's with grammars G and H, respectively.

30 CFG is not closed under C

A. Kleene
B. Concatenation
C. Complement
D. Union
Answer: C
Explanation: : If L1 and If L2 are two context free languages, their
intersection L1 ∩ L2 need not be context free.
For example, L1 = { an b n c m | n >= 0 and m >= 0 } and L2 = (am
b n c n | n >= 0 and m >= 0 } L3 = L1 ∩ L2 = { an b n c n | n >= 0 }
need not be context free.
L1 says number of a’s should be equal to number of b’s and L2
says number of b’s should be equal to number of c’s. Their
intersection says both conditions need to be true, but push down
automata can compare only two. So it cannot be accepted by
pushdown automata, hence not context free. Similarly,
complementation of context free language L1 which is ∑* – L1,
need not be context free.

31 Every grammar in Chomsky Normal Form is: B

A. Regular
B. Context free
C. Context sensitive
D. Unrestricted
Answer: B

32 While converting the context free grammar into chomsky D

 normal form, which of the following is necessary
A. Elimination of null production
B. Elimination of unit production
C. Elimination of epsilon production
D. All of these
Answer: D Explanation: Simplification of CFG is required in CNF

33 The variable which produces epsilon is called: B

A. Empty variable
B. Nullable variable
C. Terminal
D. All of the mentioned
Answer: B Explanation: Removal of Null Productions. In a CFG, a
non-terminal symbol 'A' is a nullable variable if there is a
production A → ε

34 .G = {S->SS, S->ab, S->ba, S->?} is the context free grammar A

whose statements are given below:
a. G is ambiguous
b. G produces all strings with equal number of a’s and b’s.
c. Deterministic PDA accepts G
Which of the following statement is true about G?
A. a, b, c all are true
B. Only and b are true
C. Only b and c are true
D. Only a is true
Answer: A Explanation: G is ambiguous , G produces all strings
with equal number of a’s and b’s. And Deterministic PDA accepts
G

35 Which among the following is the root of the parse tree? D

A. Production P
B. Nonterminal V
C. Terminal T
D. Starting symbol S
Answer: D Explanation: Starting symbol is the root of parse tree

36 _______is the graphical representation of a grammar. C

A. Binary tree
B. Red black tree
C. Parse tree
D. None of the mentioned
Answer: C Explanation:Parse tree shows graphical representation
of given grammar

Push Down Automata mCqs

1 A PDA machine configuration (p, w, y) can be correctly A

represented as:
a) (current state, unprocessed input, stack content)
b) (unprocessed input, stack content, current state)
c) (current state, stack content, unprocessed input) a
d) none of the mentioned
 Explanation
A machine configuration is an element of KΣ*I.
(p,w,y) = (current state, unprocessed input, stack content).

2 The transition a Push down automaton makes is additionally A

dependent upon the:

a) stack

b) input tape

c) terminals

d) none of the mentioned

Explanation:
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

3 Push down automata accepts _________ languages. B

a) Type 3 b)Type 2
c) Type 1 d)Type 0

4 A push down automaton employs ________ data structure. d

a) Queue b) Linked List
c) Hash Table d) Stack

5 If the PDA does not stop on an accepting state and the stack is A
not empty, the string is:

a) rejected

b) goes into loop forever

c) both (a) and (b)

d) none of the mentioned

Explanation:
To accept a string, PDA needs to halt at an accepting
state and with a stack empty, else it is called rejec PDA M, we can
construct a PDA M' that accepts the same language as M, by both
 acceptance criteria.

6 A push down automata is different than finite automata by: A

(A) Its memory
(B) Number of states
(C) Both (a) and (b)
(D) None of these
Explanation: Finite automata don’t have any memeory to store
data

7 PDA is more powerful than C

(A) Turing machine
(B) Multi tape Turing machine
(C) Finite automata
(D) All of these
Answer : C Explanation: A PDA is more powerful than FA. Any
language which can be acceptable by FA can also be acceptable
by PDA. PDA also accepts a class of language which even cannot
be accepted by FA. Thus PDA is much more superior to FA.

8 Which of the following are the actions that operates on stack D

top?
(A) Pushing
(B) Updating
(C) Popping
(D) All of the mentioned A
nswer : D Explanation: in PDA all operation are opertaes on top of
the stack(ToS)

9 State true or false: A

Statement: For every CFL, G, there exists a PDA M such that
L(G) = L(M) and vice versa.
a) true b) false
Answer: a Explanation: There exists two lemma’s such that: a)
Given a grammar G, construct the PDA and show the equivalence
b) Given a PDA, construct a grammar and show the equivalence

10 The instantaneous PDA is has the following elements D

a) State
b) Unconsumed input
c) Stack content
d) All of the mentioned
Answer: d Explanation: The instantaneous description of a PDA is
represented by 3 tuple: (q,w,s) where q is the state, w is the
unconsumed input and s is the stack content.

11 A push down automata can represented using: D

a) Transition graph
b) Transition table
c) ID
d) All of the mentioned
Answer: d Explanation: Yes, a PDA can be represented using a
transition diagram, transition table and an instantaneous
description.
12 State true or false: Statement: Every context free grammar A
can be transformed into an equvalent non deterministic push
down automata.
a) true b) false
Answer: a Explanation: Push down automata is the automaton
machine for all the context free grammar or Type 2 languages.

13 A push down automata is said to be _________ if it has D

atmost one transition around all configurations.
a) Finite
b) Non regular
c) Non-deterministic
d) Deterministic
Answer: d Explanation: DPDA or Deterministic Push down
automata has atmost one transition applicable to each
configuration

14 A pushdown automata can be defined as: (Q, ∑, G, q0, z0, A, D

d) What does the symbol z0 represents?
a) an element of G
b) initial stack symbol
c) top stack alphabet
d) all of the mentioned
Answer: d Explanation: z0 is the initial stack symbol, is an element
of G. Other symbols like d represents the transition function of the
machine.

15 23 Which of the operations are eligible in PDA? A,D both

a) Push b) Delete c) Insert d) Pop
Answer: a, d Explanation: Push and pop are the operations we
perform to operate a stack. A stack follows the LIFO principle,
which states its rule as: Last In First Out.

16 A string is accepted by a PDA when C

a) Stack is empty
b) Acceptance state
c) Both (a) and (b)
d) None of the mentioned
Answer: c Explanation: When we reach the acceptance state and
find the stack to be empty, we say, the string has been accepted
by the push down automata.

17 The following move of a PDA is on the basis of: C

a) Present state b) Input Symbol c) Both (a) and (b) d) None of
the mentioned Answer: c Explanation: The next operation is
performed by PDA considering three factors: present state,symbol
on the top of the stack and the input symbo

18 A language is accepted by a push down automata if it is C

: a) regular
b) context free
c) both (a) and (b)
d) none of the mentioned
 Answer: c
Explanation: All the regular languages are the subset to context
free languages and thus can be accepted using push down
automata.

19 A DPDA is a PDA in which: A

(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: A Explanation: DPDA is a deterministic PDA, in which
one state has only one outgoin transitionon one input

20 The push down automata accepts the input string in form of C

(A) Finial state
(B) Empty stack
C) Both (a) and (b)
(D) None of these
Answer: C
Explanation: PDA canaccept by two way:1)acceptance of pda by
dinal state & 2) acceptance of pda by empty stack

21 Limitation of PDA can overcome by: C

(A) Mealy machine
(B) Moore machine
(C) Turing machine
(D) FA
Answer: C Explanation:Limitation of PDA can overcome by TM
as TM tape head can move both direction

22 Which of the following option resembles the given PDA? A

a. {0^n1^n|n>=0}
b. {0^n1^2n|n>=0}
c. {0^2n1^n|n>=0}
d. None of the mentioned
Answer: a

23 The moves in the PDA is technically termed as: A

a) Turnstile b) Shifter c) Router d) None of the mentioned
Answer: a
 Explanation: A turnstile notation is used for connecting pairs od
ID’s taht represents one or many moves of a PDA.

Turing machine mcqs

1 What is the reason behind a Turing machine is more 3

powerful than finite state machine FSM?
1. Turing machine head movement is continued to one direction.
2. Turing machine head moment is in both directions i.e. left
moment and right moment as well.
3. Turing machine has capability remember arbitrary long
sequence of input string.
4. All are correct.
Ans: 3

2 If Turing machine accepts all the words of the languages L 1

and rejects or loops for other words, which are not in L, then
L is said to be
1. Recursive enumerable
2. Recursive
3. Context Free Language (CFL)
4. None of them Ans: 1

3 If a Turing machine halts for each and every world of a 3

language L and rejects other, then L is said to be
1. Recursive enumerable
2. Recursive
3. Context Free Language
4. None of these
Ans: 3

4 Universal Turing machine (UTM) influenced the concepts of 4

1. Computability
2. Interpretive implementation of programming language
3. Program and data is in same memory
4. All are correct

5 A universal Turing machine is a 1

1. Reprogrammable Truing machine
2. Two-tape Turing machine
3. Single tape Turing machine 4. None of them
Ans: 1

6 Church’s Thesis supports 3

1. A Turing machine as a general-purpose computer system
2. A Turing machine an algorithm and an algorithm as a Turing
machine
3. Both TM is an general-purpose computer and TM is an
algorithm and vice-versa are correct
4. None of them is correct Ans: 3
7 B
A language L is said to be ____________ if there is a turing
machine M such that L(M)=L and M halts at every point?

a) Turing acceptable b) decidable

c) undecidable d) none of the mentioned

8 A turing machine with several tapes in known as: a

a) Multi-tape turing machine b) Poly-tape turing
maching
c)Universal turing machine d) All of the mentioned

9 Which of the following can be used to simulate any turing b

machine? a) Finite State Automaton b) Universal Turing
Machine c) Counter machines d) All of the mentioned

10 A turing machine is a d
a) real machine b) abstract machine c) hypothetical machine
d) more than one option is correct
A turing machine is abstract or hypothetical machine thought
by mathematician Alan Turing in 1936 capable of simulating
any algorithm, however complicated it is.

11 Which is correct regard an off-line Truing machine? 1

1. An offline Turing machine is a special type of multi-tape Turing
machine
2. An offline Turing machine is a kind of multi-tracks Truing
machine
3. An offline Turing machine is a kind of single-track Turing
machine
4. None of them

12 The ability for a system of instructions to simulate a Turing a

Machine is called _________ a) Turing Completeness b)
Simulation c) Turing Halting d) None of the mentioned

Explanation: Turing Completeness the ability for a system of

instructions to simulate a Turing machine. A programming
language that is Turing complete is theoretically capable of
expressing all tasks accomplishable by computers; nearly all
programming languages are Turing complete

13 Given S = {a, b}, which one of the following sets is not 2

countable?
 1. The set all strings over ∑
2. The set of all language over ∑
3. The set of all binary strings
4. The set of all languages over ∑ accepted by Turing machines

14 Turing machine can be represented using the following tools: D

a) Transition graph b) Transition table c) Queue and Input tape d)
All of the mentioned

15 Match the following List-I with List-II and select the correct 2
answer using the codes given below the lists
List-I List-II
A. Laxical analyser 1. Pushdown automata
B. Parsing 2. Turing machine
C.Computing 3. Finite state automata
D.Non-deterministic
butfinite machine 4. Non-deterministic FA

0ptions
1. A-3, B-4, C-2, D-1
2. A-3, B-1, C-2, D-4
3. A-3, B-1, C-4, D-2
4. A-3, B-2, C-1, D-

decidable /undecidable mcqs

1 Halting problem is an example for? B

a) decidable problem b)undecidable problem c) complete problem
d) trackable problem
explanation:halting problem by alan turing cannot be solved by
any algorithm.
hence, it is undecidable.

2 Consider three decision problem A, B, C. A is decidable and B B

is not. Which of the following is a correct option?
a)C is undecidable if C is reducible to B b)C is undecidable if B
is reducible to C
c) C is decidable if A is reducible to C d)All of the above

3 The problems which have no algorithm, regardless of whether B

or not they are accepted by a turing machine that fails to halts
on some input are referred as:

a)Decidable b) Undecidable c) Computable d) None of the

mentioned

Clarification: The problems that can be solved by a turing machine

can divided into two classes:

a) Those that have an algorithm

 b) Intractable problems: Those that are only solved by a turing
machine that may run forever on inputs they do not accept.

4 Linear Bounded Automaton is a: B

a) Finite Automaton
b) Turing Machine
c) Push down Automaton
d) None of the mentioned
Answer: b
Explanation: Linear Bounded Automaton is a type of Turing
Machine where tape is not allowed to move off the portion of the
tape containing the input. It is a Turing machine with limited
amount of memory.

5 Which of the following statement is false? d

a) The union of two recursively enumerable language is

recursively enumerable
b) Let L1 and L2 are two recursive language then the union of L1
and L2 i.e.L1 U L2 is also recursive
c) If a language L and its complement L- are both recursively
enumerable then,L is recursive language
d) None of these

6 Which of the following remarks the given statement? C

Statement: Any function whose values can be computed by an
algorithm, can be computed by a Turing machine.
a) Smn theorem
b) Structured Program theorem
c) Church-Turing thesis
d) None of the mentioned
Answer: c
Explanation: The following conclusion is laid down from the
Church-Turing thesis:
Any function whose values can be computed by an algorithm, can
be computed by a Turing machine. If any real world computer can
be simulated by a turing machine, it is Turing equivalent to a
Turing Machine.

Which of the following does not have left recursions?

A) Chomsky Normal Form
B) Greibach Normal Form
C) Backus Naur Form
D) All of the mentioned
7 What are recursive enumerable languages? b

a) There exists a PDA to accept the languages b) There exists a

Turing Machine to accept the languages c) There exists a Finite
Automata to accept the languages d) None of the mentioned

8 Post Correspondence problem is B

A : decidable decision problem

B : undecidable decision problem

C : not a decision problem

D : none of the mentioned

Answer : undecidable decision problem

9 When problem is said to be un-decidable? b

a) There exists an algorithm to find answer of the problem is yes
or no.
b) There is no algorithm to find answer of the problem is yes or
no.
c) There is no algorithm to find answer of the problem is yes.
d) There is an algorithm to find answer of the problem is yes.

10 A
Decidable can be taken as a synonym to:

A)Recursive

b) non recursive

c) recognizable

d) none of the mentioned

Answer: a

Clarification: We can refer to languages as 'recursive and

problems as 'decidable. If a language is not recursive, then we call
the problem expressed by that language undecidable.

11 A recursive language is also called A

a) Decidable
b) Undecidable
c) Both (a) and (b)
d) None of these
 lOMoARcPSD|14948590

www.studymaterialz.in

f) Kleene closure

UNIT II REGULAR EXPRESSIONS AND LANGUAGES

TOPIC 1: Regular Expressions

1. L is a regular Language if and only If the set of classes of IL is finite.
a) Equivalence
b) Reflexive
c) Myhill
d) Nerode
SOLUTION
Answer: a
Explanation: According to Myhill Nerode theorem, the corollary proves the given
statement correct for equivalence classes.
2. A language can be generated from simple primitive language in a simple way if and
only if
a) It is recognized by a device of infinite states
b) It takes no auxiliary memory
c) Both are correct
d) Both are wrong
SOLUTION
Answer: b
Explanation: A language is regular if and only if it can be accepted by a finite
automaton. Secondly, It supports no concept of auxiliary memory as it loses the data
as soon as the device is shut down.
3. Which of the following does not represents the given language?
Language: {0,01}
a) 0+01
b) {0} U {01}
c) {0} U {0}{1}
d) {0} ^ {01}
SOLUTION
Answer: d
Explanation: The given option represents {0, 01} in different forms using set
operations and Regular Expressions. The operator like ^, v, etc. are logical operation
and they form invalid regular expressions when used.
4. According to the given language, which among the following expressions does it
corresponds to?
Language L={xϵ{0,1}|x is of length 4 or
less} a) (0+1+0+1+0+1+0+1)4
b) (0+1)4

17

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

c) (01)4
d) (0+1+ε)4
SOLUTION
Answer: d
Explanation: The extended notation would be (0+1)4 but however, we may allow
some or all the factors to be ε. Thus ε needs to be included in the given regular
expression.
5. Which among the following looks similar to the given expression?
((0+1). (0+1)) *
a) {xϵ {0,1} *|x is all binary number with even length}
b) {xϵ {0,1} |x is all binary number with even length}
c) {xϵ {0,1} *|x is all binary number with odd length}
d) {xϵ {0,1} |x is all binary number with odd
length} SOLUTION
Answer: a
Explanation: The given regular expression corresponds to a language of binary
strings which is of even length including a length of 0.
6. If R represents a regular language, which of the following represents the Venn-
diagram most correctly?

a) An Irregular Set
b) R*
c) R complement
d) R reverse
SOLUTION
Answer: b
Explanation: The given diagram represents the Kleene operation over the Regular
Language R in which the final states become the initial and the initial state becomes
final.
7. The given NFA corresponds to which of the following Regular expressions?

a) (0+1) *(00+11) (0+1) *

b) (0+1) *(00+11) *(0+1) *
c) (0+1) *(00+11) (0+1)
d) (0+1) (00+11) (0+1) *
SOLUTION
Answer: a
Explanation: The transition states shown are the result of breaking down the given
regular expression in fragments. For dot operation, we change a state, for union
(plus) operation, we diverge into two transitions and for Kleene Operation, we apply a
loop.
8. Concatenation Operation refers to which of the following set operations:

18

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

a) Union
b) Dot
c) Kleene
d) Two of the options are correct
SOLUTION
Answer: b
Explanation: Two operands are said to be performing Concatenation operation AB =
A•B = {xy: x ∈ A & y ∈ B}.
9. Concatenation of R with Ф outputs:
a) R
b) Ф
c) R.Ф
d) None of the mentioned
SOLUTION
Answer: b
Explanation: By distributive property (Regular expression identities), we can prove
the given identity to be Ф.
10. RR* can be expressed in which of the forms:
a) R+
b) R-
c) R+ U R-
d) R
SOLUTION
Answer: a
Explanation: RR*=R+ as R+ means the occurrence to be at least once.

TOPIC 2: FA and Regular Expressions

1. What kind of expressions do we used for pattern matching?
a) Regular Expression
b) Rational Expression
c) Regular & Rational Expression
d) None of the mentioned
SOLUTION
Answer: c
Explanation: In automata theory, Regular Expression(sometimes also called the
Rational Expression ) is a sequence or set of characters that define a search pattern,
mainly for the use in pattern matching with strings or string matching.
2. Which of the following do Regexps do not find their use in?
a) search engines
b) word processors
c) sed
d) none of the mentioned

ANSWER: d
19

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

Answer: c
Explanation: It matches the end of a string and not an internal line.The given
segment of code outputs:
Hello
World
is a string that ends with ‘d\n’
10. Conversion of a regular expression into its corresponding NFA :
a) Thompson’s Construction Algorithm
b) Powerset Construction
c) Kleene’s algorithm
d) None of the mentioned
SOLUTION
Answer: a
Explanation: Thompson construction algorithm is an algorithm in automata theory
used to convert a given regular expression into NFA. Similarly, Kleene algorithm is
used to convert a finite automaton to a regular expression.

TOPIC 3: Proving Languages not to be regular

1. Relate the following statement:

Statement: All sufficiently long words in a regular language can have a middle section
of words repeated a number of times to produce a new word which also lies within the
same language.
a) Turing Machine
b) Pumping Lemma
c) Arden’s theorem
d) None of the mentioned
SOLUTION
Answer: b
Explanation: Pumping lemma defines an essential property for every regular
language in automata theory. It has certain rules which decide whether a language is
regular or not.
2. While applying Pumping lemma over a language, we consider a string w that belong
to L and fragment it into parts.
a) 2
b) 5
c) 3
d) 6
SOLUTION
Answer: c
Explanation: We select a string w such that w=xyz and |y|>0 and other conditions.
However, there exists an integer n such that |w|>=n for any wÎL.

22

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

3. If we select a string w such that w∈L, and w=xyz. Which of the following portions
cannot be an empty string?
a) x
b) y
c) z
d) all of the mentioned
SOLUTION
Answer: b
Explanation: The lemma says, the portion y in xyz cannot be zero or empty i.e. |y|>0,
this condition needs to be fulfilled to check the conclusion condition.
4. Let w= xyz and y refers to the middle portion and |y|>0.What do we call the process
of repeating y 0 or more times before checking that they still belong to the language L
or not?
a) Generating
b) Pumping
c) Producing
d) None of the mentioned
SOLUTION
Answer: b
Explanation: The process of repeatation is called pumping and so, pumping is the
process we perform before we check whether the pumped string belongs to L or not.
5. There exists a language L. We define a string w such that w∈L and w=xyz and |w|
>=n for some constant integer n.What can be the maximum length of the substring xy
i.e. |xy|<=?
a) n
b) |y|
c) |x|
d) none of the mentioned
SOLUTION
Answer: a
Explanation: It is the first conditional statement of the lemma that states that
|xy|<=n, i.e. the maximum length of the substring xy in w can be n only.
6. Fill in the blank in terms of p, where p is the maximum string length in L.
Statement: Finite languages trivially satisfy the pumping lemma by having n =
a) p*1
b) p+1
c) p-1
d) None of the mentioned
SOLUTION
Answer: b
Explanation: Finite languages trivially satisfy the pumping lemma by having n equal
to the maximum string length in l plus 1.

23

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

7. Answer in accordance to the third and last statement in pumping lemma:

For all xyiz ∈L
a) i>0
b) i<0
c) i<=0
d) i>=0
SOLUTION
Answer: d
Explanation: Suppose L is a regular language . Then there is an integer n so that for
any x∈L and |x|>=n, there are strings u,v,w so that
x= uvw
|uv|<=n
|v|>0
for any m>=0, uvmw ∈L.
8. If d is a final state, which of the following is correct according to the given diagram?

a) x=p, y=qr, z=s

b) x=p, z=qrs
c) x=pr, y=r, z=s
d) All of the mentioned
SOLUTION
Answer: a
Explanation: The FSA accepts the string pqrs. In terms of pumping lemma, the string
pqrs is broken into an x portion an a, a y portion qr and a z portion s.
9. Let w be a string and fragmented by three variable x, y, and z as per pumping lemma.
What does these variables represent?
a) string count
b) string
c) both (a) and (b)
d) none of the mentioned
SOLUTION
Answer: a
Explanation: Given: w =xyz. Here, xyz individually represents strings or rather
substrings which we compute over conditions to check the regularity of the
language.
10. Which of the following one can relate to the given statement:
Statement: If n items are put into m containers, with n>m, then atleast one container
must contain more than one item.
a) Pumping lemma
b) Pigeon Hole principle
c) Count principle
d) None of the mentioned

24

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

SOLUTION
Answer: b
Explanation: Pigeon hole principle states the following example: If there exists n=10
pigeons in m=9 holes, then since 10>9, the pigeonhole principle says that at least
one hole has more than one pigeon.

TOPIC 4: Proving Languages not to be regular (Pumping Lemma)

1. Relate the following statement:
Statement: All sufficiently long words in a regular language can have a middle section
of words repeated a number of times to produce a new word which also lies within the
same language.
a) Turing Machine
b) Pumping Lemma
c) Arden’s theorem
d) None of the mentioned
SOLUTION
Answer: b
Explanation: Pumping lemma defines an essential property for every regular
language in automata theory. It has certain rules which decide whether a language is
regular or not.
2. While applying Pumping lemma over a language, we consider a string w that belong
to L and fragment it into parts.
a) 2
b) 5
c) 3
d) 6
SOLUTION
Answer: c
Explanation: We select a string w such that w=xyz and |y|>0 and other conditions.
However, there exists an integer n such that |w|>=n for any wÎL.
3. If we select a string w such that w∈L, and w=xyz. Which of the following portions
cannot be an empty string?
a) x
b) y
c) z
d) all of the mentioned
SOLUTION
Answer: b
Explanation: The lemma says, the portion y in xyz cannot be zero or empty i.e. |y|>0,
this condition needs to be fulfilled to check the conclusion condition.

25

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

4. Let w= xyz and y refers to the middle portion and |y|>0.What do we call the process
of repeating y 0 or more times before checking that they still belong to the language L
or not?
a) Generating
b) Pumping
c) Producing
d) None of the mentioned
SOLUTION
Answer: b
Explanation: The process of repeatation is called pumping and so, pumping is the
process we perform before we check whether the pumped string belongs to L or not.
5. There exists a language L. We define a string w such that w∈L and w=xyz and |w|
>=n for some constant integer n.What can be the maximum length of the substring xy
i.e. |xy|<=?
a) n
b) |y|
c) |x|
d) none of the mentioned
SOLUTION
Answer: a
Explanation: It is the first conditional statement of the lemma that states that
|xy|<=n, i.e. the maximum length of the substring xy in w can be n only.
6. Fill in the blank in terms of p, where p is the maximum string length in L.
Statement: Finite languages trivially satisfy the pumping lemma by having n =
a) p*1
b) p+1
c) p-1
d) None of the mentioned
SOLUTION
Answer: b
Explanation: Finite languages trivially satisfy the pumping lemma by having n equal
to the maximum string length in l plus 1.
7. Answer in accordance to the third and last statement in pumping lemma:
For all xyiz ∈L
a) i>0
b) i<0
c) i<=0
d) i>=0
SOLUTION
Answer: d
Explanation: Suppose L is a regular language . Then there is an integer n so that for
any x∈L and |x|>=n, there are strings u,v,w so that

26

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

x= uvw
|uv|<=n
|v|>0
for any m>=0, uvmw ∈L.
8. If d is a final state, which of the following is correct according to the given diagram?

a) x=p, y=qr, z=s

b) x=p, z=qrs
c) x=pr, y=r, z=s
d) All of the mentioned
SOLUTION
Answer: a
Explanation: The FSA accepts the string pqrs. In terms of pumping lemma, the string
pqrs is broken into an x portion an a, a y portion qr and a z portion s.
9. Let w be a string and fragmented by three variable x, y, and z as per pumping lemma.
What does these variables represent?
a) string count
b) string
c) both (a) and (b)
d) none of the mentioned
SOLUTION
Answer: a
Explanation: Given: w =xyz. Here, xyz individually represents strings or rather
substrings which we compute over conditions to check the regularity of the
language.
10. Which of the following one can relate to the given statement:
Statement: If n items are put into m containers, with n>m, then atleast one container
must contain more than one item.
a) Pumping lemma
b) Pigeon Hole principle
c) Count principle
d) None of the mentioned
SOLUTION
Answer: b
Explanation: Pigeon hole principle states the following example: If there exists n=10
pigeons in m=9 holes, then since 10>9, the pigeonhole principle says that at least
one hole has more than one pigeon.
TOPIC 4: Closure Properties of Regular Languages
1. If L1, L2 are regular and op(L1, L2) is also regular, then L1 and L2 are said to be
under an operation op.
a) open
b) closed

27

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

c) decidable
d) none of the mentioned
SOLUTION
Answer: b
Explanation: If two regular languages are closed under an operation op, then the
resultant of the languages over an operation op will also be regular.
2. Suppose a regular language L is closed under the operation halving, then the result
would be:
a) 1/4 L will be regular
b) 1/2 L will be regular
c) 1/8 L will be regular
d) Al of the mentioned
SOLUTION
Answer: d
Explanation: At first stage 1/2 L will be regular and subsequently, all the options will
be regular.
3. If L1′ and L2′ are regular languages, then L1.L2 will be
a) regular
b) non regular
c) may be regular
d) none of the mentioned
SOLUTION
Answer: a
Explanation: Regular language is closed under complement operation. Thus, if L1′
and L2′ are regular so are L1 and L2. And if L1 and L2 are regular so is L1.L2.
4. If L1 and L2′ are regular languages, L1 ∩ (L2′ U L1′)’ will be
a) regular
b) non regular
c) may be regular
d) none of the mentioned
SOLUTION
Answer: a
Explanation: If L1 is regular, so is L1′ and if L1′ and L2′ are regular so is L1′ U L2′.
Further, regular languages are also closed under intersection operation.
5. If A and B are regular languages, !(A’ U B’) is:
a) regular
b) non regular
c) may be regular
d) none of the mentioned
SOLUTION
Answer: a
Explanation: If A and B are regular languages, then A Ç B is a regular language and A

28

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

∩ B is equivalent to !(A’ U B’).

6. Which among the following are the boolean operations that under which regular
languages are closed?
a) Union
b) Intersection
c) Complement
d) All of the mentioned
SOLUTION
Answer: d
Explanation: Regular languages are closed under the following operations:
a) Regular expression operations
b) Boolean operations
c) Homomorphism
d) Inverse Homomorphism
7. Suppose a language L1 has 2 states and L2 has 2 states. After using the cross
product construction method, we have a machine M that accepts L1 ∩ L2. The total
number of states in M:
a) 6
b) 4
c) 2
d) 8
SOLUTION
Answer: 4
Explanation: M is defined as: (Q, S, d, q0, F)
where Q=Q1*Q2 and F=F1*F2
8. If L is a regular language, then (L’)’ U L will be :
a) L
b) L’
c) f
d) none of the mentioned
SOLUTION
Answer: a
Explanation: (L’)’ is equivalent to L and L U L is subsequently equivalent to L.
9. If L is a regular language, then (((L’)r)’)* is:
a) regular
b) non regular
c) may be regular
d) none of the mentioned
SOLUTION
Answer: a
Explanation: If L is regular so is its complement, if L’ is regular so is its reverse, if (L’)r
is regular so is its Kleene.

29

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

10. Which among the following is the closure property of a regular language?
a) Emptiness
b) Universality
c) Membership
d) None of the mentioned
SOLUTION
Answer: d
Explanation: All the following mentioned are decidability properties of a regular
language. The closure properties of a regular language include union, concatenation,
intersection, Kleene, complement , reverse and many more operations.

TOPIC 5: Equivalence and Minimization of Automata

1. Which of the following is same as the given DFA?

a) (0+1)*001(0+1)*
b) 1*001(0+1)*
c) (01)*(0+0+1)(01)*
d) None of the mentioned
SOLUTION
Answer: a
Explanation: There needs to be 001 together in the string as an essential substring.
Thus, the other components can be anything, 0 or 1 or e.
2. Which of the following statements is not true?
a) Every language defined by any of the automata is also defined by a regular
expression
b) Every language defined by a regular expression can be represented using a DFA
c) Every language defined by a regular expression can be represented using NFA with e
moves
d) Regular expression is just another representation for any automata definition
SOLUTION
Answer: b
Explanation: Using NFA with e moves, we can represent all the regular expressions
as an automata. As regular expressions include e, we need to use e moves.

30

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

3. The total number of states required to automate the given regular expression
(00)*(11)*
a) 3
b) 4
c) 5
d) 6
SOLUTION
Answer: c

Explanation:
4. Which of the given regular expressions correspond to the automata shown?

31

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

UNIT III CONTEXT FREE GRAMMAR AND LANGUAGES

TOPIC 1: CFG
1. The entity which generate Language is termed as:
a) Automata
b) Tokens
c) Grammar
d) Data
SOLUTION
Answer: c
Explanation: The entity which accepts a language is termed as Automata while the
one which generates it is called Grammar. Tokens are the smallest individual unit of a
program.
2. Production Rule: aAb->agb belongs to which of the following category?
a) Regular Language
b) Context free Language
c) Context Sensitive Language
d) Recursively Ennumerable Language
SOLUTION
Answer: c
Explanation: Context Sensitive Language or Type 1 or Linearly Bounded Non
deterministic Language has the production rule where the production is context
dependent i.e. aAb->agb.
3. Which of the following statement is false?
a) Context free language is the subset of context sensitive language
b) Regular language is the subset of context sensitive language
c) Recursively ennumerable language is the super set of regular language
d) Context sensitive language is a subset of context free language
SOLUTION
Answer: d
Explanation: Every regular language can be produced by context free grammar and
context free language can be produced by context sensitive grammar and so on.

4. The Grammar can be defined as: G=(V, ∑, p, S)

In the given definition, what does S represents?
a) Accepting State
b) Starting Variable
c) Sensitive Grammar

35

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

d) None of these
SOLUTION
Answer: b
Explanation: G=(V, ∑, p, S), here V=Finite set of variables, ∑= set of terminals, p=
finite productions, S= Starting Variable.
5. Which among the following cannot be accepted by a regular grammar?
a) L is a set of numbers divisible by 2
b) L is a set of binary complement
c) L is a set of string with odd number of 0
d) L is a set of 0n1n
SOLUTION
Answer: d
Explanation: There exists no finite automata to accept the given language i.e. 0n1n.
For other options, it is possible to make a dfa or nfa representing the language set.
6. Which of the expression is appropriate?
For production p: a->b where a∈V and b∈
a) V
b) S
c) (V+∑)*
d) V+ ∑
SOLUTION
Answer: c
Explanation: According to the definition, the starting variable can produce another
variable or any terminal or a variable which leads to terminal.
7. For S->0S1|e for ∑={0,1}*, which of the following is wrong for the language
produced?
a) Non regular language
b) 0n1n | n>=0
c) 0n1n | n>=1
d) None of the mentioned
SOLUTION
Answer: d
Explanation: L={e, 01, 0011, 000111, ……0n1n }. As epsilon is a part of the set, thus all
the options are correct implying none of them to be wrong.
8. The minimum number of productions required to produce a language consisting of
palindrome strings over ∑={a,b} is
a) 3
b) 7
c) 5
d) 6
SOLUTION
Answer: c

36

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

Explanation: The grammar which produces a palindrome set can be written as:
S-> aSa | bSb | e | a | b
L={e, a, b, aba, abbbaabbba…..}
9. Which of the following statement is correct?
a) All Regular grammar are context free but not vice versa
b) All context free grammar are regular grammar but not vice versa
c) Regular grammar and context free grammar are the same entity
d) None of the mentioned
SOLUTION
Answer: a
Explanation: Regular grammar is a subset of context free grammar and thus all
regular grammars are context free.
10. Are ambiguous grammar context free?
a) Yes
b) No
SOLUTION
Answer: a
Explanation: A context free grammar G is ambiguous if there is atleast one string in
L(G) which has two or more distinct leftmost derivations.

TOPIC 2: Parse Trees

1. The most suitable data structure used to represent the derivations in compiler:
a) Queue
b) Linked List
c) Tree
d) Hash Tables
SOLUTION
Answer: c
Explanation: The tree, known as “Parse tree” when used in a compiler, is the data
structure of choice to represent the source program.
2. Which of the following statement is false in context of tree terminology?
a) Root with no children is called a leaf
b) A node can have three children
c) Root has no parent
d) Trees are collection of nodes, with a parent child relationship
SOLUTION
Answer: a
Explanation: A node has atmost one parent, drawn above the node, and zero or more
children drawn below. Lines connect parents to children. There is one node, one root,
that has no parent; this node appears to be at the top of the tree. Nodes with no
children are called leaves. Nodes that are not leaves are called interior nodes.

37

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

3. In which order are the children of any node ordered?

a) From the left
b) From the right
c) Arbitrarily
d) None of the mentioned
SOLUTION
Answer: a
Explanation: The children of a node are ordered from the left and drawn so. If N is to
the left of node M, then all the descendents of N are considered to be to the left of all
the descendents of M.
4. Which among the following is the root of the parse tree?
a) Production P
b) Terminal T
c) Variable V
d) Starting Variable S
SOLUTION
Answer: d
Explanation: The root is labelled by the start symbol. All the leaves are either
labelled by a a terminal or with e.
5. For the expression E*(E) where * and brackets are the operation, number of nodes in
the respective parse tree are:
a) 6
b) 7
c) 5
d) 2
SOLUTION
Answer: b

Explanation:
6. The number of leaves in a parse tree with expression E*(E) where * and () are
operators
a) 5
b) 2
c) 4
d) 3

38

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

SOLUTION
Answer: a

Explanation:
7. Which of the following does the given parse tree correspond to?

a) P->1100
b) P->0110
c) P->1100ε
d) P->0101
SOLUTION
Answer: b
Explanation: The following is a parse tree for the production 0110 over {0,1}*.
8. A grammar with more than one parse tree is called:
a) Unambiguous
b) Ambiguous

39

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

c) Regular
d) None of the mentioned
SOLUTION
Answer: b
Explanation: A context free grammar G is ambiguous if there is at least one string in
L(G) having two or more distinct derivation trees or equivalently, two or more
distinct leftmost derivations.
9. is the acyclic graphical representation of a grammar.
a) Binary tree
b) Oct tree
c) Parse tree
d) None of the mentioned
SOLUTION
Answer: c
Explanation: In order to graphically represent a derivation of a grammar we need to
use parse trees.
10. Grammar is checked by which component of compiler
a) Scanner
b) Parser
c) Semantic Analyzer
d) None of the mentioned
SOLUTION
Answer: Parser or syntax analyzer is the one responsible for checking the grammar
and reporting errors. In this phase, parse tree is generated and syntax is analyzed.
TOPIC 3: Ambiguity in Grammars and Languages
1. Which of the following is not a notion of Context free grammars?
a) Recursive Inference
b) Derivations
c) Sentential forms
d) All of the mentioned
SOLUTION
Answer: d
Explanation: The following are the notions to express Context free grammars:
a) Recursive Inferences
b) Derivations
c) Sentential form
d) Parse trees
2. State true or false:
Statement: The recursive inference procedure determines that string w is in the
language of the variable A, A being the starting variable.
a) true
b) false

40

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

SOLUTION
Answer: a
Explanation: We apply the productions of CFG to infer that certain strings are in the
language of a certain variable.
3. Which of the following is/are the suitable approaches for inferencing?
a) Recursive Inference
b) Derivations
c) Both Recursive Inference and Derivations
d) None of the mentioned
SOLUTION
Answer: c
Explanation: Two inference approaches:
1. Recursive inference, using productions from body to head
2. Derivations, using productions from head to body
4. If w belongs to L(G), for some CFG, then w has a parse tree, which defines the
syntactic structure of w. w could be:
a) program
b) SQL-query
c) XML document
d) All of the mentioned
SOLUTION
Answer: d
Explanation: Parse trees are an alternative representation to derivations and
recursive inferences. There can be several parse trees for the same string.
5. Is the following statement correct?
Statement: Recursive inference and derivation are equivalent.
a) Yes
b) No
SOLUTION
Answer: a
Explanation: Yes, they are equivalent. Both the terminologies represent the two
approaches of recursive inferencing.
6. A->aA| a| b
The number of steps to form aab:
a) 2
b) 3
c) 4
d) 5
SOLUTION
Answer: b
Explanation: A->aA=>aaA=>aab
7. An expression is mentioned as follows. Figure out number of incorrect notations or

41

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

symbols, such that a change in those could make the expression correct.
L(G)={w in T*|S→*w}
a) 0 Errors
b) 1 Error
c) 2 Error
d) Invalid Expression
SOLUTION
Answer: a
Explanation: For the given expression, L(G)={w in T*|S→*w}, If G(V, T, P, S) is a CFG,
the language of G, denoted by L(G), is the set of terminal strings that have
derivations from the start symbol.
8. The language accepted by Push down Automaton:
a) Recursive Language
b) Context free language
c) Linearly Bounded language
d) All of the mentioned
SOLUTION
Answer: b
Explanation: Push down automata accepts context free language.
9. Which among the following is the correct option for the given grammar?
G->X111|G1,X->X0|00
a) {0a1b|a=2,b=3}
b) {0a1b|a=1,b=5}
c) {0a1b|a=b}
d) More than one of the mentioned is correct
SOLUTION
Answer: a
Explanation: Using the recursive approach, we can conclude that option a is the
correct answer, and its not possible for a grammar to have more than one language.
10. Which of the following the given language belongs to?
L={ambmcm| m>=1}
a) Context free language
b) Regular language
c) Both (a) and (b)
d) None of the mentioned
SOLUTION
Answer: d
Explanation: The given language is neither accepted by a finite automata or a push
down automata. Thus, it is neither a context free language nor a regular language.
11. Choose the correct option:
Statement: There exists two inference approaches:
a) Recursive Inference

42

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

b) Derivation
a) true
b) partially true
c) false
d) none of the mentioned
SOLUTION
Answer: a
Explanation: We apply the productions of a CFG to infer that certain strings are in a
language of certain variable.
12. Choose the correct option:
Statement 1: Recursive Inference, using productions from head to body.
Statement 2: Derivations, using productions from body to head.
a) Statement 1 is true and Statement 2 is true
b) Statement 1 and Statement 2, both are false
c) Statement 1 is true and Statement 2 is false
d) Statement 2 is true and Statement 1 is true
SOLUTION
Answer: b
Explanation: Both the statements are false. Recursive Inference, using productions
from body to head. Derivations, using productions from head to body.
13. Which of the following statements are correct for a concept called inherent
ambiguity in CFL?
a) Every CFG for L is ambiguous
b) Every CFG for L is unambiguous
c) Every CFG is also regular
d) None of the mentioned
SOLUTION
Answer: a
Explanation: A CFL L is said to be inherently ambiguous if every CFG for L is
ambiguous.
14. Which of the theorem defines the existence of Parikhs theorem?
a) Parikh’s theorem
b) Jacobi theorem
c) AF+BG theorem
d) None of the mentioned
SOLUTION
Answer: a
Explanation: Rohit Parikh in 1961 proved in his MIT research paper that some context
free language can only have ambiguous grammars.

TOPIC 4: Definition of the Pushdown Automata

1. The production of the form A->B , where A and B are non terminals is called

43

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

a) Null production
b) Unit production
c) Greibach Normal Form
d) Chomsky Normal Form
SOLUTION
Answer: b
Explanation: A->ε is termed as Null production while A->B is termed as Unit
production.
2. Halting states are of two types. They are:
a) Accept and Reject
b) Reject and Allow
c) Start and Reject
d) None of the mentioned
SOLUTION
Answer: a
Explanation: Halting states are the new tuple members introduced in turing machine
and is of two types: Accept Halting State and Reject Halting State.
3. A push down automata can be represented as:
PDA= ε-NFA +[stack] State true or false:
a) true
b) false
SOLUTION
Answer: a
Explanation:

4. A pushdown automata can be defined as: (Q, ∑, G, q0, z0, A, d)

What does the symbol z0 represents?
a) an element of G
b) initial stack symbol
c) top stack alphabet
d) all of the mentioned
SOLUTION
Answer: d
Explanation: z0 is the initial stack symbol, is an element of G. Other symbols like d
represents the transition function of the machine.
5. Which of the following correctly recognize the symbol ‘|-‘ in context to PDA?
a) Moves
b) transition function

44

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

c) or/not symbol
d) none of the mentioned
SOLUTION
Answer: a
Explanation: Using this notation, we can define moves and further acceptance of a
string by the machine.
6. Which among the following is true for the given statement?
Statement :If there are strings R and T in a language L so that R is prefix of T and R is
not equivalent to T.
a) No DPDA can accept L by empty stack
b) DPDA can accept L by an empty stack
c) L is regular
d) None of the mentioned
SOLUTION
Answer: a
Explanation: If M is a DPDA accepting L by an empty stsck, R and T are distinct
strings in L, and R is a prefix of T, then the sequence of moves M must make in order
to accept R leaves the stack empty, since R∈L. But then T cannot be accepted, since
M cant move with an empty stack.
7. Which of the following can be accepted by a DPDA?
a) The set of even length palindrome over {a,b}
b) The set of odd length palindrome over {a,b}
c) {xxc| where c stands for the complement,{0,1}}
d) None of the mentioned
SOLUTION
Answer: d
Explanation: Theorem: The language pal of palindromes over the alphabet {0,1}
cannot be accepted by any finite automaton , and it is therefore not regular.
8. For a counter automaton, with the symbols A and Z0, the string on the stack is
always in the form of
a) A
b) AnZ0, n>=0
c) Z0An, n>=0
d) None of the mentioned
SOLUTION
Answer: b
Explanation:The possible change in the stack contents is a change in the number of
A’s on the stack.
9. State true or false:
Statement: Counter Automaton can exist for the language L={0i1i|i>=0}
a) true
b) false

45

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

SOLUTION
Answer: a
Explanation: The PDA works as follows. Instead of saving excess 0’s or 1’s on the
stack, we save *’s and use two different states to indicate which symbol there is
currently a surplus of. The state q0 is the initial state and the only accepting state.
10. Let ∑={0,1}* and the grammar G be:
S->ε
S->SS
S->0S1|1S0
State which of the following is true for the given
a) Language of all and only Balanced strings
b) It contains equal number of 0’s and 1’s
c) Ambiguous Grammar
d) All of the mentioned
SOLUTION
Answer: d
Explanation: A string is said to be balanced if it consist of equal number of 0’s and 1’s.

TOPIC 5: Languages of a Pushdown Automata

1. Context free grammar is called Type 2 grammar because of
hierarchy.
a) Greibach
b) Backus
c) Chomsky
d) None of the mentioned
SOLUTION
Answer: c
Explanation: Chomsky hierarchy decide four type of language :Type 3- Regular
Language, Type 2-Context free language, Type 1-Context Sensitive Language, Type
0- Unrestricted or Recursively Ennumerable language.
2. a→b
Restriction: Length of b must be atleast as much length of a.
Which of the following is correct for the given assertion?
a) Greibach Normal form
b) Context Sensitive Language
c) Chomsky Normal form
d) Recursively Ennumerable language
SOLUTION
Answer: b
Explanation: A context-sensitive grammar (CSG) is a formal grammar in which the
left-hand sides and right-hand sides of any production rules may be surrounded by a
context of terminal and non terminal symbols. Context-sensitive grammars are more

46

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

general than context-free grammars, in the sense that there are some languages
that cannot be described by context-free grammars, but can be described by CSG.
3. From the definition of context free grammars,
G=(V, T, P, S)
What is the solution of VÇT?
a) Null
b) Not Null
c) Cannot be determined, depends on the language
d) None of the mentioned
SOLUTION
Answer: a
Explanation: V is the set of non terminal symbols while T is the st of terminal
symbols, their intersection would always be null.
4. If P is the production, for the given statement, state true or false.
P: V->(V∑T)* represents that the left hand side production rule has no right or left
context.
a) true
b) false
SOLUTION
Answer: a
Explanation: Here the production P is from the definition of Context free grammar
and thus, has no right or left context.
5. There exists a Context free grammar such that:
X->aX
Which among the following is correct with respect to the given assertion?
a) Left Recursive Grammar
b) Right Recursive Grammar
c) Non Recursive Grammar
d) None of the mentioned
SOLUTION
Answer: b
Explanation: The grammar with right recursive production is known as Right
recursive grammar. Right recursive production is of the form X->aX where a is a
terminal and X is a non terminal.
6. If the partial derivation tree contains the root as the starting variable, the form is
known as:
a) Chomsky hierarchy
b) Sentential form
c) Root form
d) None of the mentioned
SOLUTION
Answer: b

47

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

Explanation: Example: For any grammar, productions be:

S->AB
A->aaA| ^
B->Bb| ^
The partial derivation tree can be drawn as:

Since it has the root as S, this can be said to be in sentential form.

7. Find a regular expression for a grammar which generates a language which states :
L contains a set of strings starting wth an a and ending with a b, with something in the
middle.
a) a(a*Ub*)b
b) a*(aUb)b*
c) a(a*b*)b
d) None of the mentioned
SOLUTION
Answer: a
Explanation: The grammar for the same language can be stated as :
(1) S → aMb
(2) M → A
(3) M → B
(4) A → e
(5) A → aA
(6) B → e
(7) B → bB
8. Which of the following is the correct representation of grammar for the given regular
expression?
a(aUb)*b
a) (1) S → aMb
(2) M → e
(3) M → aM
(4) M → bM
b) (1) S → aMb
(2) M → Mab
(3) M → aM
(4) M → bM

48

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 lOMoARcPSD|14948590

www.studymaterialz.in

c) (1) S → aMb
(2) M → e
(3) M → aMb
(4) M → bMa
d) None of the mentioned
SOLUTION
Answer: a
Explanation:
The basic idea of grammar formalisms is to capture the structure of string by
a) using special symbols to stand for substrings of a particular structure
b) using rules to specify how the substrings are combined to form new substrings.
9. A CFG consist of the following elements:
a) a set of terminal symbols
b) a set of non terminal symbols
c) a set of productions
d) all of the mentioned
SOLUTION
Answer: d
Explanation: A CFG consists of:
a) a set of terminals, which are characters of alphabets that appear in the string
generated by the grammar.
b) a set of non terminals, which are placeholders for patterns of terminal symbols
that can be generated by the nonterminal symbols.
c) a set of productions, which are set of rules to transit from one state to other
forming up the string
d) a start symbol, a special non terminal symbol that appears in the initial string
generated in the grammar.
10. A CFG for a program describing strings of letters with the word “main” somewhere
in the string:
a) -> m a i n
-> | epsilon
-> A | B | … | Z | a | b … | z
b) –> m a i n
–>
–> A | B | … | Z | a | b … | z
c) –> m a i n
–> | epsilon
–> A | B | … | Z | a | b … | z
d) None of the mentioned
SOLUTION
Answer: a
Explanation: None.

49

Downloaded by Shrunkhala Wankhede (shrunkhala.wankhede@gmail.com)

 PJLCE/ CSE/20-21/TFCS/CT-01

PRIYADARSHINI J. L. COLLEGE OF ENGINEERING

846, New Nandanvan Layout, Nagpur

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Fourth Semester B. E. – 2020-21

Class Test - 01
Course: Theoretical Foundation of Computer Science

Time: 1 Hr Total Marks: 20

All questions are compulsory.

1. ………..is a finite sequence of symbols and we use a letter w to denote.

a. Character
b. String
c. Array
d. None of above
2. ……….. of string is the string formed by taking any number of leading symbols of a string.
a. Character
b. Prefix
c. Suffix
d. None of the above
3. ……….. of string is the string formed by taking any number of trailing symbols of a string.
e. Character
f. Prefix
g. Suffix
h. None of the above
4. If w = pranay then which is not proper prefix.
a. ↋
b. P
c. Pra
d. nay
5. If w = pranay then which is not proper sufix.
e. y
f. ay
g. Pra
h. nay
6. ……………..is a finite set of symbols denoted by ∑.
a. String
b. Alphabet
c. Language
 d. None of above
7. …………….is a well defined collection of object.
a. String
b. Alphabet
c. Set
d. None of above
8. If every element of A is related with itself by relation R is called as…………..
a. Reflecxive relation
b. Transitive relation
c. Symmetric relation
d. None of above
9. When a is related with b by R and if b is related with a by same relation R then relation R is
called ………………..
a. Reflecxive relation
b. Transitive relation
c. Symmetric relation
d. None of above
10. If every aRb and bRc implies aRc then relation R is said to be …………….
a. Reflecxive relation
b. Transitive relation
c. Symmetric relation
d. None of above
11. The non- Kleene Star operation accepts the following string of finite length over set A = {0,1} |
where string s contains even number of 0 and 1
a. 01,0011,010101
b. 0011,11001100
c. ε,0011,11001100
d. ε,0011,11001100
12. A regular language over an alphabet ∑ is one that cannot be obtained from the basic languages
using the operation
a. Union
b. Concatenation
c. Kleene*
d. All of the mentioned
13. The minimum number of states required to recognize an octal number divisible by 3 are/is
a. 1
b. 3
c. 5
d. 7
14. Which of the following is a not a part of 5-tuple finite automata?
a. Input alphabet
b. Transition function
c. Initial State
d. Output Alphabet
15. If an Infinite language is passed to Machine M, the subsidiary which gives a finite solution to the
infinite input tape is ______________
a. Compiler
b. Interpreter
c. Loader and Linkers
d. None of the mentioned
16. Transition function maps.
a. Σ * Q -> Σ
b. Q * Q -> Σ
c. Σ * Σ -> Q
d. Q * Σ -> Q
17. The prefix of string’pranay’ is
a. P
b. P,pr,pra
c. P,pr,pra,pran
d. All of the above
18. The binary relation {(1,1), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2)} on the set {1, 2, 3} is
a. reflective, symmetric and transitive
b. irreflexive, symmetric and transitive
c. neither reflective, nor irreflexive but transitive
d. irreflexive and antisymmetric
19. A grammar G = (V, T, P, S) in which V is
a. Set of terminals
b. Set of non terminals
c. Set of variable and terminal
d. None of above
20. Which automata is more powerful.
a. Turing machine
b. Linear bounded automata
c. Finite automata
d. None of above
21. Every infinite set is uncountable . ------False
22. Every subset of regular set is a regular set .-------F
23. Set of all positive rational numbers is countable. ------T
24. Transitive closure of the symmetric closure of a binary relation is always reflexive. ------F
25. Regular set are not closed under
a. Union
b. Intersection
c. Subset
d. Complement
26. Every infinite language is
 a. Always non-regular
b. Always regular
c. May be regular may not be regular
d. None of Above
27. Every infinite language is
a. Always non-regular
b. Always regular
c. May be regular may not be regular
d. None of Above
28. Intersection of two regular language is :
a. Always non-regular
b. Always regular
c. May be regular may not be regular
d. None of Above
29. If A and B are two nonempty finite sets, then there exists no one-to-one function from A to
B , if |A| is greater than |B| is a ……………..
a. Pumping Lemma
b. Pigeonhole Principle
c. Both
d. None of Above
30. A relation is reflexive,antisymmetric and transitive is called a partial order. -------True
31. Finite Automata recognizes …………….
a. Any Language
b. Context Sensitive Language
c. Context Free Language
d. Regular Language
32. What are the limitation of Finite State Machine?
a. It can not remember the arbitrary large information.
b. It can not remember the State Transitions
c.It can not remember the language for Grammar
d.None of the above
1. Number of states of FSM required to simulate behaviour of a computer with a
memory capable of storing “m” words, each of length ‘n’
a) m x 2^n
b) 2^mn
c) 2^(m+n)
d) All of the mentioned
2. Given a NFA with N states, the maximum number of states in an equivalent
minimized DFA is at least.
(a) N^2
(b) 2^N
(c) 2N
(d) N!
 3. A finite Automata which does not contain the ambiguity is called
a. DFA
b.NDFA
c. PDA
d. Regular Language
4. Machine without output is……..
a. DFA
b.Mealy Machine
c.Moore Machine
d.All of the Above
5.Moore Machine is a application of ……….
a.DFA without input
b.NFA with output
c.DFA with output
d.None of the above
6.In Moore Machine produce output over a change of
a.Transitions
b.States
c. Input Symbols
d.None of the Above
7.Which of the following is correct statement?
a.Moore Machine has no final state
b Mealy Machine has final state
c.Moore machine can converted into Mealy Machine but not vice versa
d.All of the Above
8. . Can a DFA recognize a palindrome number?

A. Yes
B. No
C. Yes, with input alphabet as ∑*
D. Can’t be determined

Reverse of a DFA can be formed by----

A. using PDA
B. making final state as non-final
C. making final as starting state and starting state as final state
D. None of the above.
In Mealy Machine the output is depends upon
a. Final State
b.Current State
c.Input
d. Current State & Input
 Unit- 4 MCQ
1. Which of the functions can a turing machine not perform?
a) Copying a string b) Deleting a symbol
c) Accepting a pal d) Inserting a symbol
2. If T1 and T2 are two turing machines. The composite can be represented using the expression:
a) T1T2 b) T1 U T2
c) T1 X T2 d) None of the mentioned
3. A language L is said to be Turing decidable if:
a) recursive b) TM recognizes L
c) TM accepts L d) recursive & TM recognizes L
4. A Language L may not be accepted by a Turing Machine if:
a) It is recursively enumerable b) It is recursive
c) L can be enumerated by some turing machine d) None of the mentioned
5. A turing machine that is able to simulate other turing machines:
a) Nested Turing machines b) Universal Turing machine
c) Counter machine d) None of the mentioned
6. Which of the problems are unsolvable?
a) Halting problem b) Boolean Satisfiability problem
c) Halting problem & Boolean Satisfiability problem d) None of the mentioned
7. Which of the following a turing machine does not consist of?
a) input tape b) head c) state register d) none of the mentioned
8. The value of n if turing machine is defined using n-tuples:
a) 6 b) 7 c) 8 d) 5
9. If d is not defined on the current state and the current tape symbol, then the machine ______
a) does not halts b) halts
c) goes into loop forever d) none of the mentioned
10. Which of the following are the models equivalent to Turing machine?
a) Multi tape turing machine b) Multi track turing machine
c) Register machine d) All of the mentioned
11. Which among the following is incorrect for o-machines?
a) Oracle Turing machines b) Can be used to study decision problems
c) Visualizes Turing machine with a black box which is able to decide cerain decion problems in one
operation
d) None of the mentioned
12.
A turing machine has ____________ number of states in a CPU.
a. finite b. infinte
c. May be finite d. None of the mentioned

13. Statement 1: Multitrack Turing machine.

Statement 2: Gamma is Cartesian product of a finite number of finite sets.

Which among the following is the correct option?

a. Statement 1 is the assertion and Statement 2 is the reason
b. Statement 1 is the reason and Statement 2 is the assertion
c. Statement 1 and Statement 2 are independent from each other
d. None of the mentioned
14. A multi track turing machine can described as a 6-tuple (Q, X, S, d, q0, F) where X represents:
a. input alphabet b. tape alphabet
c. shift symbols d. none of the mentioned
15. Statement: Two track turing machine is equivalent to a standard turing machine.
a. true b. false c. may be d. can't say
16. Which of the following is/are not true for recursively ennumerable language?
a. partially decidable b.Turing acceptable c.Turing Recognizable d.None of the mentioned
17.According to Chomsky hierarchy, which of the following is adopted by Recursively Ennumerable
language?
a.Type 0 b.Type 1 c.Type 2 d.Type 3
18. A turing machine with several tapes in known as:
a.Multi-tape turing machine b.Poly-tape turing maching
c.Universal turing machine d.All of the mentioned
19. A multitape turing machine is ________ powerful than a single tape turing machine.
a. more b.less c.equal d.none of the mentioned
20.In what ratio, more computation time is needed to simulate multitape turing machines using single tape
turing machines?
a.doubly b.triple c.quadratically d.none of the mentioned
21. Which of the following is true for two stack turing machines?
a.one read only input b.two storage tapes c.both a and b d.None of the mentioned
22. Which of the following is not a Non deterministic turing machine?
a.Alternating Turing machine b.Probabalistic Turing machine
c.Read-only turing machine d.None of the mentioned
23. Which of the turing machines have existential and universal states?
a.Alternating Turing machine b.Probalistic Turing machine
c.Read-only turing machine d.None of the mentioned

24. Which of the following is false for Quantum Turing machine?

a.Abstract machine
b.Any quantum algorithm can be expressed formally as a particular quantum turing machine
c.Gives a solution to ‘Is a universal quantum computer sufficient’
d.None of the mentioned
25. A deterministic turing machine is:
a.ambiguous turing machine b.unambiguous turing machine
c.non-deterministic d.none of the mentioned
26. Which of the following is true about Turing’s a-machine?
a.a stands for automatic b.left ended, right end-infinite
c. finite number of tape symbols were allowed d.all of the mentioned
27. Which of the following is a multi tape turing machine?
a.Post turing Machine b.Wang-B Machine c.Oblivious turing Machine d.All of the mentioned
28. Which of the following are related to construction of One Tape turing machines?
a.JFLAP b.NFLAP c.both a and b d.None of the mentioned
29 . Are Multitape and Multitrack turing machines same?
a. Yes b. No c. Somewhat yes d. Cannot tell
30. In a n-track turing machine, _________ head/heads read and write on all tracks simultaneously.
a. one b. two c. n d. infinite