| 1. | Any Language generated by an unrestricted grammar is: |
| A. | Recursive |
| B. | Recursively Enumerable |
| C. | Not Recursive |
| D. | None of the above |
| Answer» A. Recursive | |
| 2. | The Family of recursive language is not closed under which of the following operations: |
| A. | Union |
| B. | Intersection |
| C. | Complementation |
| D. | None of the above. |
| Answer» D. None of the above. | |
| 3. | PCP is: |
| A. | Decidable |
| B. | Undecidable |
| C. | Sometimes Decidable |
| D. | None of the |
| Answer» B. Undecidable | |
| 4. | If PCP is decidable then MPCP is |
| A. | Decidable |
| B. | Undecidable |
| C. | Can’t Say |
| D. | None of the |
| Answer» C. Can’t Say | |
| 5. | Consider a language L for which there exists a Turing machine ™, T, that accepts every word in L and either rejects or loops for every word that is not in L. The language L is |
| A. | NP hard |
| B. | NP complete |
| C. | Recursive |
| D. | Recursively enumerable |
| Answer» D. Recursively enumerable | |
| 6. | Consider the following statements I. Recursive languages are closed under complementation II. Recursively enumerable languages are closed under union III. Recursively enumerable languages are closed under complementation Which of the above statement are TRUE? |
| A. | I only |
| B. | I and II |
| C. | I and III |
| D. | II and III |
| Answer» B. I and II | |
| 7. | Recursively enumerable languages are not closed under |
| A. | Union |
| B. | homomorphism |
| C. | complementation |
| D. | concatenation |
| Answer» C. complementation | |
| 8. | Which of the following problem is undecidable? |
| A. | Membership problem for CFL |
| B. | Membership problem for regular sets |
| C. | Membership problem for CSL |
| D. | Membership problem for type 0 languages |
| Answer» D. Membership problem for type 0 languages | |
| 9. | Recursive languages are |
| A. | A proper superset of CFL |
| B. | Always recognized by PDA |
| C. | Are also called type 0 languages |
| D. | Always recognized by FSA |
| Answer» A. A proper superset of CFL | |
| 10. | Consider the following problem x. Given a Turing machine M over the input alphabet Σ, any state q of M. And a word w Є Σ*, does the computation of M on w visit the state q? Which of the following statements about x is correct? |
| A. | X is decidable |
| B. | X is undecidable but partially decidable |
| C. | X is undecidable and not even partially decidable |
| D. | X is not a decision problem |
| Answer» A. X is decidable | |
| 11. | If a language is denoted by a regular expression L = ( x )* (x y x ), then which of the following is not a legal string within L ? |
| A. | yx |
| B. | xyx |
| C. | x |
| D. | xyxyx |
| Answer» D. xyxyx | |
| 12. | Given A = {0,1} and L = A*. If R = (0n1n, n > 0), then language L ∪ R and R are respectively |
| A. | Regular, regular |
| B. | Not regular, regular |
| C. | Regular, not regular |
| D. | Context free, not regular |
| Answer» D. Context free, not regular | |
| 13. | If L1 and L2 are context free language and R a regular set, then which one of the languages below is not necessarily a context free language? |
| A. | L1 L2 |
| B. | L1 ∩ L2 |
| C. | L1 ∩ R |
| D. | L1 ∪ L2 |
| Answer» B. L1 ∩ L2 | |
| 14. | The logic of pumping lemma is a good example of |
| A. | Pigeon-hole principle |
| B. | Divide-and-conquer technique |
| C. | Recursion |
| D. | Iteration |
| Answer» A. Pigeon-hole principle | |
| 15. | For two regular languages L1 = (a + b)* a and L2 = b (a + b ) *, the intersection of L1 and L2 is given by |
| A. | (a + b ) * ab |
| B. | ab (a + b ) * |
| C. | a ( a + b ) * b |
| D. | b (a + b ) * a |
| Answer» D. b (a + b ) * a | |
| 16. | Pumping lemma is generally used for proving that |
| A. | Given grammar is regular |
| B. | Given grammar is not regular |
| C. | Whether two given regular expressions are equivalent or not |
| D. | None of these |
| Answer» B. Given grammar is not regular | |
| 17. | What is the highest type number which can be applied to the following grammar? S —>Aa, A —> Ba, B —>abc |
| A. | Type 0 |
| B. | Type 1 |
| C. | Type 2 |
| D. | Type 3 |
| Answer» C. Type 2 | |
| 18. | Following syntax-directed translation scheme is used with a shift reduction (bottom up) parser that perform the action in braces immediately after a reduction by the corresponding production A —>aB {print “(1)” A —> c {print “1”), B —>Ab {print *2”}. When parser is aaacbbb, then string printed |
| A. | 0202021 |
| B. | 1202020 |
| C. | 1020202 |
| D. | None of these |
| Answer» A. 0202021 | |
| 19. | FSM can recognize |
| A. | Any grammar |
| B. | Only CG |
| C. | Both (a) and ( b ) |
| D. | Only regular grammar |
| Answer» D. Only regular grammar | |
| 20. | Basic limitation of FSM is that it |
| A. | Cannot remember arbitrary large amount of information |
| B. | Sometimes fails to recognize grammars that are regular |
| C. | Sometimes recognizes grammars are not regular |
| D. | None of these |
| Answer» A. Cannot remember arbitrary large amount of information | |
| 21. | Which of the following are decidable? 1) Whether the intersection of two regular language is infinite. 2) Whether a given context free language is regular. 3) Whether two push down automata accept the same language. 4) Whether a given grammar is context free. |
| A. | 1 and 2 |
| B. | 1 and 4 |
| C. | 2 and 3 |
| D. | 2 and 4 |
| Answer» B. 1 and 4 | |
| 22. | If L and L¯ are recursively enumerable, then L is |
| A. | Regular |
| B. | Context free |
| C. | Context sensitive |
| D. | Recursive |
| Answer» D. Recursive | |
| 23. | Which of the following problems is undecidable? |
| A. | Membership problem for CFGs |
| B. | Ambiguity problem for CFGs. |
| C. | Finiteness problem for FSAs. |
| D. | Equivalence problem for FSAs. |
| Answer» B. Ambiguity problem for CFGs. | |
| 24. | Fred created a new automaton model which is a push down automaton but with two stacks and the added ability of having commands which do not read input tape but which can pop from one stack and push into the other.This new automaton can recognize (choose strongest result) |
| A. | Context Free Language |
| B. | Context sensitive language |
| C. | Regular language |
| D. | Languages recognizable by Turing machine |
| Answer» D. Languages recognizable by Turing machine | |
| 26. | Consider a string s over (0+1)*. The number of 0’s in s is denoted by no(s) and the number of 1’s in s is denoted by n1(s). The language that is not regular is |
| A. | L = {s ε (0+1)* I for every prefix s’ of s, I no(s’)-n1(s’) I ≤ 2} |
| B. | L = {s ε (0+1)* I no(s) mod 7 = n1(s) mod 5 = 0} |
| C. | L = {s ε (0+1)* I no(s) is a 3 digit prime} |
| D. | L = {s ε (0+1)* I no(s)-n1(s) I ≤ 4 |
| Answer» D. L = {s ε (0+1)* I no(s)-n1(s) I ≤ 4 | |
| 27. | Which one of the following is true regarding FOTRAN? |
| A. | It is a context free language |
| B. | It is a context sensitive language |
| C. | It is a regular language |
| D. | None of the above |
| Answer» B. It is a context sensitive language | |
| 28. | Which statement is true? |
| A. | The PDA must have one accept state and one reject state |
| B. | The PDA must have one accept state and two reject state |
| C. | The PDA must have two accept state and two reject state |
| D. | There is no reject state in the PDA. |
| Answer» D. There is no reject state in the PDA. | |
| 29. | TM is more powerful than FSM because |
| A. | The tape movement is confined to one direction |
| B. | It has no finite state control |
| C. | It has the capability to remember arbitrary long sequences of input symbols |
| D. | None of these |
| Answer» B. It has no finite state control | |
| 30. | Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true? |
| A. | Both DHAM3 and SHAM3 are NP-hard |
| B. | SHAM3 is NP-hard, but DHAM3 is not |
| C. | DHAM3 is NP-hard, but SHAM3 is not |
| D. | Neither DHAM3 nor SHAM3 is NP-hard |
| Answer» A. Both DHAM3 and SHAM3 are NP-hard | |
| 31. | Consider the following statements about the context free grammar G = {S – >SS,S – >ab,S ->ba, S – ε} I. G is ambiguous II. G produces all strings with equal number of a’s and b’s III. G can be accepted by a deterministic PDA. Which combination below expresses all the true statements about G? |
| A. | 1 only |
| B. | 1 and 3 |
| C. | 2 and 3 |
| D. | 1,2 and 3 |
| Answer» D. 1,2 and 3 | |
| 32. | Consider the regular language L =(111+11111)*. The minimum number of states in any DFA accepting this languages is: |
| A. | 3 |
| B. | 5 |
| C. | 8 |
| D. | 9 |
| Answer» D. 9 | |
| 33. | Give a production grammar for the language L = {x/x ∈ (a,b)*, the number of a’s in x is multiple of 3}. |
| A. | {S->bS,S->b,S->aA,S->bA,A->aB,B->bB,B->aS,S->a} |
| B. | {S->aS,S->bA,A->bB,B->bBa,B->bB} |
| C. | {S->aaS,S->bbA,A->bB,B->ba} |
| D. | None of the above |
| Answer» A. {S->bS,S->b,S->aA,S->bA,A->aB,B->bB,B->aS,S->a} | |
| 34. | The production Grammar is {S->aSbb,S->abb} is |
| A. | type-3 grammar |
| B. | type-2 grammar |
| C. | type-1 grammar |
| D. | type-0 grammar |
| Answer» B. type-2 grammar | |
| 35. | Regular expression (x/y)(x/y) denotes the set |
| A. | {xy,xy} |
| B. | {xx,xy,yx,yy} |
| C. | {x,y} |
| D. | {x,y,xy} |
| Answer» B. {xx,xy,yx,yy} | |
| 36. | The regular expression have all strings in which any number of 0’s is followed by any number of 1’s followed by any number of 2’s is : |
| A. | (0+1+2)* |
| B. | 0*1*2* |
| C. | 0* + 1 + 2 |
| D. | (0+1)*2* |
| Answer» B. 0*1*2* | |
Tags
Question and answers in Unit 3,Unit 3 Multiple choice questions and answers,Unit 3 Important MCQs,Solved MCQs for Unit 3,Unit 3 MCQs with answers PDF download
