Chapter:

30+ Unit 2 Solved MCQs

in Theory of Computation

Chapters

1.	Type-1 Grammar is known as_____________
A.	CFG
B.	CSG
C.	REGULAR
D.	All
Answer» B. CSG

discuss

2.	If G is “S → a S/a”, then L(G) = ?
A.	a*
B.	^
C.	{a}+
D.	Both (a) & (c)
Answer» C. {a}+

discuss

3.	“S →a S”, what is the type of this production?
A.	Type 0
B.	Type 1
C.	Type 2
D.	Type 3
Answer» D. Type 3

discuss

4.	A→abA a type __________productions
A.	Type 0
B.	Type 1
C.	Type 2
D.	Type 3
Answer» B. Type 1

discuss

5.	The following CFG is in S → ABspaceB → CDspaceB → ADspaceB → bspaceD → ADspaceD → dspaceA → a**spaceC → a
A.	Chomsky normal form but not strong Chomsky normal form
B.	Weak Chomsky normal form but not Chomsky normal form
C.	Strong Chomsky normal form
D.	Greibach normal form
Answer» C. Strong Chomsky normal form

discuss

6.	The language accepted by a Push down Automata:
A.	Type0
B.	Type1
C.	Type2
D.	Type3
Answer» C. Type2

discuss

7.	Which of the following problems is undecidable?
A.	Membership problem for CFGs
B.	Ambiguity problem for CFGs
C.	Finiteness problem for Finite state automata FSAs
D.	Equivalence problem for FSAs
Answer» B. Ambiguity problem for CFGs

discuss

8.	Which one of the following statement is FALSE?
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» C. context-free languages are closed under intersection

discuss

9.	Which of the following statement is wrong?
A.	Any regular language can be generated by a context-free grammar
B.	Some non-regular languages cannot be generated by any CFG
C.	the intersection of a CFL and regular set is a CFL
D.	All non-regular languages can be generated by CFGs.
Answer» D. All non-regular languages can be generated by CFGs.

discuss

10.	Which of the following strings is not generated by the following grammar? S → SaSbS ε
A.	aabb
B.	abab
C.	aababb
D.	aaabb
Answer» D. aaabb

discuss

11.	Which of the following regular expression identity is true?
A.	r() = r
B.	(rs)* = (r + s)*
C.	(r + s)* = r* + s*
D.	rs = r* + s*
Answer» B. (rs)* = (r + s)*

discuss

12.	A language L is accepted by a FSA iff it is
A.	CFL
B.	CSL
C.	Recursive
D.	Regular
Answer» D. Regular

discuss

13.	Consider the following CFG S → aB S → bAspaceB → b A → aspaceB → bS A → aSspaceB → aBB A → bAAspace Consider the following derivation spaceS ⇒aBspace⇒aaBBspace⇒aaBbspace⇒aabSbspace⇒aabbAbspace⇒aabbab**space This derivation is
A.	A leftmost derivation
B.	A rightmost derivation
C.	Both leftmost and rightmost derivation
D.	Neither leftmost nor rightmost derivation
Answer» D. Neither leftmost nor rightmost derivation

discuss

14.	Consider the following language L = {anbncndn n ≥ 1} L is
A.	CFL but not regular
B.	CSL but not CFL
C.	Regular
D.	Type 0 language but not type 1
Answer» B. CSL but not CFL

discuss

15.	A language is represented by a regular expression (a)*(a + ba). Which of the following strings does not belong to the regular set represented by the above expression?
A.	aaa
B.	aba
C.	abab
D.	aa
Answer» C. abab

discuss

16.	Which of the following denotes Chomskianhiearchy?
A.	REG ⊂ CFL ⊂ CSL ⊂ type0
B.	CFL ⊂ REG ⊂ type0 ⊂ CSL
C.	CSL ⊂ type0 ⊂ REG ⊂ CFL
D.	CSL ⊂ CFL ⊂ REG ⊂ type0
Answer» A. REG ⊂ CFL ⊂ CSL ⊂ type0

discuss

17.	The concept of FSA is much used in this part of the compiler
A.	Lexical analysis
B.	Parser
C.	Code generation
D.	Code optimization
Answer» A. Lexical analysis

discuss

18.	The following grammar G = (N, T, P, S)spaceN = {S, A, B, C, D, E}spaceT = {a, b, c}spaceP : S → aABspaceAB → CDspaceCD → CEspaceC → aCspaceC → bspacebE → bc is
A.	is type 3
B.	is type 2 but not type 3
C.	is type 1 but not type 2
D.	is type 0 but not type 1
Answer» C. is type 1 but not type 2

discuss

19.	The following CFG is in S → aBBspaceB → bAAspaceA → a**spaceB → b
A.	Chomsky normal form but not strong Chomsky normal form
B.	Weak Chomsky normal form but not Chomsky normal form
C.	Strong Chomsky normal form
D.	Greibach normal form
Answer» D. Greibach normal form

discuss

20.	Which of the following statements is wrong?
A.	The regular sets are closed under intersection
B.	The class of regular sets is closed under substitution
C.	The class of regular sets is closed under homomorphism
D.	Context Sensitive Grammar(CSG) can be recognized by Finite State Machine
Answer» D. Context Sensitive Grammar(CSG) can be recognized by Finite State Machine

discuss

21.	Context free grammar is not closed under
A.	Product operation
B.	Union
C.	Complementation
D.	kleene star
Answer» C. Complementation

discuss

22.	Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then
A.	L1
B.	L1>=L2
C.	L1 U L2 = .*
D.	L1=L2
Answer» D. L1=L2

discuss

23.	Which of the following statement is wrong?
A.	Any regular language has an equivalent context-free grammar.
B.	Some non-regular languages can’t be generated by any context-free grammar
C.	Intersection of context free language and a regular language is always context-free
D.	All languages can be generated by context- free grammar
Answer» D. All languages can be generated by context- free grammar

discuss

24.	Grammar that produce more than one Parse tree for same sentence is:
A.	Ambiguous
B.	Unambiguous
C.	Complementation
D.	Concatenation
Answer» A. Ambiguous

discuss

25.	The language accepted by a Push down Automata:
A.	Type 0
B.	Type 1
C.	Type 2
D.	Type 3
Answer» C. Type 2

discuss

26.	The PDA is called non-deterministic PDA when there are more than one out going edges from……… state:
A.	START or READ
B.	POP or REJECT
C.	READ or POP
D.	PUSH or POP
Answer» C. READ or POP

discuss

27.	Let L be a language defined over an alphabet ∑,then the language of strings , defined over ∑, not belonging to L denoted by LC or L. is called :
A.	Non regular language of L
B.	Complement of the language L
C.	None of the given
D.	All of above
Answer» B. Complement of the language L

discuss

28.	All NonNull words of the CFL can be generated by the corresponding CFG which is in CNF i.e the grammar in CNF will generate the same language except the:
A.	String
B.	Regular language
C.	Null string
D.	None of the above
Answer» C. Null string

discuss

29.	Let L={w (0 + 1)* w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?
A.	(0101)*
B.	0(1010)
C.	0(101)0*
D.	01(101)10
Answer» B. 0(1010)

discuss

30.	Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression
A.	babab*ab
B.	(a+b)*
C.	ba(a+b)
D.	babab
Answer» C. ba(a+b)

discuss

31.	Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
A.	L2-L1 is recursively enumerable
B.	L1-L3 is recursively enumerable
C.	L2 intersection L1 is recursively enumerable
D.	L2 union L1 is recursively enumerable
Answer» B. L1-L3 is recursively enumerable

discuss

32.	Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?
A.	L = O
B.	L is regular but not O
C.	L is context free but not regular
D.	L is not context free
Answer» B. L is regular but not O

discuss

33.	Let S and T be language over ={a,b} represented by the regular expressions (a+b) and (a+b)*, respectively. Which of the following is true?
A.	ScT (S is a subset of T)
B.	TcS (T is a subset of S)
C.	S=T
D.	SnT=Ø
Answer» C. S=T

discuss

34.	Which of the following pairs have DIFFERENT expressive power?
A.	Deterministic finite automata (DFA) and Non-Deterministic finite automata(NFA)
B.	Deterministic push down automata (DPDA) and Non-deterministic pushdown automata
C.	Deterministic single-tape Turing machine and Non-deterministic single-tape Turing Machine
D.	Single-tape Turing machine and multi-tape Turing machine
Answer» B. Deterministic push down automata (DPDA) and Non-deterministic pushdown automata

discuss

35.	Match all items in Group 1 with correct options from those given in Group 2. List I List IIspaceP. Regular Expression 1. Syntax analysisspaceQ. Push down automata 2. Code GenerationspaceR. Dataflow analysis 3. Lexical analysisspaceS. 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
Answer» B. P-3, Q-1, R-4, S-2

discuss

36.	A minimum state deterministic finite automation accepting the language L = {W W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has
A.	15 states
B.	11 states
C.	10 states
D.	9 states
Answer» A. 15 states

discuss

30+ Unit 2 Solved MCQs

Type-1 Grammar is known as_____________

If G is “S → a S/a”, then L(G) = ?

“S →a S”, what is the type of this production?

A→abA a type __________productions

The following CFG is in S → AB**spaceB → CD**spaceB → AD**spaceB → b**spaceD → AD**spaceD → d**spaceA → a**spaceC → a

The language accepted by a Push down Automata:

Which of the following problems is undecidable?

Which one of the following statement is FALSE?

Which of the following statement is wrong?

Which of the following strings is not generated by the following grammar? S → SaSbS ε

Which of the following regular expression identity is true?

A language L is accepted by a FSA iff it is

Consider the following CFG S → aB S → bA**spaceB → b A → a**spaceB → bS A → aS**spaceB → aBB A → bAA**space Consider the following derivation **spaceS ⇒aB**space⇒aaBB**space⇒aaBb**space⇒aabSb**space⇒aabbAb**space⇒aabbab**space This derivation is

Consider the following language L = {anbncndn n ≥ 1} L is

A language is represented by a regular expression (a)*(a + ba). Which of the following strings does not belong to the regular set represented by the above expression?

Which of the following denotes Chomskianhiearchy?

The concept of FSA is much used in this part of the compiler

The following grammar G = (N, T, P, S)**spaceN = {S, A, B, C, D, E}**spaceT = {a, b, c}**spaceP : S → aAB**spaceAB → CD**spaceCD → CE**spaceC → aC**spaceC → b**spacebE → bc is

The following CFG is in S → aBB**spaceB → bAA**spaceA → a**spaceB → b

Which of the following statements is wrong?

Context free grammar is not closed under

Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then

Which of the following statement is wrong?

Grammar that produce more than one Parse tree for same sentence is:

The language accepted by a Push down Automata:

The PDA is called non-deterministic PDA when there are more than one out going edges from……… state:

Let L be a language defined over an alphabet ∑,then the language of strings , defined over ∑, not belonging to L denoted by LC or L. is called :

All NonNull words of the CFL can be generated by the corresponding CFG which is in CNF i.e the grammar in CNF will generate the same language except the:

Let L={w (0 + 1)* w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?

Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?

Which of the following pairs have DIFFERENT expressive power?

Match all items in Group 1 with correct options from those given in Group 2. List I List II**spaceP. Regular Expression 1. Syntax analysis**spaceQ. Push down automata 2. Code Generation**spaceR. Dataflow analysis 3. Lexical analysis**spaceS. Register allocation 4. Code optimization

A minimum state deterministic finite automation accepting the language L = {W W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has

The following CFG is in S → ABspaceB → CDspaceB → ADspaceB → bspaceD → ADspaceD → dspaceA → a**spaceC → a

Consider the following

CFG
S → aB S → bAspaceB → b A → aspaceB → bS A → aSspaceB → aBB A → bAAspace

Consider the following derivation
spaceS ⇒aBspace⇒aaBBspace⇒aaBbspace⇒aabSbspace⇒aabbAbspace⇒aabbab**space

This derivation is

The following grammar G = (N, T, P, S)spaceN = {S, A, B, C, D, E}spaceT = {a, b, c}spaceP : S → aABspaceAB → CDspaceCD → CEspaceC → aCspaceC → bspacebE → bc is

The following CFG is in S → aBBspaceB → bAAspaceA → a**spaceB → b

Let S and T be language over ={a,b} represented by the regular expressions (a+b) and (a+b)*, respectively. Which of the following is true?

Match all items in Group 1 with correct options from those given in Group 2. List I List IIspaceP. Regular Expression 1. Syntax analysisspaceQ. Push down automata 2. Code GenerationspaceR. Dataflow analysis 3. Lexical analysisspaceS. Register allocation 4. Code optimization