Engineering

Theory of Computation and Compiler Design MCQs: 92 Questions & Answers in Engineering

92 Theory of Computation and Compiler Design MCQs in Engineering with answers & explanations. Practice objective questions for competitive exams, interviews… Use the answer toggle below to show or hide all solutions, tap an option to check one question, or open a question for its own page.

Page 1 of 5

Show answers

Answers hidden — tap an option or use “View Answer” on each question.

Theory of Computation and Compiler Design MCQs: 92 Questions & Answers in Engineering

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?

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?

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?

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

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?

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?

Which of the following languages is regular?

The minimum state automaton equivalent to the above FSA has the following number of states

The language L = { 0^i 2 1 ^i i>-0 } over the alphabet (0,1,2) is

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

If s is a string over (0 + 1)* then let n0 (s) denote the number of 0’s in s and n1 (s)the number of l’s in s. Which one of the following languages is not regular?

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?

Consider the following statements about the context free grammarG = {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?

Let L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?

Consider the regular language L =(111+11111)*. The minimum number of states

Consider the languages: GATE[2005]L1 = {wwR w €{0, 1} *1L2 ={w#ww € {O,1}*},where # is a special symbolL3 ={www € {0,1}*}Which one of the following is TRUE?

Consider the languages: L1 ={a^n b^n c^m | n,m >01 and L2 ={a^n b^m c^m |n,m> o) Which one of the following statements is FALSE?

Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

Study tips for Theory of Computation and Compiler Design

Consider the languages: GATE[2005]L1 = {wwR w €{0, 1} 1L2 ={w#ww € {O,1}},where # is a special symbolL3 ={www € {0,1}*}Which one of the following is TRUE?