Explore Exams
Login Signup
Sign in Open App

All questions of Theory of Computation for Computer Science Engineering (CSE) Exam

Clear all your doubts with EduRev

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∗
Correct answer is option 'C'. Can you explain this answer?

Ravi Singh answered
  • In this case, we would at least have to reach q1 so that our string gets accepted. So, b* a is the smallest accepted string.
  • Now, at q1, any string with any number of a’s and b’s would be accepted. So, we append (a + b)* to the smallest accepted string.
  • Thus, the string accepted by the FSA is b* a(a + b)*.
Thus, C is the correct choice.

The language accepted by a Pushdown Automation in which the stack is limited to 10 items is best described as
  • a)
    Context Free
  • b)
    Regular
  • c)
    Deterministic Context Free
  • d)
    Recursive
Correct answer is option 'B'. Can you explain this answer?

Ravi Singh answered
Pushdown automata is used for context free languages, i.e., languages in which the length of elements is unrestricted and length of one element is related to other. To resolve this problem, we use a stack with no restrictions on length. 
 
But in the given case, length of stack is restricted. Thus, this pushdown automata can only accept languages which can also be accepted by finite state automata and a finite state automata accepts only regular languages. 
 
Thus, B is the correct choice. 
 
Please comment below if you find anything wrong in the above post.

Which two of the following four regular expressions are equivalent? (ε is the empty string).
  • a)
    (i) and (ii)
  • b)
    (ii) and (iii)
  • c)
    (i) and (iii)
  • d)
    (iii) and (iv)
Correct answer is option 'C'. Can you explain this answer?

Ravi Singh answered
you can have any no. of 0's as well as null.
A is false because you cannot have single 0 in ii). same for option B. In D you are forced to have single 0 in iv) whereas not in iii).

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 ∩ L1 is recursively enumerable
  • d)
    L2 ∪ L1 is recursively enumerable
Correct answer is option 'B'. Can you explain this answer?

Machine Experts answered
A) Always True (Recursively enumerable - Recursive) is Recursively enumerable
B) Not always true L1 - L3 = L1 intersection (Complement L3) L1 is recursive , L3 is recursively enumerable but not recursive Recursively enumerable languages are NOT closed under complement.
C) and D) Always true Recursively enumerable languages are closed under intersection and union.

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
Correct answer is option 'B'. Can you explain this answer?

Aditya Deshmukh answered
There are finite number of strings of length ‘2014’. So, a turing machine will take the input string of length ‘2014’ and test it.
If, input string is present in the language then turing machine will halt in final state .
But, if turing machine is unable to accept the input string then it will halt in non-final state or go in an infinite loop and never halt.
Thus, ‘L’ is undecidable and recursively enumerable .

Consider the languages L1 = {0i1j | i != j}. L2 = {0i1j | i = j}. L3 = {0i1j | i = 2j+1}. L4 = {0i1j | i != 2j}.
  • 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
Correct answer is option 'D'. Can you explain this answer?

Pathways Academy answered
All these languages have valid CFGs that can derive them. Hence, all of them are CFLs. Intuitively, (A) & (B) are well known CFLs and CFGs for (C) & (D) could be made by little modifications in A & B’s CFGs. 

Let G = ({S}, {a, b} R, S) be a context free grammar where the rule set R is S → a S b | SS | ε Which of the following statements is true?
  • a)
    G is not ambiguous
  • b)
    There exist x, y, ∈ L (G) such that xy ∉ L(G)
  • c)
    There is a deterministic pushdown automaton that accepts L(G)
  • d)
    We can find a deterministic finite state automaton that accepts L(G)
Correct answer is option 'C'. Can you explain this answer?

Ravi Singh answered
An ambiguous grammar can be converted to unambiguous one.
Here we can get grammar in partial GNF form as S -> ab | abS | aSb | aSbS
We can convert this into GNF too but no need for PDA reasoning so, above grammar is not a ambiguous thus a definite PDA possible
Trick for this is but just deriving 3-4 strings from grammar, we can easily understand its (anbn)* above expression anbn is in CFL thus closure of DCFG is a DCFG i.e., you can get L = {ε, ab, abab, aabb, aabbab, abaabb, ababab,......}
PDA will push "a" until "b" is read, start popping "a" for the "b" read.
If "a" is read again from the tape then push only when stack is empty else terminate.
Repeat this until string is read. Remember fastest way to get answer is by elimination other options.

Which of the following is TRUE?
  • 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
Correct answer is option 'B'. Can you explain this answer?

Yash Patel answered
(B) Every finite subset of a non-regular set is regular.
Any finite set is always regular. 
∑* being regular any non regular language is a subset of this, and hence (A) is false.
If we take a CFL which is not regular, and takes union with its complement (complement of a CFL which is not regular won't be regular as regular is closed under complement), we get ∑* which is regular. So, (C) is false. 
Regular set is not closed under infinite union. Example: Let Li = {0i1i }, i ∊ N
Now, if we take infinite union over all i, we get
L = {0i1i | i ∊ N}, which is not regular. So, D is false. 

Which of the following statements is false?
  • a)
    Every NFA can be converted to an equivalent DFA
  • b)
    Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine
  • c)
    Every subset of a recursively enumerable set is recursive
  • d)
    none
Correct answer is option 'C'. Can you explain this answer?

Bijoy Sharma answered
A language is recursively enumerable if there exists a Turing machine that accepts every string of the language, and does not accept strings that are not in the language. Strings that are not in the language may be rejected or may cause the Turing machine to go into an infinite loop. 
A recursive language can't go into an infinite loop, it has to clearly reject the string, but a recursively enumerable language can go into an infinite loop. 
So, every recursive language is also recursively enumerable. Thus, the statement ‘Every subset of a recursively enumerable set is recursive’ is false. 
 
Thus, option (C) is the answer. 

Answer in accordance to the third and last statement in pumping lemma:For all _______ xyiz ∈L
  • a)
    i>0
  • b)
    i<0
  • c)
    i<=0
  • d)
    i>=0
Correct answer is option 'D'. Can you explain this answer?

Eesha Bhat answered
Suppose L is a regular language . Then there is an integer n so that for any x∈L and |x|>=n, there are strings u,v,w so that
x= uvw
|uv|<=n
|v|>0
for any m>=0, uvmw ∈L.

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0's and two consecutive 1's?
  • a)
  • b)
  • c)
  • d)
Correct answer is option 'B'. Can you explain this answer?

K I N G answered
Option A represents those strings which either have 0011 or 1100 as substring.
Option C represents those strings which either have 00 or 11 as substring.
Option D represents those strings which start with 11 and end with 00 or start with 00 and end with 11.

 
Q. Which one of the following is CORRECT?
  • a)
    Only (I)
  • b)
    Only (II)
  • c)
    Both (I) and (II)
  • d)
    Neither (I) nor (II)
Correct answer is option 'A'. Can you explain this answer?

Pie Academy answered
L1.L2 is also regular since regular languages are closed under concatenation.
But, L1.L2 is not { anbn | n ≥ 0 }, because both the variable is independent in both languages.
It should have been L1.L2 = { ambn | m ≥ 0, n ≥ 0 }

Consider a DFA over ∑ = {a, b} accepting all strings which have number of a’s divisible by 6 and number of b’s divisible by 8. What is the minimum number of states that the DFA will have?
  • a)
    8
  • b)
    14
  • c)
    15
  • d)
    48
Correct answer is option 'D'. Can you explain this answer?

Ravi Singh answered
We construct a DFA for strings divisible by 6. It requires minimum 6 states as length of string mod 6 = 0, 1, 2, 3, 4, 5 
We construct a DFA for strings divisible by 8. It requires minimum 8 states as length of string mod 8 = 0, 1, 2, 3, 4, 5, 6, 7 
If first DFA is minimum and second DFA is also minimum then after merging both DFAs resultant DFA will also be minimum. Such DFA is called as compound automata. 
So, minimum states in the resultant DFA = 6 * 8 = 48 
 
Thus, option (D) is the answer. 
 
Please comment below if you find anything wrong in the above post.

Suppose M1 and M2 are two TM’s such that L(M1) = L(M2). Then
  • a)
    On every input on which M1 doesn’t halt, M2 doesn’t halt too.
  • b)
    On every i/p on which M1 halts, M2 halts too.
  • c)
    On every i/p which M1 accepts, M2 halts.
  • d)
    None of above
Correct answer is option 'C'. Can you explain this answer?

Aditya Deshmukh answered
You are mixing 'rejection' and 'looping forever', we cannot interchange the two and consider anything on our own, isn't it? As rejection invovles halting whereas 'looping forever' do not. Also it is not mentioned in the question whether we are talking about R.E or recursive language.
So, if two turing machines accept the same language, acceptance can only mean halting on an input contained in the language. And we cannot talk about non-acceptance or rejection as it can be definite or indefinite, option C is correct i.e. Two Turing machines accept the same language if they halt on same input sequences.

Consider the regular expression R = (a + b)* (aa + bb) (a + b)*
Which one of the regular expressions given below defines the same language as defined by the regular expression R?
  • a)
    (a(ba)* + b(ab)*)(a + b)+
  • b)
    (a(ba)* + b(ab)*)*(a + b)*
  • c)
    (a(ba)* (a + bb) + b(ab)*(b + aa))(a + b)*
  • d)
     (a(ba)* (a + bb) + b(ab)*(b + aa))(a + b)+
Correct answer is option 'C'. Can you explain this answer?

Ravi Singh answered
R = (a+b)*(aa+bb)(a+b)*
having NFA
Equivalent DFA :
which is equivalent Transition graph [ by removing transition from q1 to q2 and q2 to q1 but does not effect on language ..be careful ]
That is equivalent to 
which is equivalent to 
which is equivalent to 
so equivalent regular expression is [a(ba)*(a+bb) + b(ab)*(b+aa)](a+b)* so option C is answer.

The language 
  • a)
    regular
  • b)
    context-free but not regular
  • c)
    context-sensitive but not context free
  • d)
    type-0 but not context sensitive
Correct answer is option 'B'. Can you explain this answer?

Pallavi Reddy answered
Language is not regular bcoz we need to match count of c's is equal to count of b's + count of a's
and that can implement by PDA
∂(q0,a,^)= (q0,a) [ push a in stack, as per language a comes first]
∂(q0,a,a)= (q0,aa) [push all a's into stack]
∂(q0,b,a) = (q1,ba) [push b in stack, state change to q1 that sure b comes after a]
∂(q1,b,b)=(q1,bb) [push all b's in stack]
∂(q1,c,b) = (q2,^) [ pop one b for one c]
∂(q2,c,b) = (q2,c) [ pop one b's for each c and continue same ]
∂(q2,c,a) = (q3,^) [ pop one a for one c , when there is no more b in stack]
∂(q3,c,a) = (q3,^) [pop one a for each c and continue same]
∂(q3,^,^) = (qf,^) [ if sum of c's is sum of a's and b's then stack will be empty when there is no c in input]
Note :1. state changes make sure b's comes after a and c's comes after b's]
 

W hat is the complement of the language accepted by the NFA shown below?
  • a)
    Ø
  • b)
    {ε}
  • c)
    a*
  • d)
    {a,ε}
Correct answer is option 'B'. Can you explain this answer?

Neha Mishra answered
The given alphabet contains only one symbol {a} and the given NFA accepts all strings with any number of occurrences of ‘a’. In other words, the NFA accepts a+. Therefore complement of the language accepted by automata is empty string.

Let L1 and L2 be languages over an alphabet £ such that L1 ⊂ L2. Which of the following is true
  • a)
    If L
    2
     is regular, then L1 must also be regular.
  • b)
    If L1 is regular, then L2  must also be regular.
  • c)
    Either L1 both  and L2  are regular, or both are not regular.
  • d)
    None of the above.
Correct answer is option 'D'. Can you explain this answer?

Raghav Sharma answered
Contradiction for A. Let L2 = {a,b}* ... which is regular.
And L1 = anbn which is CFL but not regular.
And here L1 is subset of L2.
Contradiction for B. Let L1 = ab ,
which is regular. And L2 = anbn which is CFL but not regular.
And here L1 is subset of L2.
C- > False , ( reason A and B).

Fill in the blank in terms of p, where p is the maximum string length in L. Statement: Finite languages trivially satisfy the pumping lemma by having n = ______
  • a)
    p*1
  • b)
    p+1
  • c)
    p-1
  • d)
    None of the mentioned
Correct answer is option 'B'. Can you explain this answer?

Hrishikesh Unni answered
The Pumping Lemma for Regular Languages:
The Pumping Lemma is a fundamental tool in formal language theory used to prove that a language is not regular. It states that for any regular language L, there exists a constant p such that any string w in L with length greater than or equal to p can be divided into three parts: w = xyz, where y is a non-empty substring of w, and for any non-negative integer n, the string xy^n z is also in L.

Explanation:
In the given statement, we are considering finite languages. A finite language is a language that contains a finite number of strings. For example, the language L = {a, ab, abc} is a finite language.

Finite Languages and the Pumping Lemma:
Finite languages trivially satisfy the Pumping Lemma because the Pumping Lemma requires the existence of an infinite number of strings, and since finite languages have a finite number of strings, there cannot be an infinite string in the language to test the Pumping Lemma.

Understanding the Maximum String Length:
In the statement, p represents the maximum string length in the language L. For a finite language, the maximum string length can be determined by finding the length of the longest string in the language.

Answer Explanation:
The correct answer is option B) p.

Since the language L is finite, it contains a finite number of strings. Let's assume the longest string in L has a length of p. In this case, the maximum string length in L is p.

Therefore, when applying the Pumping Lemma to a finite language, we can take n = p, where n represents the constant from the Pumping Lemma.

Since the Pumping Lemma requires the constant p, which represents the maximum string length in the language, option B) p is the correct answer.

Conclusion:
In the context of the given statement, the correct answer is option B) p because finite languages trivially satisfy the Pumping Lemma by taking n = p, where p represents the maximum string length in the language.

Given below are two finite state automata (→ indicates the start state and F indicates a final state)Which of the following represents the product automaton Z×Y?
  • a)
  • b)
  • c)
  • d)
Correct answer is option 'A'. Can you explain this answer?

Shivam Sharma answered
All four states 11, 21, 22 , 12 are interpreted as P, Q, R and S. By looking at options we can easily find out that →11 is P and 22(F) is R. Now say 12 is S and 21 is Q.
Let’s construct the transition table for ZxY.

So, the answer should be (A) but in the row for S, it should be P and Q and not Q and P.

If we select a string w such that w∈L, and w=xyz. Which of the following portions cannot be an empty string?
  • a)
    x
  • b)
    y
  • c)
    z
  • d)
    all of the mentioned
Correct answer is option 'B'. Can you explain this answer?

Sankar Sarkar answered

Explanation:

Given: w = xyz, where w ∈ L

Breakdown of w:
- Let w = xyz, where x, y, z are substrings of w.

Portions of w:
- x is the portion before y
- y is the portion in the middle
- z is the portion after y

Reasoning:

Option B (yc):
- The portion y cannot be empty because it is stated that y is a non-empty substring of w.
- Therefore, option B (yc) cannot be an empty string.

Therefore, the correct answer is option B (yc) as the portion y cannot be an empty string.

  Which of the following is true?
  • a)
  • b)
  • c)
  • d)
Correct answer is option 'D'. Can you explain this answer?

Ravi Singh answered
Only D. because n and m are independent and thus no memory element required. a and b are same and are DCFL's.
c is L = { an bm | n > m }. which is not regular.
Correction:I think c should be that x has more a's than b's.

Consider the regular grammar below
The Myhill-Nerode equivalence classes for the language generated by the grammar are
  • a)
  • b)
  • c)
  • d)
Correct answer is option 'A'. Can you explain this answer?

Avinash Sharma answered
The given grammar generates all string over the alphabet {a,b}  which have an even number of 's.
The given right-linear grammar can be converted to the following DFA.

Can you explain the answer of this question below:
Consider the languages L1 = \phi and L2 = {a}. Which one of the following represents L1 L2* U L1*
  • A:
    A
  • B:
    B
  • C:
    C
  • D:
    D
The answer is a.

Ankita Chopra answered
Since L1 is empty.The concatenation of any other language with empty language is always empty.Hence L1 L2*  evaluates to be empty language. Hence , L1 L2* = {Φ} . a* = {Φ} The kleene closure of empty language always gives null string hence  Φ* = {∈} Final answer evaluates to be  {Φ} U {∈} = {∈}.

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only.
Let      be three regular expressions. Which one of the following is true?
  • a)
  • b)
  • c)
  • d)
  • e)
    None of the above
Correct answer is option 'A,C'. Can you explain this answer?

Zoya Sharma answered
to know the ans let us check all the options.
strings generated by S are any numbers of 1's followed by one 0, i.e., 10,110,1110,1110,......) Strings generated by r are is 1 followed by any combination of 0 or 1, i.e., 1,10,11,1110,101,110,.....This shows that all the strings that can be generated by S,can also be generated by r it means 
  here strings generated by t are any numbers of 1 (here 1* means we have strings as    followed by only one 0, i.e., 0,10,110,1110,.....So we can see that all the strings that are present in S can also be
generated by t, hence    which shows that option A is true.
  this is false because string 1 which can be generated by r, cannot be generated by S
Same as option A.
. this is false because string 0 which can be generated by t ,cannot be generated by S .

Let  denote the languages generated by the grammar S→ 0S0 I 00.
Which of the following is TRUE?
  • a)
    L=0+
  • b)
    L is regular but not 0+
  • c)
     L is context free but not regular
  • d)
    L is not context free
Correct answer is option 'B'. Can you explain this answer?

Aditya Deshmukh answered
Option A : L is not 0+ , because 0+ will contain any arbitrary string over alphabet 0 with any no of 0’s ( except empty string ), for ex: {0, 00, 000,00000}, but L will only have the strings as { 00, 0000, 000000,…}, i.e only even no of  0’s ( excluding empty string}.

Option D : L is a Context Free Language, because the Grammar G which generates the language L is Context Free Grammar. A Grammar G is CFG if all of its productions are of the form A->α, where A is a single non-terminal and α belongs to (V∪ T)* , i.e  α can be a string of terminals and/or Non-terminals. (V represents a non-terminal and T represents a terminal)   

Option C : L is a Regular Language, Because we are able to write a regular expression for it ( and also able to make a Finite Automaton), which is (00)+.

Option B :  Hence This option is Correct, because L is Regular but not 0+, as we proved above.

Which one of the following regular expressions is NOT equivalent to the regular expression (a + b + c)*?
  • a)
    (a* + b* + c*)*
  • b)
    (a*b*c*)*
  • c)
    ((ab)* + c*)*
  • d)
    (a*b* + c*)*
Correct answer is option 'C'. Can you explain this answer?

Ravi Singh answered
A) (a* + b* + c*)*  = ( ^ + a+aa+.. ..+b+bb+...+c+cc...)* = (a+b+c+ aa+..+bb+..+cc+..)*= (a+b+c)*  [any combination of rest of aa ,bb,cc, etc already come in (a+b+c)* ]
(a*b*c*)* = (a*+b*+c* +a*b*+b*c*+a*c*+..)*= (a+b+c+....)* = (a+b+c)*
((ab)* + c*)* =(ab+c+^+abab+...)* = (ab+c)*
(a*b* + c*)* = (a*+b*+c*+...)* =(a+b+c+..)* = (a+b+c)*
 

Given the language L = {ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa
  • a)
    1, 2 and 3
  • b)
    2, 3 and 4
  • c)
    1, 2 and 4
  • d)
    1, 3 and 4
Correct answer is 'C'. Can you explain this answer?

Shivam Sharma answered
The answer is c.Any combination of strings in set {ab, aa, baa} will be in L*.….1) “abaabaaabaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “ab aa baa ab aa”….2) “aaaabaaaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “aa ab aa aa”….3) “baaaaabaaaab” cannot be partitioned as a combination of strings in set {ab, aa, baa}….4) “baaaaabaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “baa aa ab aa”

Chapter doubts & questions for Theory of Computation - GATE Computer Science Engineering(CSE) 2026 Mock Test Series 2026 is part of Computer Science Engineering (CSE) exam preparation. The chapters have been prepared according to the Computer Science Engineering (CSE) exam syllabus. The Chapter doubts & questions, notes, tests & MCQs are made for Computer Science Engineering (CSE) 2026 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests here.

Chapter doubts & questions of Theory of Computation - GATE Computer Science Engineering(CSE) 2026 Mock Test Series in English & Hindi are available as part of Computer Science Engineering (CSE) exam. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.

Top Courses Computer Science Engineering (CSE)

Signup to see your scores go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup