| 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
|
| 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
|
| 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
|
| 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?
|
| 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 | |
| 25. |
How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*? |
| A. | 7 |
| B. | 10 |
| C. | 12 |
| D. | 11 |
| Answer» D. 11 | |
We're developing a website for study materials for students.
We would love to hear your answers to some of the questions.
