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

0 votes
2 answers
3931
GKP Book
Q:)The following CFG, S-> aB/ bA A->a/ aS/ bAA B -> b/ bS/ aBB generates strings with (a) Odd number of a's & odd number of b’s (b) Even number of a's & even number of b's (c) Equal number of a’s & b’s (d) Odd number of a’s & even number of b’s
Q:)The following CFG, S- aB/ bAA->a/ aS/ bAAB - b/ bS/ aBBgenerates strings with(a) Odd number of a's & odd number of b’s(b) Even number of a's & even number of b's(c) ...
User Avatar
0 votes
0 answers
3932
Left linear grammar to regular expression
User Avatar
0 votes
1 answer
3933
For each regular expression, give two strings that are in the corresponding language and two strings that are not.
For each regular expression, give two strings that are in the corresponding language and two strings that are not.1. (a + b)∗ab(a + b)∗2. b∗ab∗ab∗3. a + (a∗b)...
User Avatar
1 votes
1 answer
3936
Self Doubt
If a language L is Context Free Language then what can we say about $L^-$ (Complement of L): 1. It is surely not Context Free Language? 2.It may or may not be Context Free Language?
If a language L is Context Free Language then what can we say about $L^-$ (Complement of L):1. It is surely not Context Free Language?2.It may or may not be Context Free ...
User Avatar
0 votes
0 answers
3937
Generate CFG
L={x ∈ (0,1)* | |x|>1 and symbol at position i is same at position i+2}.Generate the grammar for L 1) A -> 0B | ∈ B -> 1A | ∈ 2) S -> A | B | C | D A -> 0A | 00 B -> 1B | 11 C -> 10C | 10 D -> 01D | 01 3) A -> 00B | AA B -> 11A | ∈ 4) none of the above
L={x ∈ (0,1)* | |x|>1 and symbol at position i is same at position i+2}.Generate the grammar for L1) A - 0B | ∈ B - 1A | ∈2) S - A | B | C | D A - 0A | 00 ...
User Avatar
0 votes
2 answers
3938
GNF Question
Can GNF contains ε example - S-----> aε is it in GNF i.e can a terminal have an ε afterwards and will that be in GNF?
Can GNF contains ε example - S - aε is it in GNF i.e can a terminal have an ε afterwards and will that be in GNF?
User Avatar
1 votes
1 answer
3939
Doubt :Regular Language
L={ W(W^r) , W ∈ (a,b)* } W^r is reverse of W. Is it a regular language ? please Explain.
L={ W(W^r) , W ∈ (a,b)* }W^r is reverse of W.Is it a regular language ?please Explain.
User Avatar
0 votes
0 answers
3940
Self Doubt
Is there any method to check equivalence of two regular expressions other than checking all strings of two set? I mean sometimes I may miss a string.
Is there any method to check equivalence of two regular expressions other than checking all strings of two set?I mean sometimes I may miss a string.
User Avatar
2 votes
1 answer
3941
Decidable or undecidable
If M is a turing machine and Language accepted by that turning machine is L(M) such that L is regular language. Whether this Statement is decidable or undecidable?
If M is a turing machine and Language accepted by that turning machine is L(M) such that L is regular language. Whether this Statement is decidable or undecidable?
User Avatar
0 votes
0 answers
3946
doubt
$L= \{ w \mid f(w)%8 = 0 , f(w)$ returns decimal value of binary number$, \Sigma =\{0,1\}\}$. Draw the transition diagram.
$L= \{ w \mid f(w)%8 = 0 , f(w)$ returns decimal value of binary number$, \Sigma =\{0,1\}\}$.Draw the transition diagram.
User Avatar
1 votes
1 answer
3949
Identify type of grammer
Identify type of grammer:- S-> a | $\epsilon$ 1. TYPE 0 2. TYPE 1 3. TYPE 2 4. TYPE 3
Identify type of grammer:-S- a | $\epsilon$1. TYPE 02. TYPE 13. TYPE 24. TYPE 3
User Avatar
0 votes
2 answers
3950
How is this result true?
How come L1∩ L2 = (L1' U L2')'
How come L1∩ L2 = (L1' U L2')'
User Avatar
Page: