| 1. | = ∈{ } w has at least as many occurrences of (110)’s as (011)’s}. Let L {w 0,1 * 2 = ∈{ } w has at least as many occurrence of (000)’s as (111)’s}. Which one of the following is TRUE? |
| A. | L1 is regular but not L2 |
| B. | L2 is regular but not L1 |
| C. | Both L1 and L2 are regular |
| D. | Neither L1 nor L2 are regular |
| Answer» B. L2 is regular but not L1 | |
| 2. | A spanning tree for a simple graph of order 24 has |
| A. | 12 edges |
| B. | 6 edges |
| C. | 23 edges |
| D. | None of above. |
| Answer» C. 23 edges | |
| 3. | If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is |
| A. | 3 |
| B. | 4 |
| C. | 6 |
| D. | 5 |
| Answer» C. 6 | |
| 4. | If G is a connected planar graph of v vertices e edges and r regions then |
| A. | v-e+r=2 |
| B. | e-v+r=2 |
| C. | v+e-r=2 |
| D. | None of above. |
| Answer» A. v-e+r=2 | |
| 5. | A Hamiltonian cycle in a Hamiltonian graph of order 24 has |
| A. | 12 edges. |
| B. | 24 edges |
| C. | 23 edges |
| D. | None of above. |
| Answer» B. 24 edges | |
| 6. | If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is |
| A. | 3 |
| B. | 4 |
| C. | 6 |
| D. | 5 |
| Answer» C. 6 | |
| 7. | The following grammar G = (N, T, P, S) N = {S, A, B} T = {a, b, c} P : S → aSa S → aAa A → bB B → bB B → c 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» B. is type 2 but not type 3 | |
| 8. | The following grammar G = (N, T, P, S) N = {S, A, B, C, D, E} T = {a, b, c} P : S → aAB AB → CD CD → CE C → aC C → b bE → 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 | |
| 9. | The following grammar G = (N, T, P, S) N = {S, A, B, C} T = {a, b, c} P : S → aS A → bB B → cC C → a 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» A. is type 3 | |
| 10. | P, Q, R are three languages. If P & R are regular and if PQ=R, then |
| A. | Q has to be regular |
| B. | Q cannot be regular |
| C. | Q need not be regular |
| D. | Q has to be a CFL |
| Answer» C. Q need not be regular | |
| 11. | Which of the following is true with respect to Kleene’s theorem? 1 A regular language is accepted by a finite automaton. 2 Every language is accepted by a finite automaton or a turingmachine. |
| A. | 1 only |
| B. | 2 only |
| C. | Both 1 and 2 are true statements |
| D. | None is true |
| Answer» C. Both 1 and 2 are true statements | |
| 12. | Automaton accepting the regular expression of any number of a ‘ s is: |
| A. | a* |
| B. | ab* |
| C. | (a/b)* |
| D. | a*b*c |
| Answer» A. a* | |
| 13. | Grammars that can be translated to DFAs: |
| A. | Left linear grammar |
| B. | Right linear grammar |
| C. | Generic grammar |
| D. | All of these |
| Answer» B. Right linear grammar | |
| 14. | Two strings x and y are indistinguishable if: |
| A. | δ*(s, x) = δ* (s, y), i.e. the state reached by a DFA M on input x is the same as the state reached by M on input y |
| B. | if for every string z Є ∑* either both xz and yz are in language A on ∑* or both xz and yz are not in A |
| C. | Both above statements are true |
| D. | None of the above |
| Answer» C. Both above statements are true | |
| 15. | Given an arbitrary non-deterministic finite automaton NFA with N states, the maximum number of states in an equivalent minimized DFA is at least: |
| A. | N2 |
| B. | 2N |
| C. | 2N |
| D. | N! |
| Answer» C. 2N | |
| 16. | Regular expressions are |
| A. | Type 0 language |
| B. | Type 1 language |
| C. | Type 2 language |
| D. | Type 3 language |
| Answer» A. Type 0 language | |
| 17. | The regular expression 0*(10)* denotes the same set as |
| A. | (1*0)*1* |
| B. | 0+(0+10)* |
| C. | (0+1)*10(0+1)* |
| D. | None of the above |
| Answer» B. 0+(0+10)* | |
| 18. | Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true? |
| A. | L1 = {0,1}* − L |
| B. | L1 = {0,1}* |
| C. | L1 is a subset of L |
| D. | L1 = L |
| Answer» A. L1 = {0,1}* − L | |
| 19. | Which of the statements is true: |
| A. | The complement of a regular language is always regular. |
| B. | Homomorphism of a regular language is always regular. |
| C. | Both of the above are true statements |
| D. | None of the above |
| Answer» C. Both of the above are true statements | |
| 20. | The regular sets are closed under: |
| A. | Union |
| B. | Concatenation |
| C. | Kleene closure |
| D. | All of the above |
| Answer» D. All of the above | |
| 21. | Any given transition graph has an equivalent: |
| A. | regular |
| B. | DFSM (Deterministic Finite State Machine) |
| C. | NDFSM |
| D. | All of them |
| Answer» D. All of them | |
| 22. | A language is regular if and only if |
| A. | Accepted by DFA |
| B. | Accepted by PDA |
| C. | Accepted by LBA |
| D. | Accepted by Turing machine |
| Answer» A. Accepted by DFA | |
| 23. | Which of the following is not a regular expression? |
| A. | [(a+b)*-(aa+bb)]* |
| B. | [(0+1)-(0b+a1)*(a+b)]* |
| C. | (01+11+10)* |
| D. | (1+2+0)*(1+2)* |
| Answer» B. [(0+1)-(0b+a1)*(a+b)]* | |
| 24. | Consider the regular language L = (111+111111)*. The minimum number of states inany DFA accepting this language is |
| A. | 3 |
| B. | 5 |
| C. | 8 |
| D. | 9 |
| Answer» D. 9 | |
| 26. | Which of the following is TRUE? | |
| A. | Every subset of a regular set is regular | |
| B. | Every finite subset of a non-regular set is regular | |
| C. | The union of two non-regular sets is not regular | |
| D. | Infinite union of finite sets is regular | |
| Answer» B. Every finite subset of a non-regular set is regular | ||
| 27. | The minimum state automaton equivalent to the above FSA has the following number of states |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» B. 2 | |
| 28. | Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*? |
| A. | The set of all strings containing the substring 00. |
| B. | The set of all strings containing at most two 0’s. |
| C. | The set of all strings containing at least two 0’s. |
| D. | The set of all strings that begin and end with either 0 or 1. |
| Answer» C. The set of all strings containing at least two 0’s. | |
| 29. | Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L? |
| A. | n-1 |
| B. | n |
| C. | n+1 |
| D. | 2n-1 |
| Answer» C. n+1 | |
| 30. | Which of the following are regular sets? |
| A. | I and IV only |
| B. | I and III only |
| C. | I only |
| D. | IV only |
| Answer» A. I and IV only | |
| 31. | A minimum state deterministic finite automation accepting the language L={W W ε {0,1}*, number of 0s and 1s in are divisible by 3 and 5, respectively} has |
| A. | 15 states |
| B. | 11 states |
| C. | 10 states |
| D. | 9 states |
| Answer» A. 15 states | |
| 32. | Let P be a regular language and Q be context-free language such that Q ∈ P. (For example, let P be the language represented by the regular expression p*q* and Q be {pnqn n∈ N}). Then which of the following is ALWAYS regular? |
| A. | P ∩ Q |
| B. | P – Q |
| C. | ∑* – P |
| D. | ∑* – Q |
| Answer» C. ∑* – P | |
| 33. | Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below: A B P – Q q R S r R S s R S The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is |
| A. | 5 |
| B. | 4 |
| C. | 3 |
| D. | 2 |
| Answer» C. 3 | |
| 34. | Which one of the following statement is true for a regular language L over {a} whose minimal finite state automation has two states? |
| A. | L must be either {an I n is odd} or {an I n is even} |
| B. | L must be {an I n is odd} |
| C. | L must be {an I n is even} |
| D. | L must be {an I n = 0} |
| Answer» A. L must be either {an I n is odd} or {an I n is even} | |
| 35. | The …………. is said to be ambiguous if there exist at least one word of its language that can be generated by the different production tree . |
| A. | CFL |
| B. | CFG |
| C. | GTG |
| D. | None of the given |
| Answer» B. CFG | |
Tags
Question and answers in Unit 1,Unit 1 Multiple choice questions and answers,Unit 1 Important MCQs,Solved MCQs for Unit 1,Unit 1 MCQs with answers PDF download
