Here are the Theory of computation(TOC ) multiple choice questions(MCQ) from GATE computer science previous years papers. We have divided the questions into 1 marks and 2 marks section for the ease of GATE aspirants simplicity.

## TOC 1 Marks

Start

Congratulations - you have completed

*TOC 1 Marks*.You scored %%SCORE%% out of %%TOTAL%%.Your performance has been rated as %%RATING%% Your answers are highlighted below.

Question 1 |

**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? [GATE 2010]**

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 |

Question 2 |

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

A | All palindromes. |

B | All odd length palindromes. |

C | Strings that begin and end with the same symbol |

D | All even length palindromes. |

Question 2 Explanation:

The strings accepted by language are {a, b, aaa, bbb, aba, bab, ..}. All of these strings are odd length palindromes.

Question 3 |

**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)*? [GATE 2009]**

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

Question 3 Explanation:

The regular expression has two 0′s surrounded by (0+1)* which means accepted strings must have at least 2 0′s.

Question 4 |

**Which one of the following is FALSE?[ GATE 2009]**

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

Question 4 Explanation:

Deterministic PDA cannot handle languages or grammars with ambiguity, but NDPDA can handle languages with ambiguity and any context-free grammar. So every nondeterministic PDA can not be converted to an equivalent deterministic PDA.

Question 5 |

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 |

Question 6 |

**Which of the following pairs have DIFFERENT expressive power? [GATE 2011]**

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 |

Question 6 Explanation:

DPDA cannot handle languages or grammars with ambiguity, but NDPDA can handle languages with ambiguity and any context-free grammar.

Question 7 |

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? (GATE CS 2000)

A | ScT (S is a subset of T) |

B | TcS (T is a subset of S) |

C | S=T |

D | SnT=Ø |

Question 8 |

**Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true? (GATE CS 2000)**

A | L = O |

B | L is regular but not O |

C | L is context free but not regular |

D | L is not context free |

Question 8 Explanation:

grammar itself is not regular but language L is regular as L can be represented using a regular grammar, for example S -> S00/00

Question 9 |

**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? (GATE CS 2001)

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? (GATE CS 2001)

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 |

Question 9 Explanation:

S1 can be written as (00)^n where n >= 1. And S2 can be written as (00)^(m+n) where m >=2 and n >= 1. S2 can be further reduced to (00)^x where x >= 3. We can easily write regular grammars for both S1 and S2. G1 -> G100/00 (For S1) G2 -> G200/000000 (For S2)

Question 10 |

Which of the following statements in true? (GATE CS 2001)

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 |

Question 10 Explanation:

Context-free languages are closed under the following operations. That is, if L and P are context-free languages and D is a regular language, the following languages are context-free as well: • the Kleene star L * of L • the image Ø(L) of L under a homomorphism Ø • the concatenation of L and P • the union of L and P • the intersection of L with a regular language D (L n D). Context-free languages are not closed under complement, intersection, or difference. Why a) is not true? The language recognized by deterministic pushdown automaton is deterministic context free language. Not all context-free languages are deterministic. This is unlike the situation for deterministic finite automata, which are also a subset of the nondeterministic finite automata but can recognize the same class of languages (as demonstrated by the subset construction).

Question 11 |

Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least. (GATE CS 2001)

A | N^2 |

B | 2^N |

C | 2N |

D | N! |

Question 12 |

Which of the following is true for the language {a^p} p is prine ? [GATE 2008]

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 |

Question 12 Explanation:

apply pumping leema

Question 13 |

Which of the following are decidable ? [GATE 2008]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

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 |

Question 14 |

If L and L¯ are recursively enumerable, then L is [GATE 2008]

A | regular |

B | context free |

C | context sensitive |

D | recursive |

Question 15 |

Which of the following problems is undecidable? [GATE 2007]

A | Membership problem for CFGs |

B | Ambiguity problem for CFGs. |

C | Finiteness problem for FSAs. |

D | Equivalence problem for FSAs. |

Question 16 |

Which of the following is TRUE? [GATE 2007]

A | Every subset of a regular set is regular. |

B | Every finite subset of a non-regular set is regular |

C | The union of two non-regular sets is not regular |

D | Infinite union of finite sets is regular |

Question 16 Explanation:

Finite subset of non regular set is regular as we know that pumping lemma can be applied on all the finite sets that states that all finite sets are regular. Infinite union of finite set is not regular because regular sets can never be closed under infinite union.

Question 17 |

The problem 3-SAT and 2-SAT are [GATE 2004]

A | both in P |

B | both NP complete |

C | NP-complete and in P respectively |

D | Undecidable and NP-complete respectively |

Once you are finished, click the button below. Any items you have not completed will be marked incorrect. Get Results

There are 17 questions to complete.

← | List | → |

Return

Shaded items are complete.

1 | 2 | 3 | 4 | 5 |

6 | 7 | 8 | 9 | 10 |

11 | 12 | 13 | 14 | 15 |

16 | 17 | End |

Return

You have completed

questions

question

Your score is

Correct

Wrong

Partial-Credit

You have not finished your quiz. If you leave this page, your progress will be lost.

Correct Answer

You Selected

Not Attempted

Final Score on Quiz

Attempted Questions Correct

Attempted Questions Wrong

Questions Not Attempted

Total Questions on Quiz

Question Details

Results

Date

Score

Hint

Time allowed

minutes

seconds

Time used

Answer Choice(s) Selected

Question Text

All done

Need more practice!

Keep trying!

Not bad!

Good work!

Perfect!

## TOC 2 Marks Questions

Start

Congratulations - you have completed

*TOC 2 Marks Questions*.You scored %%SCORE%% out of %%TOTAL%%.Your performance has been rated as %%RATING%% Your answers are highlighted below.

Question 1 |

**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?b [GATE 2010]**

A | (0*10*1)* |

B | 0*(10*10*)* |

C | 0*(10*1*)*0* |

D | 0*1(10*1)*10* |

Question 2 |

**Consider the languages L1={|i != j}, L2={|i = j}, L3 = {|i = 2j+1}, L4 = {|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 |

Question 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? [GATE 2010]**

A | n-1 |

B | n |

C | n+1 |

D | 2n-1 |

Question 4 |

**Let L = L1 L2, where L1 and L2 are languages as defined below: [GATE 2009] L1 = { | m, n >= 0 } L2 = { | 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. |

Question 4 Explanation:

The language L1 accept strings {c, abc, abcab, aabbcab, aabbcaabb, …} and L2 accept strings {a, b, c, ab, abc, aabc, aabbc, … }. Intersection of these two languages is context free, but not regular.

Question 5 |

**Consider the language L1,L2,L3 as given below.**

**L1={ | p,q N} L2={ | p,q N and p=q} L3={ | p,q,r N and p=q=r} Which of the following statements is NOT TRUE? [GATE 2011]**

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 |

Question 6 |

**Definition of a language L with alphabet {a} is given as following. L= { | k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L? [GATE 2011]**

A | k+1 |

B | n+1 |

C | 2^(n+1) |

D | 2^(k+1) |

Question 6 Explanation:

n is a constant and k is any positive integer. For example, if n is given as 3, then the DFA must be able to accept 3a, 6a, 9a, 12a, .. To build such a DFA, we need 4 states.

Question 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? [GATE 2012]**

A | 1, 2, 3, 4 |

B | 1, 2 |

C | 2, 3, 4 |

D | 3, 4 |

Question 7 Explanation:

….1) Is a variation of Turing Machine Halting problem and it is undecidable. ….2) Context Free Languages are not closed under intersection and complement. See this for details. ….3) Complement of Regular languages is also regular. Then a DFA that accepts the complement of L, i.e. E* – L, can be obtained by swapping its accepting states with its non-accepting states. ….4) Recursive Languages are closed under complement.

Question 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. [GATE 2012]**

The missing arcs in the DFA are

A | A |

B | B |

C | C |

D | D |

Question 8 Explanation:

State ‘q’ is trap state. All other states are accept states. In state 00, DFA must move to ‘q’ for input symbol 0. All (non-trap) states indicate names indicate the characters seen before reaching that particular state. Option (D) is the only option that follow these rules.

Question 9 |

Consider the following Finite State Automaton

The language accepted by this automaton is given by the regular expression

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 |

Question 9 Explanation:

q0 to q1 -> b*a , q1 to q2 ->(a+b)*Regular expression b*a (a+b)*

Question 10 |

The minimum state automaton equivalent to the above FSA has the following number of states [GATE 2007]

A | 1 |

B | 2 |

C | 3 |

D | 4 |

Question 10 Explanation:

q0 and q1 are the states that are required at most and hence the minium number of states is 2

Question 11 |

Which of the following languages is regular? [GATE 2007]

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}+ } |

Question 12 |

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

A | not recurcise |

B | is recursive and deterministic CFL |

C | is a regular language |

D | is not a deterministic CFL but a CFL |

Question 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 [GATE 2007]

A | 15 States |

B | 11 states |

C | 10 states |

D | 9 states |

Question 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? [GATE 2006]

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 } |

Question 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? [GATE 2006]

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 |

Question 15 Explanation:

both the languages are regular since there exists deterministic finite automata for both of them. therefore L is regular.

Question 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? [GATE 2006]

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 |

Question 16 Explanation:

There is a difference between SHAM and DHAM, that SHAM is used for finding a hamiltonian cycle in a graph but DHAM is the problem of determining if a graph exists in a Hamiltonian cycle. Also it is given that |v| id divisible by 3, hence the problem can be reduced from 3 SAT which further determines that SHAM and DHAM are NP hard

Question 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? GATE 2006

A | 1 only |

B | 1 and 3 |

C | 2 and 3 |

D | 1,2 and 3 |

Question 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? [GATE 2006]

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 |

Question 18 Explanation:

b is false since L3 is not recursive and hence L3 N L1 cannont be recursive

Question 19 |

Consider the regular language L =(111+11111)*. The minimum number of states in any DFA accepting this languages is: [GATE 2006]

A | 3 |

B | 5 |

C | 8 |

D | 9 |

Question 19 Explanation:

more than eight 1's can be generated by the combination of 111 and 11111. Therefore number of states = 8+1 =9

Question 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 |

Question 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? [GATE 2005]

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 |

Question 21 Explanation:

L1 and L2 are context free, therefore L1 n L2 may not be context free, since CFL's are not closed under intersection. Now L1 n L2 are not context free but context sensitive

Question 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? [GATE 2005]

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 |

Question 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? [GATE 2005]

α: 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? [GATE 2005]

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 |

Once you are finished, click the button below. Any items you have not completed will be marked incorrect. Get Results

There are 23 questions to complete.

← | List | → |

Return

Shaded items are complete.

1 | 2 | 3 | 4 | 5 |

6 | 7 | 8 | 9 | 10 |

11 | 12 | 13 | 14 | 15 |

16 | 17 | 18 | 19 | 20 |

21 | 22 | 23 | End |

Return

You have completed

questions

question

Your score is

Correct

Wrong

Partial-Credit

You have not finished your quiz. If you leave this page, your progress will be lost.

Correct Answer

You Selected

Not Attempted

Final Score on Quiz

Attempted Questions Correct

Attempted Questions Wrong

Questions Not Attempted

Total Questions on Quiz

Question Details

Results

Date

Score

Hint

Time allowed

minutes

seconds

Time used

Answer Choice(s) Selected

Question Text

All done

Need more practice!

Keep trying!

Not bad!

Good work!

Perfect!

Related posts: