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

4 votes
3 answers
4581
How many DFAs are possible?
How many 3 state DFA's can be constructed with a designated initial final state that accepts empty language over alphabet {a,b}?
How many 3 state DFA's can be constructed with a designated initial final state that accepts empty language over alphabet {a,b}?
User Avatar
0 votes
0 answers
4583
peterlinz
User Avatar
0 votes
3 answers
4584
theory of computation
User Avatar
0 votes
2 answers
4585
deterministic and non deterministic push down automata
Which of the following is accepted by an NDPDM but not by DPDM a)All strings in which a given symbol is present at least twice b)Even length palindromes c)Strings ending with a particular terminal d)Odd length palindromes
Which of the following is accepted by an NDPDM but not by DPDMa)All strings in which a given symbol is present at least twiceb)Even length palindromesc)Strings ending w...
User Avatar
1 votes
1 answer
4587
peter linz .theorem 6.3
LET G be any context-free grammar with (lambda) not in L(G).Then there exist an equivalent grammar G' having no (lambda) production. Q.2-> let G be any CFG without (lambda production). Then there exist a CFG G' that does not have any unit production equivalent to G Unable to understand this
LET G be any context-free grammar with (lambda) not in L(G).Then there exist an equivalent grammar G' having no (lambda) production. Q.2- let G be any CFG without (lambda...
User Avatar
0 votes
3 answers
4588
theory of computation
L = (a^n b^n a^n | n = 1,2,3) is an example of a language that is A. context free B. not context free C. not context free but whose complement is CF D. both (b) and (c)
L = (a^n b^n a^n | n = 1,2,3) is an example of a language that isA.context freeB.not context freeC. not context free but whose complement is CFD. both (b) and (c)
User Avatar
0 votes
3 answers
4589
theory of computation
Let sigma = { a,b }.Find the grammar which generates the language, where na(w) and nb(w) denote the number of a's in w and number of b's in w respectively.
Let sigma = { a,b }.Find the grammar which generates the language,where na(w) and nb(w) denote the number of a's in w and number of b's in w respectively.
User Avatar
0 votes
1 answer
4590
CFG (Timothy WIlliams)
The following CFG S->aS| bS| a| b is equivalent to the regular expression a)(a*+b)* b)(a+b)+ c)(a+b)(a+b)* d)(a+b)* (a+b)
The following CFG S->aS| bS| a| bis equivalent to the regular expression a)(a*+b)* b)(a+b)+c)(a+b)(a+b)* d)(a+b)* (a+b)
User Avatar
0 votes
1 answer
4591
theory of computation
The number of prefixes and suffixes respectively in the string "abbab" are ___ and ___ .
The number of prefixes and suffixes respectively in the string "abbab" are ___ and ___ .
User Avatar
0 votes
1 answer
4592
Designing DFA's
Design a DFA which accepts all strings over { a, b } that doesn't contain string aabb in it.
Design a DFA which accepts all strings over { a, b } that doesn't contain string aabb in it.
User Avatar
0 votes
1 answer
4593
Theory of Computation Study doubt
Are proofs in Theory of Computation required for Gate? Or will learning the theorems and skipping the proofs suffice? What about its consequences in Interviews to PSU?
Are proofs in Theory of Computation required for Gate? Or will learning the theorems and skipping the proofs suffice? What about its consequences in Interviews to PSU?
User Avatar
1 votes
1 answer
4594
context free grammar
Construct context-free grammars to accept the following languages. $\begin{align*} \large L = \left \{ 0^i1^j2^k \;\; | \;\; i \neq j \;\; or \;\; j \neq k \right \} \end{align*}$
Construct context-free grammars to accept the following languages.$$\begin{align*} \large L = \left \{ 0^i1^j2^k \;\; | \;\; i \neq j \;\; or \;\; j \neq k \right \} \end...
User Avatar
2 votes
2 answers
4595
ISI PCB 2014 C3 (A)
Prove that the language {aN : N is a composite number} is not regular.
Prove that the language {aN : N is a composite number} is notregular.
User Avatar
0 votes
1 answer
4598
let r1=(a+bb)* , r2=(a*+b* ), r3=(aa+b)* which 0f the following is true?
A)L(r1)⊆L(r2) and L(r3)⊆L(r2) b) L(r2)⊆L(r1) and L(r2)⊆L(r3) C) L(r1)=L(r3)⊆L(r2) D) L(r1)⋃L(r3)=L(r2) plz explain with explanation
A)L(r1)⊆L(r2) and L(r3)⊆L(r2)b) L(r2)⊆L(r1) and L(r2)⊆L(r3)C) L(r1)=L(r3)⊆L(r2)D) L(r1)⋃L(r3)=L(r2)plz explain with explanation
User Avatar
0 votes
1 answer
4600
Automata-Grammars
For the language L = { anbmcmdn : n , m>=1 } I came with following set of productions : S-->aSd | A A--> bAc | bc whereas the answer was given as below S--> aSd | aAd A--> bAc | bc how far is my answer correct?
For the language L = { anbmcmdn : n , m>=1 }I came with following set of productions :S >aSd | AA bAc | bcwhereas the answer was given as belowS aSd | aAdA bAc | bcho...
User Avatar
Page: