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{2024-1} & \textbf{2024-2} & \textbf{2023} & \textbf{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count} &1&1&3& 2 &2&3& 1&2&3
\\\hline\textbf{2 Marks Count} &2&3&3& 3 &3&4& 2&3&4
\\\hline\textbf{Total Marks} &5&7&9& 8 &8&11&\bf{5}&\bf{8}&\bf{11}\\\hline
\end{array}}}$$

Filter

Recent questions in Theory of Computation

1 votes
2 answers
4401
theory of computation
contruct the PDA for CFG L={set of balanced paranthesis}
contruct the PDA for CFG L={set of balanced paranthesis}
User Avatar
1 votes
1 answer
4402
finite automata
draw thee finite automata of :(DFA) 1)a*(a+b)* 2)(a+b)*a*
draw thee finite automata of :(DFA)1)a*(a+b)*2)(a+b)*a*
User Avatar
1 votes
1 answer
4404
regular expression
The length of the shortest string NOT in the language (over Σ = {a, b}) of the following regular expression is ______________. a*b*(ba)*a* A 2 B 3 C 4 D 5
The length of the shortest string NOT in the language (over Σ = {a, b}) of the following regular expression is ______________.a*b*(ba)*a*A2B3C4D5
User Avatar
1 votes
2 answers
4405
CFL AND DCFL
L={n(a)!= n(b) ,(a,b)* belongs to universal language } is CFL or DCFL explain.
L={n(a)!= n(b) ,(a,b)* belongs to universal language } is CFL or DCFLexplain.
User Avatar
1 votes
0 answers
4406
regular language
regular language infinite intersction not neccessary regular?????????? any body have example
regular language infinite intersction not neccessary regular?????????? any body have example
User Avatar
1 votes
0 answers
4407
group
what is the group in properties of closure properties in automata??
what is the group in properties of closure properties in automata??
User Avatar
1 votes
2 answers
4408
theory of computtion
find regular expression of 1. S-> 01A/10B A->0B/1 B->1A/0 and 2. A->A00 /A1/0 3. S->baS/aA A->bbA/bb
find regular expression of1.S- 01A/10BA->0B/1B->1A/0and2.A->A00 /A1/0 3.S->baS/aAA->bbA/bb
User Avatar
1 votes
2 answers
4409
Finite accepter(machine Design)
What is product automata and what is the difference between grid machine and mod machine?
What is product automata and what is the difference between grid machine and mod machine?
User Avatar
5 votes
3 answers
4410
Regular language problem
Which of the following is TRUE? S1: Any language L over an alphabet Σ,L+=L-{ϵ} is always TRUE. S2: For any automata M, L(M)≠∅( Marks: 0.00 ) S1,S2 Only S1 Only S2 Both the statements are false
Which of the following is TRUE?S1: Any language L over an alphabet Σ,L+=L-{ϵ} is always TRUE.S2: For any automata M, L(M)≠∅( Marks: 0.00 ) S1,S2 Only S1 Only S2 Bot...
User Avatar
0 votes
1 answer
4412
TOC RL and FA
Is every EPSILON-NFA a DFA given the fact that every NFA is a DFA and every NFA is EPSILON-NFA
Is every EPSILON-NFA a DFA given the fact that every NFA is a DFA and every NFA is EPSILON-NFA
User Avatar
1 votes
1 answer
4413
epsilon-NFA to DFA conversion
For the following NFA what will be corresponding DFA I m getting different automata from different methods,by directly convert it into DFA or first convert it into NFA and then DFA.
For the following NFA what will be corresponding DFAI m getting different automata from different methods,by directly convert it into DFA or first convert it into NFA and...
User Avatar
1 votes
3 answers
4414
FA with complement
Consider this FA: How many strings will be there in the complement of the language accepted by this Finite Automata? (a) Infinite (b) 2 (c) 3 (d) 0
Consider this FA:How many strings will be there in the complement of the language accepted by this Finite Automata?(a) Infinite(b) 2(c) 3(d) 0
User Avatar
0 votes
1 answer
4415
Doubt
What is "Regular set" ?
What is "Regular set" ?
User Avatar
0 votes
1 answer
4416
Total number of states in NFA
How many NFA with exactly four states can be constructed over the alphabet S= {a, b} with designated initial state?
How many NFA with exactly four states can be constructed over the alphabet S= {a, b} withdesignated initial state?
User Avatar
0 votes
1 answer
4417
Union of R.E and non R.E
What is the class of the language resulting from Union of R.E and non R.E ? (R.E => recursively enumerable)
What is the class of the language resulting from Union of R.E and non R.E ?(R.E = recursively enumerable)
User Avatar
0 votes
0 answers
4418
Normal Forms
While converting a grammar to Greibach Normal Form or Chomsky Normal Form, why do we do this - "If the start symbol S occurs on some right side, create a new start symbol S’ and a new production S’ → S."
While converting a grammar to Greibach Normal Form or Chomsky Normal Form, why do we do this - "If the start symbol S occurs on some right side, create a new start symbol...
User Avatar
0 votes
0 answers
4420
Doubt
Number of formal parameters in the declaration of a function agrees with the number of actual parameters in a use of that function is L={a^nb^mc^nd^m∣n≥1,m≥1} ? how?
Number of formal parameters in the declaration of a function agrees with the number of actual parameters in a use of that function is L={a^nb^mc^nd^m∣n≥1,m≥1} ? how...
User Avatar
Page: