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

1 votes
1 answer
3181
test series
S→0A|1B|0|1 A→0S|1D|1 B→0C|1S|0 C→1D|0S|1 D→0C|1S|0 The number of states and final states in min DFA are-------?
S→0A|1B|0|1 A→0S|1D|1B→0C|1S|0C→1D|0S|1D→0C|1S|0 The number of states and final states in min DFA are -?
User Avatar
3 votes
2 answers
3183
regular expressions
Answer is c. but i think it should be b as r1 = (0+1)* = r2=r3. please correct me if i m wrong
Answer is c. but i think it should be b as r1 = (0+1)* = r2=r3. please correct me if i m wrong
User Avatar
2 votes
0 answers
3184
Test series
How L1 is regular...? Explain...
How L1 is regular...? Explain...
User Avatar
1 votes
1 answer
3185
Test series
Which of the following are decidable? 1. Complement of a regular language is infinite. 2. Whether a given CFG is regular
Which of the following are decidable?1. Complement of a regular language is infinite.2. Whether a given CFG is regular
User Avatar
2 votes
1 answer
3186
gateforum test series
Given a finite automata M, is it the minimum state FA accepting L(M) is this problem decidable, if yes then why?
Given a finite automata M, is it the minimum state FA accepting L(M)is this problem decidable, if yes then why?
User Avatar
3 votes
0 answers
3187
Decidability
a) L is decidable b) L is undecidable c) L is regular d) None of these
a) L is decidableb) L is undecidablec) L is regulard) None of these
User Avatar
1 votes
2 answers
3188
Self oubt
Are the languages produced (a+b)* and (a*b*)* same?
Are the languages produced (a+b)* and (a*b*)* same?
User Avatar
1 votes
0 answers
3190
Test series
HOW is L2 CFL?
HOW is L2 CFL?
User Avatar
2 votes
1 answer
3191
Testseries
How is L3 regular?
How is L3 regular?
User Avatar
1 votes
1 answer
3194
minimum no. of states in dfa in which no. of "a" divisible by 8
I can use 4 state dfa for no. of a should be divisible by 4 then minimum = 4 , or we have to construct dfa with 8 states ??
I can use 4 state dfa for no. of a should be divisible by 4 then minimum = 4 , or we have to construct dfa with 8 states ??
User Avatar
3 votes
1 answer
3195
automata
How many states in dfa of X= { (a+b)* where no of a is divisible by 4 and 8}
How many states in dfa of X= { (a+b)* where no of a is divisible by 4 and 8}
User Avatar
1 votes
0 answers
3196
ace test
A is a P-problem B is a NP problem and L= A intersection B , then L is 1.always P 2.L is NP but may not be P
A is a P-problem B is a NP problem and L= A intersection B , then L is1.always P2.L is NP but may not be P
User Avatar
2 votes
1 answer
3198
Turing Computatbe Function
Which of the following functions are Turing Machine computable? $1) \ n \times (n-1) \times (n-2) ......1$ $2)\{log_2n\}$ $3)\Large2^{2^n}$
Which of the following functions are Turing Machine computable?$1) \ n \times (n-1) \times (n-2) ......1$$2)\{log_2n\}$$3)\Large2^{2^n}$
User Avatar
2 votes
1 answer
3199
TOC - Regularity
Which of the following languages are regular?
Which of the following languages are regular?
User Avatar
2 votes
1 answer
3200
TOC - Language Interpretation
$L_1=\{a^nb^nc^n\ |n>=0\}$ $L_2=\{a^{2n}b^{2n}c^{2n}\ |n>=0\}$ $L_3=\{ a^{2n}b^{2n}c^n\ |n>=0\}$ Options : $1)\ L_2 \subseteq L_1 \&L_2 \subseteq L_3 $ $2)\ L_2 \subseteq L_1 \&L_2 \not\subset L_3 $
$L_1=\{a^nb^nc^n\ |n>=0\}$$L_2=\{a^{2n}b^{2n}c^{2n}\ |n>=0\}$$L_3=\{ a^{2n}b^{2n}c^n\ |n>=0\}$Options :$1)\ L_2 \subseteq L_1 \&L_2 \subseteq L_3 $$2)\ L_2 \subseteq L_1 ...
User Avatar
Page: