Chapter:

# 30+ Unit 2 Solved MCQs

Chapters

65
67.4k
Chapter: Unit 2
1.

A. CFG
B. CSG
C. REGULAR
D. All
2.

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

A. a*
B. ^
C. {a}+
D. Both (a) & (c)
3.

A. Type 0
B. Type 1
C. Type 2
D. Type 3
4.

A. Type 0
B. Type 1
C. Type 2
D. Type 3
5.

## The following CFG is in S → AB**spaceB → CD**spaceB → AD**spaceB → b**spaceD → AD**spaceD → d**spaceA → 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
6.

A. Type0
B. Type1
C. Type2
D. Type3
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
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
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.
10.

A. aabb
B. abab
C. aababb
D. aaabb
11.

## Which of the following regular expression identity is true?

A. r(*) = r*
B. (r*s*)* = (r + s)*
C. (r + s)* = r* + s*
D. r*s* = r* + s*
Answer» B. (r*s*)* = (r + s)*
12.

A. CFL
B. CSL
C. Recursive
D. Regular
13.

## 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

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
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
15.

A. aaa
B. aba
C. abab
D. aa
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
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
18.

## 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

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
19.

## The following CFG is in S → aBB**spaceB → bAA**spaceA → 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
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
21.

## Context free grammar is not closed under

A. Product operation
B. Union
C. Complementation
D. kleene star
22.

A. L1
B. L1>=L2
C. L1 U L2 = .*
D. L1=L2
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
24.

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

A. Ambiguous
B. Unambiguous
C. Complementation
D. Concatenation
25.

A. Type 0
B. Type 1
C. Type 2
D. Type 3
26.

B. POP or REJECT
D. PUSH or POP
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
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
29.

A. (0*10*1)*
B. 0*(10*10*)*
C. 0*(10*1*)*0*
D. 0*1(10*1)*10*
30.

A. b*ab*ab*ab
B. (a+b)*
C. b*a(a+b)*
D. b*ab*ab
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
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
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=Ø
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
35.

## 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. 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
36.

A. 15 states
B. 11 states
C. 10 states
D. 9 states