Theory of Computation and Compiler Design MCQs | Page - 1

Dear candidates you will find MCQ questions of Theory of Computation and Compiler Design here. Learn these questions and prepare yourself for coming examinations and interviews. You can check the right answer of any question by clicking on any option or by clicking view answer button.

📊 Theory of Computation and Compiler Design
Q. Let L={w \in (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*
💬 Discuss
✅ Correct Answer: (B) 0*(10*10*)*
📊 Theory of Computation and Compiler Design
Q. Consider the languages
L1={0^{i}1^{j}|i != j},
L2={0^{i}1^{j}|i = j},
L3 = {0^{i}1^{j}|i = 2j+1},
L4 = {0^{i}1^{j}|i != 2j}.
Which one of the following statements is true?
  • (A) Only L2 is context free
  • (B) Only L2 and L3 are context free
  • (C) Only L1 and L2 are context free
  • (D) All are context free
💬 Discuss
✅ Correct Answer: (D) All are context free
📊 Theory of Computation and Compiler Design
Q. 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
💬 Discuss
✅ Correct Answer: (C) n+1
📊 Theory of Computation and Compiler Design
Q. Let L = L1 \cap L2, where L1 and L2 are languages as defined below: L1 = {a^{m}b^{m}ca^{n}b^{n} | m, n >= 0 } L2 = {a^{i}b^{j}c^{k} | i, j, k >= 0 } Then L is
  • (A) Not recursive
  • (B) Regular
  • (C) Context free but not regular
  • (D) Recursively enumerable but not context free.
💬 Discuss
✅ Correct Answer: (C) Context free but not regular
📊 Theory of Computation and Compiler Design
Q. Consider the language L1,L2,L3 as given below.
L1={0^{p}1^{q} | p,q \in N}
L2={0^{p}1^{q} | p,q \in N and p=q} L3={0^{p}1^{q}1^{r} | p,q,r \in N and p=q=r}
Which of the following statements is NOT TRUE?
  • (A) Push Down Automata (PDA) can be used to recognize L1 and L2
  • (B) L1 is a regular language
  • (C) All the three languages are context free
  • (D) Turing machine can be used to recognize all the three languages
💬 Discuss
✅ Correct Answer: (C) All the three languages are context free
📊 Theory of Computation and Compiler Design
Q. Definition of a language L with alphabet {a} is given as following. L= { a^{nk} | k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L?
  • (A) k+1
  • (B) n+1
  • (C) 2^(n+1)
  • (D) 2^(k+1)
💬 Discuss
✅ Correct Answer: (B) n+1
📊 Theory of Computation and Compiler Design
Q. Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is a context-free language, then is L’ (complement of L) also context-free?
3) If L is a regular language, then is L’ also regular?
4) If L is a recursive language, then, is L’ also recursive?
  • (A) 1, 2, 3, 4
  • (B) 1, 2
  • (C) 2, 3, 4
  • (D) 3, 4
💬 Discuss
✅ Correct Answer: (D) 3, 4
📊 Theory of Computation and Compiler Design
Q. Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For examples, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are
  • (A) A
  • (B) B
  • (C) C
  • (D) D
💬 Discuss
✅ Correct Answer: (D) D
📊 Theory of Computation and Compiler Design
Q. Which of the following languages is regular?
  • (A) {WW^R | W € {0,1}+ }
  • (B) {WW^R X | X W € {0,1}+ }
  • (C) {WW^R | X W € {0,1}+ }
  • (D) {XWW^R | X W € {0,1}+ }
💬 Discuss
✅ Correct Answer: (C) {WW^R | X W € {0,1}+ }

Jump to

Explore More Categories

Click on category to learn MCQs of that category.

📱 Download Our App

Learn MCQs on the go with our easy-to-use Android app

Get it on Google Play