96
80.5k

90+ Theory of Computation and Compiler Design Solved MCQs

These multiple-choice questions (MCQs) are designed to enhance your knowledge and understanding in the following areas: Computer Science Engineering (CSE) .

Take a Test
1.

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*
Answer» B. 0*(10*10*)*
discuss
2.

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
Answer» D. All are context free
discuss
3.

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
discuss
4.

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.
Answer» C. Context free but not regular
discuss
5.

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
Answer» C. All the three languages are context free
discuss
6.

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)
Answer» B. n+1
discuss
7.

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
Answer» D. 3, 4
discuss
8.

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
Answer» D. D
discuss
9.

Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression

A. b*ab*ab*ab
B. (a+b)*
C. b*a(a+b)*
D. b*ab*ab
Answer» C. b*a(a+b)*
discuss
10.

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
discuss
11.

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}+ }
Answer» C. {WW^R | X W € {0,1}+ }
discuss
12.

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

A. not recurcise
B. is recursive and deterministic CFL
C. is a regular language
D. is not a deterministic CFL but a CFL
Answer» B. is recursive and deterministic CFL
discuss
13.

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» A. 15 States
discuss
14.

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?

A. L = {s € (0 + 1)*n0 (s) is a 3-digit prime
B. L = {s € (0 + 1)* | for every prefix s’ of s, l 0 (s’) — n1 (s’) | <= 2 }
C. L={s € (0+1)* | n0(s) - n1(s) | <= 4}
D. L = {s € (0 + 1) | n0 (s) mod 7 = n1 (s) mod 5 = 0 }
Answer» C. L={s € (0+1)* | n0(s) - n1(s) | <= 4}
discuss
15.

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» D. L is regular
discuss
16.

Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

A. Both DHAM3 and SHAM3 are NP-hard
B. SHAM3 is NP-hard, but DHAM3 is not
C. DHAM3 is NP-hard, but SHAM3 is not
D. Neither DHAM3 nor SHAM3 is NP-hard
Answer» A. Both DHAM3 and SHAM3 are NP-hard
discuss
17.

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?

A. 1 only
B. 1 and 3
C. 2 and 3
D. 1,2 and 3
Answer» D. 1,2 and 3
discuss
18.

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?

A. L1 n L2 is a deterministic CFL
B. L3 n L1 is recursive
C. L1 U L2 is context free
D. L1 n L2 n L3 is recursively enumerable
Answer» B. L3 n L1 is recursive
discuss
19.

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

A. 3
B. 5
C. 8
D. 9
Answer» D. 9
discuss
20.

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?

A. L1 is a deterministic CFL
B. L2 is a deterministic CFL
C. L3 is a CFL, but not a deterministic CFL
D. L3 is a deterministic CFL
Answer» B. L2 is a deterministic CFL
discuss
21.

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?

A. L1 n L2 is a context-free language
B. L1 u L2 is a context-free language
C. L1 and L2 are context-free languages
D. L1 n L2 is a context sensitive language
Answer» A. L1 n L2 is a context-free language
discuss
22.

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?

A. L1' is recursive and L2' is recursively enumerable
B. L1' is recursive and L2' is not recursively enumerable
C. L1' and L2' are recursively enumerable
D. L1' is recursively enumerable and L2' is recursive
Answer» B. L1' is recursive and L2' is not recursively enumerable
discuss
23.

Consider the following two problems on undirected graphs:
α: Given G(V,E), does G have an independent set of size |v|—4?
β: Given G(V,E), does G have an independent set of size 5?
Which one of the following is TRUE?
A. α is in P and β is NP-complete
B. α is NP complete and β is in P
C. Both α and β are NP-complete
D. Both α and β are in P
Answer» B. α is NP complete and β is in P
discuss
24.

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 enumberable
C. L2 intersection L1 is recursively enumberable
D. L2 union L1 is recursively enumberable
Answer» B. L1 – L3 is recursively enumberable
discuss
25.

S –> aSa| bSb| a| b ; The language generated by the above grammar over the alphabet {a,b} is the set of

A. All palindromes.
B. All odd length palindromes.
C. Strings that begin and end with the same symbol
D. All even length palindromes.
Answer» B. All odd length palindromes.
discuss
26.

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.
discuss
27.

Which one of the following is FALSE?

A. There is unique minimal DFA for every regular language
B. Every NFA can be converted to an equivalent PDA.
C. Complement of every context-free language is recursive.
D. Every nondeterministic PDA can be converted to an equivalent deterministic PDA.
Answer» D. Every nondeterministic PDA can be converted to an equivalent deterministic PDA.
discuss
28.

Match all items in Group 1 with correct options from those given in Group 2.
List I List II
P. Regular Expression 1. Syntax analysis
Q. Push down automata 2. Code Generation
R. Dataflow analysis 3. Lexical analysis
S. 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» B. P-3, Q-1, R-4, S-2
discuss
29.

Which of the following pairs have DIFFERENT expressive power?

A. Deterministic finite automata (DFA) and Non-Deterministic finite automata(NFA)
B. Deterministic push down automata (DPDA) and Non-deterministic pushdown automata
C. Deterministic single-tape Turing machine and Non-deterministic single-tape Turing Machine
D. Single-tape Turing machine and multi-tape Turing machine
Answer» B. Deterministic push down automata (DPDA) and Non-deterministic pushdown automata
discuss
30.

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» C. S=T
discuss
31.

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» B. L is regular but not O
discuss
32.

Consider the following two statements:
S1: { 0^2n |n >= l} is a regu1ar language
S2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar language
Which of the following statements is correct?
A. Only S1 is correct
B. Only S2 is correct
C. Both S1 and S2 are correct
D. None of S1 and S2 is correct
Answer» C. Both S1 and S2 are correct
discuss
33.

Which of the following statements in true?

A. If a language is context free it can always be accepted by a deterministic push-down automaton
B. The union of two context free languages is context free
C. The intersection of two context free languages is context free
D. The complement of a context free language is context free
Answer» B. The union of two context free languages is context free
discuss
34.

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. N^2
B. 2^N
C. 2N
D. N!
Answer» B. 2^N
discuss
35.

Which of the following is true for the language {a^p} p is prine ?

A. It is not accepted by a turing machine
B. It is regular but not context free
C. It is context free but not regular
D. It is neither regular nor context free but accepted by a turing machine
Answer» D. It is neither regular nor context free but accepted by a turing machine
discuss
36.

Which of the following are decidable ?
1. whether the intersection of two regular language is infinite.
2. whether a give 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» B. 1 and 4
discuss
37.

If L and L' are recursively enumerable, then L is

A. regular
B. context free
C. context sensitive
D. recursive
Answer» D. recursive
discuss
38.

Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules
S --> aB S --> bA
B --> b A --> a
B --> bS A --> aS
B --> aBB A --> bAA
Which of the following strings is generated by the grammar?
A. aaaabb
B. aabbbb
C. aabbab
D. abbbba
Answer» C. aabbab
discuss
39.

Consider the following context free languages:
L1 = {0^i 1^j 2^k | i+j = k}
L2 = {0^i 1^j 2^k | i = j or j = k}
L3 = {0^i 1^j | i = 2j+1}
Which of the following option is true?
A. L1, L2 and L3 can be recognized by Deterministic Push down automata
B. L1, L2 can be recognized by Deterministic Push down automata
C. L1, L3 can be recognized by Deterministic Push down automata
D. None of the above
Answer» C. L1, L3 can be recognized by Deterministic Push down automata
discuss
40.

Which of the following are decidable?
I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free
A. I and II
B. I and IV
C. II and III
D. II and IV
Answer» B. I and IV
discuss
41.

Let <M> be the encoding of a Turing machine as a string over ∑= {0, 1}. Let L = { <M> |M is a Turing machine that accepts a string of length 2014 }. Then, L is

A. decidable and recursively enumerable
B. undecidable but recursively enumerable
C. undecidable and not recursively enumerable
D. decidable but not recursively enumerable
Answer» B. undecidable but recursively enumerable
discuss
42.

Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?

A. P3 is decidable if P1 is reducible to P3
B. P3 is undecidable if P3 is reducible to P2
C. P3 is undecidable if P2 is reducible to P3
D. P3 is decidable if P3 is reducible to P2's complement
Answer» C. P3 is undecidable if P2 is reducible to P3
discuss
43.

Consider the following decision problems:
(P1) Does a given finite state machine accept a given string
(P2) Does a given context free grammar generate an infinite number of stings
Which of the following statements is true?
A. Both (P1) and (P2) are decidable
B. Neither (P1) nor (P2) are decidable
C. Only (P1) is decidable
D. Only (P2) is decidable
Answer» A. Both (P1) and (P2) are decidable
discuss
44.

Which of the following statements is false?

A. Every context-sensitive language is recursive.
B. The set of all languages that are not recursively enumerable is countable.
C. The family of recursively enumerable languages is closed under union.
D. The families of recursively enumerable and recursive languages are closed under reversal
Answer» B. The set of all languages that are not recursively enumerable is countable.
discuss
45.

In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier?

A. (L + D) *
B. (L.D) *
C. L(L + D) *
D. L(L.D) *
Answer» C. L(L + D) *
discuss
46.

The number of strings of length 4 that are generated by the regular expression (0+1+|2+3+)*, where | is an alternation character and {+, *} are quantification characters, is:

A. 08
B. 09
C. 10
D. 12
Answer» C. 10
discuss
47.

The regular grammar for the language L = {anbm | n + m is even} is given by

A. S → S1 | S2 S1 → a S1| A1 A1 → b A1| λ S2 → aaS2| A2 A2 → b A2| λ
B. S → S1 | S2 S1 → a S1| aA1 S2 → aaS2| A2 A1 → b A1| λ A2 → b A2| λ
C. S → S1 | S2 S1 → aaa S1| aA1 S2 → aaS2| A2 A1 → b A1| λ A2 → b A2| λ
D. S → S1 | S2 S1 → aa S1| A1 S2 → aaS2| A2 A1 → bb A1| λ A2 → bb A2| λ
Answer» D. S → S1 | S2 S1 → aa S1| A1 S2 → aaS2| A2 A1 → bb A1| λ A2 → bb A2| λ
discuss
48.

Consider the following identities for regular expressions: (a) (r + s)* = (s + r)* (b) (r*)* = r* (c) (r* s*)* = (r + s)* Which of the above identities are true?

A. (a) and (b) only
B. (b) and (c) only
C. (c) and (a) only
D. (a), (b) and (c)
Answer» D. (a), (b) and (c)
discuss
49.

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)mod5 = 2 and d(s)mod7 != 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» D. L is regular
discuss
50.

The number of tokens in the following C statement is (GATE 2000) printf("i = %d, &i = %x", i, &i);

A. 3
B. 26
C. 10
D. 21
Answer» C. 10
discuss

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.

Take a Test