Register

Web Page

Regular expressions and finite automata, Context-free grammars and push-down automata, Regular and context-free languages, Pumping lemma, Turing machines and undecidability.

$$\scriptsize{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline
\textbf{Year}& \textbf{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{2020}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count} & 2 &2&3&3&2&2&2&3&3&3&2&2.5&3
\\\hline\textbf{2 Marks Count} & 3 &3&4&3&3&3&5&3&3&3&3&3.3&5
\\\hline\textbf{Total Marks} & 8 &8&11&9&8&8&12&9&9&9&\bf{8}&\bf{9.1}&\bf{12}\\\hline
\end{array}}}$$

Filter

Recent questions in Theory of Computation

4 votes
2 answers
6322
Equivalence classes of a Language
Find all the equivalence classes of Regular Language 011 (0+1)* 011
Find all the equivalence classes of Regular Language011 (0+1)* 011
User Avatar
3 votes
1 answer
6323
Relation between given regular Expression (Finite Automata)
Let A= (a + b)* ab (a + b)*, B= a*b* and C= (a + b)*. Then the relation between A, B and C: A. A+B= C B. A+Reverse(B)= C C. Reverse(A)+B= C D. None
Let A= (a + b)* ab (a + b)*,B= a*b* andC= (a + b)*.Then the relation between A, B and C:A. A+B= C B. A+Reverse(B)= C C. Reverse(A)+B= C D. None
User Avatar
3 votes
3 answers
6325
Which of the following are not equivalent to expression (a + b + c)* ?
Which of the following are not equivalent to expression $(a + b + c)^*$? (A) $(a^* + b^* + c^*)^*$ (B) $\Bigl ( (ab)^* + c^* \Bigr )^*$ (C) $(a^* b^* c^*)^*$ (D) $(a^*b^* + c^*)^*$
Which of the following are not equivalent to expression $(a + b + c)^*$?(A) $(a^* + b^* + c^*)^*$(B) $\Bigl ( (ab)^* + c^* \Bigr )^*$(C) $(a^* b^* c^*)^*$(D) $(a^*b^* + c...
User Avatar
1 votes
1 answer
6326
The language of primes in unary is
The language of primes in unary is: A. Regular B. CFL C. DCFL D. Context Sensitive
The language of primes in unary is:A. Regular B. CFL C. DCFL D. Context Sensitive
User Avatar
2 votes
1 answer
6328
S1: L ≤ m {0n1n | n ≥ 0} then L is decidable.
Answer True/False for the statements: S1: $L ≤_m \{0^n1^n \mid n ≥ 0\}$ then $L$ is decidable. S2: if $L$ is R.E. and $L’ ⊆ L$ then $L’$ is recursively enumerable because enumerator for $L$ also enumerates $L’$.
Answer True/False for the statements:S1: $L ≤_m \{0^n1^n \mid n ≥ 0\}$ then $L$ is decidable.S2: if $L$ is R.E. and $L’ ⊆ L$ then $L’$ is recursively enumerable...
User Avatar
2 votes
3 answers
6329
Consider 2 scenarios: C1: For DFA (ϕ, Ʃ, δ, qo, F), if F = ϕ, then L = Ʃ* C2: For NFA (ϕ, Ʃ, δ, qo, F)
Consider 2 scenarios:C1: For DFA (ϕ, Ʃ, δ, qo, F),if F = ϕ, then L = Ʃ*C2: For NFA (ϕ, Ʃ, δ, qo, F),if F = ϕ, then L = Ʃ*Where F = Final states setϕ = Total st...
User Avatar
2 votes
2 answers
6330
Let Σ= {a}, assume language, L= { a^(2012.K) / K> 0}, what is minimum number of states needed in a DFA to recognize L
Let Σ= {a}, assume language, L= { a^(2012.K) / K 0}, what is minimum number of states needed in a DFA to recognize L
User Avatar
2 votes
1 answer
6331
Is this language regular?
$L = \{ a^{n}b^{m} \mid (n+m) \text{ is even}\}$
$L = \{ a^{n}b^{m} \mid (n+m) \text{ is even}\}$
User Avatar
0 votes
1 answer
6332
Which of the following statements is/are True?
(a) If $R$ is regular and $N$ is non-regular, then there exists $R+N$, which is regular. (b) If $R$ is regular and $N$ is non-regular, then there exists $R+N$, which is non-regular.
(a) If $R$ is regular and $N$ is non-regular, then there exists $R+N$, which is regular.(b) If $R$ is regular and $N$ is non-regular, then there exists $R+N$, which is no...
User Avatar
0 votes
1 answer
6333
Relationship between Problems and Languages
Is there a one to one correspondence between problems and languages? we interchangeably use these while discussing decidabilility and turing machines
Is there a one to one correspondence between problems and languages? we interchangeably use these while discussing decidabilility and turing machines
User Avatar
0 votes
2 answers
6334
Is this Language regular?
$L = \Bigl \{ \Sigma^* \Bigr \}$
$L = \Bigl \{ \Sigma^* \Bigr \}$
User Avatar
0 votes
1 answer
6336
regular expression
User Avatar
6 votes
3 answers
6338
what is the total number of strings that can be generated from the below FA ?
The FA above recognizes a set of stings of length $6$, what is the total number of strings that can be generated from the FA? $18$ $20$ $130$ None
The FA above recognizes a set of stings of length $6$, what is the total number of strings that can be generated from the FA?$18$$20$$130$None
User Avatar
0 votes
2 answers
6339
how to deal with TOC
Having trouble while doing TOC, specially with languages. Please suggest somebook / notes / lectures. Very frustrated with it.
Having trouble while doing TOC, specially with languages.Please suggest somebook / notes / lectures.Very frustrated with it.
User Avatar
1 votes
1 answer
6340
Please post the DFA for the language.
What are the number of final states in minimal DFA, where $\Sigma = \{a,b\}$, if every string starts with "aa" and length of string is not congruent to 0 mod 4? 7 6 3 5
What are the number of final states in minimal DFA, where $\Sigma = \{a,b\}$, if every string starts with "aa" and length of string is not congruent to 0 mod 4?7635
User Avatar
Page: