| 1. | Type-1 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. | 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. | 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 CFG S → aB S → bA**spaceB → b A → a**spaceB → bS A → aS**spaceB → aBB A → bAA**spaceConsider the following derivation**spaceS ⇒aB**space⇒aaBB**space⇒aaBb**space⇒aabSb**space⇒aabbAb**space⇒aabbab**spaceThis 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 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 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 |
| Answer» A. Ambiguous | |
| 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 | |
| 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. | 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=Ø |
| Answer» C. S=T | |
| 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 | |
| 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 | |
| 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. | 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=Ø |
| Answer» C. S=T | |
| 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 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 | |
Tags
Question and answers in Unit 2,Unit 2 Multiple choice questions and answers,Unit 2 Important MCQs,Solved MCQs for Unit 2,Unit 2 MCQs with answers PDF download
