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

0 votes
0 answers
4421
Doubt
How Arithmetic expressions with matched pairs of parentheses is X→XbX∣XcX∣dXf∣g ???
HowArithmetic expressions with matched pairs of parentheses isX→XbX∣XcX∣dXf∣g ???
User Avatar
0 votes
0 answers
4422
Regular languages properties
Are regular languages closed under inverse substitution?
Are regular languages closed under inverse substitution?
User Avatar
6 votes
1 answer
4423
TOC :Regular Languages
Which of the following is not a regular language? a) $\{ w ( w_r )^* \mid w \in \{0,1\}^* \}$ b) $\{w^n w^m \mid 0\leq n\leq m, w \in \{0,1\} \}$
Which of the following is not a regular language?a) $\{ w ( w_r )^* \mid w \in \{0,1\}^* \}$b) $\{w^n w^m \mid 0\leq n\leq m, w \in \{0,1\} \}$
User Avatar
0 votes
1 answer
4424
turing machine
Construct TM for L ={a^nb^nc^n|n>=1}.
Construct TM for L ={a^nb^nc^n|n>=1}.
User Avatar
0 votes
0 answers
4425
Minimal DFA
Construct a minimal DFA which accepts set of all strings over {a,b} such that 2nd symbol from R.H.S is 'a' ?
Construct a minimal DFA which accepts set of all strings over {a,b} such that 2nd symbol from R.H.S is 'a' ?
User Avatar
1 votes
1 answer
4427
Pda for language
Construct pda for l={ a^2n b^n |n>=1}.
Construct pda for l={ a^2n b^n |n>=1}.
User Avatar
0 votes
3 answers
4428
michael sipser chp 1, 3rd edition, Q 12 , dfa
let D= {w | w contains an even no. of a's and an odd no. of b's and does not contain the substring ab } give a DFA with Five states that recognizes D and a regular expression that generates D.
let D= {w | w contains an even no. of a's and an odd no. of b's and does not contain the substring ab }give a DFA with Five states that recognizes D and a regular express...
User Avatar
1 votes
1 answer
4429
michael sipser chpater 1 3rd edition Q. 9 nfa
Give state diagrams of NFAs recognizing the concatenation of the languages a.) {w | the length of w is at most 5 } b.) {w | every odd position of w is 1 } The NFA has to be made by concatenating two different NFAs. how can this be done ?
Give state diagrams of NFAs recognizing the concatenation of the languagesa.) {w | the length of w is at most 5 }b.) {w | every odd position of w is 1 }The NFA has to be ...
User Avatar
1 votes
0 answers
4430
michael sipser Chapter 1, 3rd edition, question8 a , regular languages
give the state diagram of NFAs recognizing the union of the following languages a.) {w |w begins with a 1 and ends with a 0 } b.} {w | w contains at least three 1s } This is how i have solved it. is this correct ?
give the state diagram of NFAs recognizing the union of the following languagesa.) {w |w begins with a 1 and ends with a 0 }b.} {w | w contains at least three 1s }This is...
User Avatar
4 votes
1 answer
4431
CFL and DCFL
If L1 = { anbncm | n.m >0 } L2 = { anbmcm | n, m > 0} Which of these following are false? 1) L1 ∩ L2 is CFL. 2) L1 ∪ L2 is CFL. 3) L1 and L2 are CFL. 4) L1 ∩ L2 is CSL. I think (1) is FALSE as L1 ∩ L2 becomes CSL. PLease correct me if iam wrong.
If L1 = { anbncm | n.m >0 }L2 = { anbmcm | n, m 0}Which of these following are false?1) L1 ∩ L2 is CFL.2) L1 ∪ L2 is CFL.3) L1 and L2 are CFL.4) L1 ∩ L2 is CSL...
User Avatar
0 votes
2 answers
4432
Recursive enumerable sets
A is recursive if both A and its complement are accepted by turing machine True or false
A is recursive if both A and its complement are accepted by turing machineTrue or false
User Avatar
0 votes
2 answers
4433
finite language, cfl
Is {a^nb^n|n>0} a finite language?
Is {a^nb^n|n>0} a finite language?
User Avatar
0 votes
0 answers
4434
http://www.cs.rice.edu/~nakhleh/COMP481/
Can anybody please explain this reduction and rice theorem. http://www.cs.rice.edu/~nakhleh/COMP481/ Thanks
Can anybody please explain this reduction and rice theorem.http://www.cs.rice.edu/~nakhleh/COMP481/Thanks
User Avatar
0 votes
2 answers
4435
closure property of cfl
Can complement of a non-regular language be regular?
Can complement of a non-regular language be regular?
User Avatar
0 votes
1 answer
4436
Digital Electronics
Size of rom for converting binary code to gray code?
Size of rom for converting binary code to gray code?
User Avatar
0 votes
2 answers
4437
regular expression
write the regular expression for the given language L= { W | NO OF a mod 2= 1} (odd no of a's )
write the regular expression for the given language L= { W | NO OF a mod 2= 1} (odd no of a's )
User Avatar
0 votes
1 answer
4438
Doubt
can language wcwR accepted by a single queue? i want someone to parse abcRcba using a QUEUE
can language wcwR accepted by a single queue?i want someone to parseabcRcba using a QUEUE
User Avatar
0 votes
3 answers
4439
Regular Expression
Given statement is true or false 1. L is regular language $\Leftrightarrow$ Ǝ a regular expression without $\bigstar$ answer in detail
Given statement is true or false 1. L is regular language $\Leftrightarrow$ Ǝ a regular expression without $\bigstar$ answer in detail
User Avatar
2 votes
3 answers
4440
Theory proof
1. The complement of a finite language is always infinite 2. The complement of an infinite language may be finite or infinite .. both statements are true .. i can proof using examples .. can someone give me logical theory proof ?
1. The complement of a finite language is always infinite2. The complement of an infinite language may be finite or infinite ..both statements are true .. i can proof usi...
User Avatar
Page: