MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 55 Mcqs, each offering curated multiple-choice questions to sharpen your Computer Science Engineering (CSE) knowledge and support exam preparation. Choose a topic below to get started.
| 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» C. Both L1 and L2 are regular | |
| 2. |
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» D. 5 | |
| 3. |
The following grammarG = (N, T, P, S)N = {S, A, B, C, D, E}T = {a, b, c}P : S aABAB CDCD CEC aCC bbE 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» D. is type 0 but not type 1 | |
| 4. |
The following grammarG = (N, T, P, S)N = {S, A, B, C}T = {a, b, c}P : S aSA bBB cCC 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» B. is type 2 but not type 3 | |
| 5. |
The following grammarG = (N, T, P, S)N = {S, A, B}T = {a, b, c}P : S aSaS aAaA bBB bBB 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» C. is type 1 but not type 2 | |
| 6. |
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» D. None is true | |
| 7. |
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» E. | |
| 8. |
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» E. | |
| 9. |
The language L = {anbnan n 1} is recognized by |
| A. | turing machine |
| B. | 2 pushdown automata |
| C. | post machine |
| D. | all are correct |
| Answer» E. | |
| 10. |
If an effectively solvable problem has answered in yes or no, then this solution is called |
| A. | Decision procedure |
| B. | Decision method |
| C. | Decision problem |
| D. | Decision making |
| Answer» B. Decision method | |
| 11. |
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» C. 2 and 3 | |
| 12. |
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 BP - Qq R Sr R Ss R SThe minimum number of states required in Deterministic Finite Automation(DFA) equivalent to NFA is |
| A. | 5 |
| B. | 4 |
| C. | 3 |
| D. | 2 |
| Answer» D. 2 | |
| 13. |
Which of the following statements is/are FALSE?(1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.(2) Turing recognizable languages are closed under union and complementation.(3) Turing decidable languages are closed under intersection and complementation(4) Turing recognizable languages are closed under union and intersection. |
| A. | 1 and 4 only |
| B. | 1 and 3 only |
| C. | 2 only |
| D. | 3 only |
| Answer» D. 3 only | |
| 14. |
Which of the following statements are TRUE?(1) The problem of determining whether there exists a cycle in an undirected graph is in P.(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A. |
| A. | 1, 2 and 3 |
| B. | 1 and 2 only |
| C. | 2 and 3 only |
| D. | 1 and 3 only |
| Answer» B. 1 and 2 only | |
| 15. |
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» C. 0*(10*1*)*0* | |
| 16. |
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» D. * Q | |
| 17. |
Suppose that a problem A is known to have a polynomial-time verification algorithm. Which of the following statements can be deduced. |
| A. | A is in NP. |
| B. | A is in NP but not P |
| C. | A is in both NP and P. |
| D. | A is NP-complete. |
| Answer» C. A is in both NP and P. | |
| 18. |
Consider the following statementsI. Recursive languages are closed under complementationII. Recursively enumerable languages are closed under unionIII. Recursively enumerable languages are closed under complementationWhich of the above statement are TRUE? |
| A. | I only |
| B. | I and II |
| C. | I and III |
| D. | II and III |
| Answer» C. I and III | |
| 19. |
For s (0+1)* let d(s) denote the decimal value of s(e.g.d(101)) = 5 Let L = {s (0+1)* d(s) mod 5=2 and d(s) mod 7 != 4} Which one of the following statements is true? |
| A. | L is recursively enumerable, but not recursive |
| B. | L is recursive, but not context-free |
| C. | L is context-free, but not regular |
| D. | L is regular |
| Answer» E. | |
| 20. |
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» C. Regular | |
| 21. |
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» D. Greibach normal form | |
| 22. |
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» D. is type 0 but not type 1 | |
| 23. |
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» D. Type 3 | |
| 24. |
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» E. | |
| 25. |
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» E. | |
| 26. |
The following CFG is inS aBBB bAAA aB 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» E. | |
| 27. |
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» C. P-3, Q-4, R-1, S-2 | |
| 28. |
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» C. L is context free but not regular | |
| 29. |
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 productionA >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» B. 1202020 | |
| 30. |
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» D. The set of all strings that begin and end with either 0 or 1. | |
| 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» B. 11 states | |
| 32. |
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» B. 11 states | |
| 33. |
Which of the following strings is not generated by the following grammar? S SaSbS |
| A. | aabb |
| B. | abab |
| C. | aababb |
| D. | aaabb |
| Answer» E. | |
| 34. |
Consider the following statements about the context free grammar G = {S - >SS,S - >ab,S ->ba, S - }I. G is ambiguousII. G produces all strings with equal number of a s and b sIII. 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» E. | |
| 35. |
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» E. | |
| 36. |
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» E. | |
| 37. |
In which of the stated below is the following statement true? For every non-deterministic machine M1, there exists as equivalent deterministic machine M2 recognizing the same language. |
| A. | m1 is a non-deterministic finite automata |
| B. | m1 is a non-deterministic push-down automata |
| C. | m1 is a non-deterministic turing machine |
| D. | for no machine m1 use the above statement true |
| Answer» D. for no machine m1 use the above statement true | |
| 38. |
In which of the stated below is the following statement true? “For every non-deterministic machine M1, there exists as equivalent deterministic machine M2 recognizing the same language.†|
| A. | m1 is a non-deterministic finite automata |
| B. | m1 is a non-deterministic push-down automata |
| C. | m1 is a non-deterministic turing machine |
| D. | for no machine m1 use the above statement true |
| Answer» D. for no machine m1 use the above statement true | |
| 39. |
Given S = {a, b}, which one of the following sets is not countable? |
| A. | the set all strings over Σ |
| B. | the set of all language over Σ |
| C. | the set of all binary strings |
| D. | the set of all languages over Σ accepted by turing machines |
| Answer» C. the set of all binary strings | |
| 40. |
Which of the following conversion is not possible (algorithmically)? |
| A. | regular grammar to context-free grammar |
| B. | non-deterministic finite state automata to deterministic finite state automata |
| C. | non-deterministic pushdown automata to deterministic pushdown automata |
| D. | none deterministic turing machine to deterministic turing machine |
| Answer» C. non-deterministic pushdown automata to deterministic pushdown automata | |
| 41. |
Choose the correct statement |
| A. | recursive set ⊆ recursive enumerable set |
| B. | total function is same as partial function |
| C. | recursive sets are analogous to total functions |
| D. | both recursive set ⊆ recursive enumerable set and recursive sets are analogous to total functions are correct. |
| Answer» E. | |
| 42. |
A random access machine (RAM) and truing machine are different in |
| A. | power |
| B. | accessing |
| C. | storage |
| D. | both accessing and storage are correct |
| Answer» E. | |
| 43. |
Church’s Thesis supports |
| A. | a turing machine as a general-purpose computer system |
| B. | a turing machine an algorithm and an algorithm as a turing machine |
| C. | both tm is an general-purpose computer and tm is an algorithm and vice-versa are correct |
| D. | none of them is correct |
| Answer» D. none of them is correct | |
| 44. |
We think of a Turing machine’s transition function as a |
| A. | computer system |
| B. | software |
| C. | hardware |
| D. | all of them |
| Answer» C. hardware | |
| 45. |
Four pairs are following; in each pair both objects have some common thing. Choose the odd pair; |
| A. | (tm, 2pda) |
| B. | (computer, utm) |
| C. | (2pda, npda) |
| D. | (fa, pda) |
| Answer» E. | |
| 46. |
Which is correct regard an off-line Truing machine? |
| A. | an offline turing machine is a special type of multi-tape turing machine |
| B. | an offline turing machine is a kind of multi-tracks truing machine |
| C. | an offline turing machine is a kind of single-track turing machine |
| D. | none of them |
| Answer» B. an offline turing machine is a kind of multi-tracks truing machine | |
| 47. |
He difference between a read-only Turing machine and a two-way finite state machine is |
| A. | head movement |
| B. | finite control |
| C. | storage capacity |
| D. | power |
| Answer» D. power | |
| 48. |
A universal Turing machine is a |
| A. | reprogrammable truing machine |
| B. | two-tape turing machine |
| C. | single tape turing machine |
| D. | none of them |
| Answer» B. two-tape turing machine | |
| 49. |
The number of symbols necessary to simulate a Turing machine with m symbols and n states |
| A. | 4m × n + m |
| B. | 4m × n + n |
| C. | m+n |
| D. | none of them |
| Answer» B. 4m × n + n | |
| 50. |
Universal Turing machine (UTM) influenced the concepts of |
| A. | computability |
| B. | interpretive implementation of programming language |
| C. | program and data is in same memory |
| D. | all are correct |
| Answer» E. | |