

McqMate
These multiple-choice questions (MCQs) are designed to enhance your knowledge and understanding in the following areas: Computer Science Engineering (CSE) , Master of Computer Applications (MCA) .
Chapters
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 |
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. | 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 |
Done Studing? Take A Test.
Great job completing your study session! Now it's time to put your knowledge to the test. Challenge yourself, see how much you've learned, and identify areas for improvement. Don’t worry, this is all part of the journey to mastery. Ready for the next step? Take a quiz to solidify what you've just studied.