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

Hot questions in Theory of Computation

4 votes
2 answers
4722
minimal DFA
construct a Minimal dfa in which every a is followed by b , so language will be L = { ε , ab ,.......,............., } why epsilon will be included here ????
construct a Minimal dfa in which every a is followed by b , so language will be L = { ε , ab ,.......,............., }why epsilon will be included here ????
User Avatar
0 votes
0 answers
4724
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
4 votes
1 answer
4725
Test by Bikram | Theory of Computation | Test 1 | Question: 6
If L is any regular language accepted by Minimal Finite Automaton with $n$ states, then the number of states in Minimal Finite Automaton to accept Prefix(L) is: $n$ $n+1$ $n+2$ $2n$
If L is any regular language accepted by Minimal Finite Automaton with $n$ states, then the number of states in Minimal Finite Automaton to accept Prefix(L) is:$n$$n+1$$n...
User Avatar
1 votes
1 answer
4726
TOC Doubt
Write the Regular Expression in which two a's should not come together? Please tell how to write this R.E in a step by step way, thanks!
Write the Regular Expression in which two a's should not come together?Please tell how to write this R.E in a step by step way, thanks!
User Avatar
7 votes
2 answers
4727
Convert RE to Left Linear Grammer
How to convert a Regular Expression to Left Linear Grammar ? Eg : (0+1)*00(0+1)*
How to convert a Regular Expression to Left Linear Grammar ?Eg : (0+1)*00(0+1)*
User Avatar
0 votes
2 answers
4728
self doubt
B = {1ky | y is in {0, 1}* and y contains at least k 1s, for k >= 1} explain it is regular or not ?
B = {1ky | y is in {0, 1}* and y contains at least k 1s, for k >= 1}explain it is regular or not ?
User Avatar
0 votes
0 answers
4730
finite autometa
the number of state of the FSM required to simulate the behavior of a computer with a memory capable of storing m words each of length is n bit is: 1) m*2^n 2)2^m-n 3)2^mn 4)2^m+n
the number of state of the FSM required to simulate the behavior of a computer with a memory capable of storing m words each of length is n bit is:1) m*2^n2)2^m-n3)2^mn4)...
User Avatar
1 votes
0 answers
4734
introduction to computer theory by daniel cohen 2nd edition Chapter#05 Finite automata question 12
Suppose a particular FA, called FIN, has the property that it had only one final state that was not the start state. During the night, vandals come and switch the + sign ...
User Avatar
1 votes
1 answer
4735
DFA/NFA
How many number of states will be there in minimal DFA for the regular expression a* b* c* d* ??
How many number of states will be there in minimal DFA for the regular expression a* b* c* d* ??
User Avatar
2 votes
2 answers
4736
L={<M> : M is a TM that accepts all even numbers }
L={<M> : M is a TM that accepts all even numbers } is it recursive/R.E??
L={<M : M is a TM that accepts all even numbers }is it recursive/R.E??
User Avatar
2 votes
2 answers
4737
are following langauges CFL
How to check whether following language are context free 1)L= {a^nb^m ; n<=m<=3n} 2)L={w:2na(w) <=nb(w)<=3na(w) making NPDA or DPDA is not easy/convenient perhaps
How to check whether following language are context free1)L= {a^nb^m ; n<=m<=3n}2)L={w:2na(w) <=nb(w)<=3na(w) making NPDA or DPDA is not easy/convenient perhaps
User Avatar
2 votes
2 answers
4739
Regular Language
Given two languages L1 = Φ and L2 = {a}. What is the representation of L1L2*UL1*?
Given two languages L1 = Φ and L2 = {a}. What is the representation of L1L2*UL1*?
User Avatar
Page: