McqMate
Chapters
1. 
Type1 Grammar is known as_____________ 
A.  CFG 
B.  CSG 
C.  REGULAR 
D.  All 
Answer» B. CSG 
2. 
If G is “S → a S/a”, then L(G) = ? 
A.  a* 
B.  ^ 
C.  {a}+ 
D.  Both (a) & (c) 
Answer» C. {a}+ 
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 
4. 
A→abA a type __________productions 
A.  Type 0 
B.  Type 1 
C.  Type 2 
D.  Type 3 
Answer» B. Type 1 
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. 
The language accepted by a Push down Automata: 
A.  Type0 
B.  Type1 
C.  Type2 
D.  Type3 
Answer» C. Type2 
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.  contextfree languages are closed under union 
B.  contextfree languages are closed under concatenation 
C.  contextfree languages are closed under intersection 
D.  contextfree languages are closed under Kleene closure 
Answer» C. contextfree languages are closed under intersection 
9. 
Which of the following statement is wrong? 
A.  Any regular language can be generated by a contextfree grammar 
B.  Some nonregular languages cannot be generated by any CFG 
C.  the intersection of a CFL and regular set is a CFL 
D.  All nonregular languages can be generated by CFGs. 
Answer» D. All nonregular languages can be generated by CFGs. 
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 
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 language L is accepted by a FSA iff it is 
A.  CFL 
B.  CSL 
C.  Recursive 
D.  Regular 
Answer» D. Regular 
13. 
Consider the following

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 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 
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 
Answer» A. Lexical analysis 
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 
Answer» 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 
Answer» C. Complementation 
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 
23. 
Which of the following statement is wrong? 
A.  Any regular language has an equivalent contextfree grammar. 
B.  Some nonregular languages can’t be generated by any contextfree grammar 
C.  Intersection of context free language and a regular language is always contextfree 
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 
Answer» A. Ambiguous 
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 
26. 
The PDA is called nondeterministic 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 
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 
Answer» C. Null string 
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.  (0*10*1)* 
B.  0*(10*10*)* 
C.  0*(10*1*)*0* 
D.  0*1(10*1)*10* 
Answer» B. 0*(10*10*)* 
30. 
Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression 
A.  b*ab*ab*ab 
B.  (a+b)* 
C.  b*a(a+b)* 
D.  b*ab*ab 
Answer» C. b*a(a+b)* 
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.  L2L1 is recursively enumerable 
B.  L1L3 is recursively enumerable 
C.  L2 intersection L1 is recursively enumerable 
D.  L2 union L1 is recursively enumerable 
Answer» B. L1L3 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=Ø 
Answer» C. S=T 
34. 
Which of the following pairs have DIFFERENT expressive power? 
A.  Deterministic finite automata (DFA) and NonDeterministic finite automata(NFA) 
B.  Deterministic push down automata (DPDA) and Nondeterministic pushdown automata 
C.  Deterministic singletape Turing machine and Nondeterministic singletape Turing Machine 
D.  Singletape Turing machine and multitape Turing machine 
Answer» B. Deterministic push down automata (DPDA) and Nondeterministic 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.  P4, Q1, R2, S3 
B.  P3, Q1, R4, S2 
C.  P3, Q4, R1, S2 
D.  P2, Q1, R4, S3 
Answer» B. P3, Q1, R4, S2 
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 
Done Reading?