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

7 votes
2 answers
6221
TOC -Number of Equivalence Classes
The number of equivalence classes which exist for the following regular expression R are ______. $R=(a+b)^*b(a+b+\epsilon )$ what is the meaning of equivalence classes here...
The number of equivalence classes which exist for the following regular expression R are ______. $R=(a+b)^*b(a+b+\epsilon )$ what is the meaning of equivale...
User Avatar
4 votes
2 answers
6222
TM
Consider the following turning machine (where,,$\$ $ is represent accept the string). If the string is $01010$ then what will be the output? $10100$ $10101$ $10110$ $10011$
Consider the following turning machine (where,,$\$ $ is represent accept the string).If the string is $01010$ then what will be the output?$10100$$10101$$10110$$10011$
User Avatar
5 votes
4 answers
6223
PDA
Consider the following push down automata. The language accepted by above PDA is_______. Regular but infinite. DCFL but not regular. CFL but not DCFL Finite language.
Consider the following push down automata.The language accepted by above PDA is_______.Regular but infinite.DCFL but not regular.CFL but not DCFLFinite language.
User Avatar
4 votes
1 answer
6224
Pumping Lemma
Prove or Disprove below language is regular or not L1={w|w∈∑* where w visit all state of M atleast once where M is machine accepting L1 L2={w|w∈∑* where w visit all state of M equal no of times where M is machine accepting L2
Prove or Disprove below language is regular or notL1={w|w∈∑* where w visit all state of M atleast once where M is machine accepting L1 L2={w|w∈∑* where ...
User Avatar
2 votes
0 answers
6225
No of final state
A FA accepting language L(A) has n states and m transition.L(A) is given as L(A)={x| if x∊L(A) then u∊L(A) for ∃u,v∊∑* where x=uv } Find no of final state in above NFA?
A FA accepting language L(A) has n states and m transition.L(A) is given asL(A)={x| if x∊L(A) then u∊L(A) for ∃u,v∊∑* where x=uv } Find no of ...
User Avatar
1 votes
0 answers
6229
determine ambiguous or unambiguous
if any language is given , how we can determine that its grammar is ambiguous or unambiguous ex. L = {anbcm | n > 1, m ≤ n} its very big confusion for me . please explain in brief ?
if any language is given , how we can determine that its grammar is ambiguous or unambiguousex. L = {anbcm | n 1, m ≤ n}its very big confusion for me . please explai...
User Avatar
3 votes
2 answers
6230
toc
$L1$ is a Context free language (CFL), $L2$ is a Deterministic Context free language (DCFL) and , $L = L1 \cap\overline{L2}$ then $L$ is a) Need not be CFL b) not CFL c)DCFL
$L1$ is a Context free language (CFL), $L2$ is a Deterministic Context free language (DCFL)and , $L = L1 \cap\overline{L2}$then $L$ isa) Need not be CFLb) not CFLc)DCFL
User Avatar
1 votes
1 answer
6231
Regular
L={xwwr |x,w∈(a+b)+} this is not regular proof ?
L={xwwr |x,w∈(a+b)+} this is not regularproof ?
User Avatar
3 votes
1 answer
6232
toc
which languages are closed under membership? also explain how r u finding it?
which languages are closed under membership?also explain how r u finding it?
User Avatar
1 votes
1 answer
6234
TOC
Why Min(L) ≠ Complement((Prefix(L))? Min(L) is set of all strings w in L where every proper prefix of w is not in L Prefix(L) is set of all prefix of w ∈L
Why Min(L) ≠ Complement((Prefix(L))?Min(L) is set of all strings w in L where every proper prefix of w is not in LPrefix(L) is set of all prefix of w ∈L
User Avatar
2 votes
0 answers
6235
The vernacular English ,if considered a formal language is a
The vernacular English ,if considered a formal language is a _______________________________ a) Regular b) CFL c) CSL
The vernacular English ,if considered a formal language is a _______________________________a) Regularb) CFLc) CSL
User Avatar
1 votes
1 answer
6236
Question on deciding type of language
Given answer: A Please explain
Given answer: APlease explain
User Avatar
1 votes
1 answer
6237
Uniquely derivable strings from grammar
The given answer to the problem is 1 ('a'). But I think that strings 'a+a' & 'a*a' can also be derived from the grammar. Please correct me if I am wrong.
The given answer to the problem is 1 ('a'). But I think that strings 'a+a' & 'a*a' can also be derived from the grammar. Please correct me if I am wrong.
User Avatar
5 votes
2 answers
6239
what is the left quotient of a CFL with a regular language ?
If I take L=a^n b^n and R=(a+b)* so I am getting the value of L/R to be regular ,Am I correct ?
If I take L=a^n b^n and R=(a+b)* so I am getting the value of L/R to be regular ,Am I correct ?
User Avatar
Page: