MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 151 Mcqs, each offering curated multiple-choice questions to sharpen your Computer Science knowledge and support exam preparation. Choose a topic below to get started.
| 1. |
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 | |
| 2. |
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» E. | |
| 3. |
Automaton accepting the regular expression of any number of a ' s is: |
| A. | a* |
| B. | ab* |
| C. | (a/b)* |
| D. | a*b*c |
| Answer» B. ab* | |
| 4. |
Consider a stack, which is limited to 10 items. The language accepted by a push- down automaton in such stack is best described as |
| A. | Regular |
| B. | Deterministic context free |
| C. | Context free |
| D. | Recursive |
| Answer» B. Deterministic context free | |
| 5. |
Consider the following CFGS → 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. | |
| 6. |
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» C. type-1 grammar | |
| 7. |
A FSM can be considered, having finite tape length without rewinding capability and unidirectional tape movement |
| A. | Turing machine |
| B. | Pushdown automata |
| C. | Context free languages |
| D. | Regular languages |
| Answer» B. Pushdown automata | |
| 8. |
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» C. 23 edges | |
| 9. |
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 | |
| 10. |
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» B. {S->aS,S->bA,A->bB,B->bBa,B->bB} | |
| 11. |
If L and L¯ are recursively enumerable, then L is |
| A. | Regular |
| B. | Context free |
| C. | Context sensitive |
| D. | Recursive |
| Answer» E. | |
| 12. |
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» E. | |
| 13. |
Suppose that a problem A is known to have a polynomial-time verificationalgorithm. 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. | |
| 14. |
The set strings of 0's and 1's with atmost one pair consecutive one's- |
| A. | (0+1)*(01)(10)(0+1)* |
| B. | (0+1)*(01)*(10)(0+1)* |
| C. | (0+1)*(01)(10)*(0+1)* |
| D. | (0+!)(01)*(10)*(0+1) |
| Answer» E. | |
| 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 L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true? |
| A. | L2-L1 is recursively enumerable |
| B. | L1-L3 is recursively enumerable |
| C. | L2 intersection L1 is recursively enumerable |
| D. | L2 union L1 is recursively enumerable |
| Answer» C. L2 intersection L1 is recursively enumerable | |
| 17. |
Which one of the following is not decidable? |
| A. | given a Turing machine M, a string s, and an integer k, M accepts s with k steps |
| B. | equivalence of two given Turing machines |
| C. | language accepted by a given DFSA is nonempty |
| D. | language generated by a CFG is nonempty |
| Answer» C. language accepted by a given DFSA is nonempty | |
| 18. |
If G is a simple connected 3-regular planar graph where every region isbounded by exactly 3 edges, then the edges of G is |
| A. | 3 |
| B. | 4 |
| C. | 6 |
| D. | 5 |
| Answer» D. 5 | |
| 19. |
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 | |
| 20. |
If G is “S → a S/a”, then L(G) = ? |
| A. | a* |
| B. | ^ |
| C. | {a}+ |
| D. | Both (a) & (c) |
| Answer» D. Both (a) & (c) | |
| 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» C. 2 and 3 | |
| 22. |
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» C. GTG | |
| 23. |
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» C. (0+1)*10(0+1)* | |
| 24. |
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. | |
| 25. |
What is the reason behind a Turing machine is more powerful than finite state machine FSM? |
| A. | turing machine head movement is continued to one direction. |
| B. | turing machine head moment is in both directions i.e. left moment and right moment as well. |
| C. | turing machine has capability remember arbitrary long sequence of input string. |
| D. | all are correct. |
| Answer» D. all are correct. | |
| 26. |
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» D. None of the above | |
| 27. |
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» E. | |
| 28. |
The set which is not countable if we have ∑ = {a, b}, is |
| A. | Set of all languages over ∑ accepted by turing machine |
| B. | Set of all regular languages over ∑ |
| C. | Set of all strings over ∑ |
| D. | Set of all languages over ∑ |
| Answer» E. | |
| 29. |
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 | |
| 30. |
Choose the incorrect statement: |
| A. | (a+b)aa(a+b)generates Regular language. |
| B. | A language consisting of all strings over ∑={a,b} having equal number of a’s and b’s is a regular language |
| C. | Every language that can be expressed by FA can also be expressed by RE |
| D. | None of these |
| Answer» E. | |
| 31. |
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» E. | |
| 32. |
The PDA is called non-deterministic PDA when there are more than one out going edges from……… state |
| A. | START or READ |
| B. | POP or REJECT |
| C. | READ or POP |
| D. | PUSH or POP |
| Answer» D. PUSH or POP | |
| 33. |
The following CFG is inS → 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. | |
| 34. |
A language L is accepted by a FSA iff it is |
| A. | CFL |
| B. | CSL |
| C. | Recursive |
| D. | Regular |
| Answer» E. | |
| 35. |
In FA, if one enters in a specific state but there is no way to leave it, then that specific state is called |
| A. | Dead State |
| B. | Waste Basket |
| C. | Davey John Locker |
| D. | All of these |
| Answer» E. | |
| 36. |
A PC not connected to a network is equivalent to |
| A. | A Deterministic Finite-State Automaton, |
| B. | A Turing Machine, |
| C. | A Push-Down Automaton, |
| D. | None of the above. |
| Answer» B. A Turing Machine, | |
| 37. |
Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true? |
| A. | ScT (S is a subset of T) |
| B. | TcS (T is a subset of S) |
| C. | S=T |
| D. | SnT=Ø |
| Answer» D. SnT=Ø | |
| 38. |
Out of the three decision problems P1, P2 and P3, P1 is decidable and P2 is undecidable. The statement that holds true is |
| A. | P3 is decidable if P3 is reducible to compliment of P2 |
| B. | P3 is decidable if P1 is reducible to P3 |
| C. | P3 is undecidable if P1 is reducible to P3 |
| D. | P3 is undecidable if P2 is reducible to P3 |
| Answer» E. | |
| 39. |
Which of the following instances of the post correspondence problem has a viable sequence (a solution)? |
| A. | {(b, bb), (bb, bab), (bab, abb), (abb, babb)} |
| B. | {(ab, aba), (baa, aa), (aba, baa)} |
| C. | {(ab, abb), (ba, aaa), (aa, a)} |
| D. | none of the above |
| Answer» D. none of the above | |
| 40. |
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. | |
| 41. |
Let n be the positive integer constant and L be the language with alphabet {a}. To recognize L the minimum number of states required in a DFA will be |
| A. | 2k + 1 |
| B. | k + 1 |
| C. | 2n + 1 |
| D. | n + 1 |
| Answer» E. | |
| 42. |
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 | |
| 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. |
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 | |
| 45. |
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 | |
| 46. |
“S →a S”, what is the type of this production? |
| A. | Type 0 |
| B. | Type 1 |
| C. | Type 2 |
| D. | Type 3 |
| Answer» E. | |
| 47. |
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 | |
| 48. |
A→abA a type __________productions |
| A. | Type 0 |
| B. | Type 1 |
| C. | Type 2 |
| D. | Type 3 |
| Answer» C. Type 2 | |
| 49. |
The part of an FA, where the input string is placed before it is run, is called _______ |
| A. | State |
| B. | Transition |
| C. | Input Tape |
| D. | Output Tape |
| Answer» D. Output Tape | |
| 50. |
The set that can be recognized by a deterministic finite state automaton is |
| A. | The set {1, 101, 11011, 1110111, …….} |
| B. | The set of binary string in which the number of 0’s is same as the number of1’s |
| C. | 1, 2, 4, 8……2n ….. written in binary |
| D. | 1, 2, 4, 8……2n ….. written in unary |
| Answer» D. 1, 2, 4, 8……2n ….. written in unary | |