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
212
DRDO CSE 2022 Paper 2 | Question: 10
Construct a Deterministic Finite Automaton $\text{(DFA)}$ with $5$ states that accepts all strings with $0101$ as a substring.
Construct a Deterministic Finite Automaton $\text{(DFA)}$ with $5$ states that accepts all strings with $0101$ as a substring.
User Avatar
0 votes
2 answers
220
Theory of Computation | Automata
L= {$a^nb^nc^nd^n; n\geq 0$} Given Language is a CSL TRUE FALSE
L= {$a^nb^nc^nd^n; n\geq 0$} Given Language is a CSLTRUEFALSE
User Avatar
2 votes
1 answer
224
complementation of language
I have a language L = {ε,a}. What will be $L^{C}$? Will it be Φ or {aa, aaa, aaaa, ...} ?
I have a language L = {ε,a}. What will be $L^{C}$? Will it be Φ or {aa, aaa, aaaa, ...} ?
User Avatar
2 votes
1 answer
225
What should the answer be?
I think the answer should be (B) would be right, because lets say in R, there is a FD NPA -> CK, it won't qualify as BCNF even if CK is single attribute
I think the answer should be (B) would be right, because lets say in R, there is a FD NPA - CK, it won't qualify as BCNF even if CK is single attribute
User Avatar
1 votes
1 answer
227
TOC | Made Easy Test Series | Q.13
Consider the following statement S: $\left \{ a^{n}b^{n+k}|n\geq 0,k\geq 1 \right \} \cup \left \{a^{n+k}b^{n}|n\geq 0,k\geq 3 \right \}$ is DCFL The above statement is: TRUE FALSE
Consider the following statementS: $\left \{ a^{n}b^{n+k}|n\geq 0,k\geq 1 \right \} \cup \left \{a^{n+k}b^{n}|n\geq 0,k\geq 3 \right \}$ is DCFLThe above statement is:TRU...
User Avatar
2 votes
1 answer
228
ace academy ToC
I don’t get the explanation, How do you categorize grammer on the basis of production?
I don’t get the explanation, How do you categorize grammer on the basis of production?
User Avatar
0 votes
0 answers
229
context free
Let $L = \{a^nb^nc^nd^n | n\ge1\}$. Show that $L$ can be expressed as the intersection of two context-free languages.
Let $L = \{a^nb^nc^nd^n | n\ge1\}$. Show that $L$ can be expressed as the intersection oftwo context-free languages.
User Avatar
Page: