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

#4281
260
views
0 answers
1 votes
an intro to finite automata by peter linz
Find a regular grammar that generates the language L (aa* (ab+ a)*).how to convert this into finite automata?? and also how to form regular grammer ?
User Avatar
#4282
2.0k
views
1 answers
1 votes
TOC DPDA vs NPDA
How many stacks are available with DPDA and NPDA? I assume it is 1 with DPDA and n with NPDA where n is some constant.Assume i have a language ,over alphabet a,b,c, ... It is a CFL. Now can DPA handle this ?If yes,then how?If not,then why?
User Avatar
#4283
487
views
1 answers
1 votes
Mod Machine
Can we have a mod- n machine with states less than n?Does it exist for a particular n?
User Avatar
#4284
440
views
1 answers
1 votes
TOC NFA
Is it possible to convert NFA with e-moves to NFA without e-moves ?I have read that using e-closure we can convert the NFA with e-moves to DFA.But can we also convert NFA with e-moves to NFA without e-moves?
User Avatar
#4285
351
views
1 answers
1 votes
intro to formal language by peter linz
Is it true that for every nfa M = (Q, Σ,δ,q0,F)the complement of L (M)is equal to the set {w ∈ Σ* :δ*; (q0,w) ∈ (Q – F) = Ø}? If so, prove it; if not, give a counterexample.plz explain this ques by taking some simple example
User Avatar
#4286
2.5k
views
1 answers
1 votes
TOC DFA extended transition function
When we define DFA extended transition function :δ(q, e) = δ( q).Assume this is extended transition function with q as state and e as epsilon.Now what does e means ... on same state.But DFA should hang on e,as e is not defined in DFA.?
User Avatar
#4287
539
views
1 answers
1 votes
TOC NFA epssilon transition
In case of NFA, assume i have defined e(epsilon transition) from qo to q1:-Now if e comes on qo,then can i stay on same qo or do i need to follow transition from qo to q1?
User Avatar
#4288
2.1k
views
1 answers
1 votes
TOC Number of strings
Assume my Alphabet set($\sum$) :-{0,01,10,110}Now we say number of strings of length n in universal language= (e)^n // e is the cardinality of alphabet ... this formulae written is correct?If yes,then is there some issue with my ($\sum$)?
User Avatar
#4289
816
views
1 answers
1 votes
Theory of computation language complement
Let L be a given language $L{}'$ represents L complement.What will be result of following operations?a. ( $L{}*$)${}'$b. ( $L{}'$)${}*$
User Avatar
#4290
525
views
1 answers
1 votes
introduction to formal languages(peter linz)..7(g) and 7(e)
in 7e what is the ans and in 7g if specific condition that is not equal to 6 is to be constructed then how can we consider middle situation?7e-- L= {w :(na(w) – nb(w)) mod 3 > 0}.7g--L= {w: |w| mod 3 = 0, |w| ≠6}.
User Avatar
#4291
1.1k
views
2 answers
1 votes
an introduction to formal languages (peter linz) chapter2..excercise ..7th (d)
L= {w: na(w) mod 3 >nb(w)mod 3}. how we will make dfa of this?
User Avatar
#4292
2.1k
views
1 answers
2 votes
GATE 2017 Mock
Consider the Following regular expressionsr1 = 1(0 + 1)*r2 = 1(1 + 0)+r3 = 11*0What is the relation between the languages generated by the regular expressions above ?a) L ( ... L(r2) ⊆ L(r1) Also Please tell explain the value of 1(1 + 0)+ .
User Avatar
#4293
5.8k
views
3 answers
3 votes
Why L = { w x w ∣ w , x ∈ ( a + b ) + } is not regular?
We can say there are four types of strings in the language so the regex will be: a(a+b)+a + b(a+b)+b + a(a+b)+b + b(a+b)+a Please expleain where I am wrong
User Avatar
#4294
704
views
2 answers
1 votes
Toc dfa
In cross product method of dfa If one dfa is M1 and another is M2M1 X M2!= M2 X M1Is it Right or wrong I am little bit confused
User Avatar
#4295
326
views
0 answers
1 votes
theory of computation by cohan
Convert regular expression to dfa(i) (ab*)*(ii) (a+ab)*(a+^)
User Avatar
#4296
188
views
1 answers
1 votes
self doubt
identify the class of language{a^(m)b^(n)} for followinga) m + n = 10b) m + n <=10c)m+n>10d) m+n<10e) m + n>=10f) m/n = 10g) m - n = 10
User Avatar
#4297
331
views
0 answers
1 votes
TOC RL
If we number sigma* in dictionary order then sigma* is countable infinite. On the other hand sigma* is the superset of all the lunguagesso is sigma* regular?
User Avatar
#4298
446
views
1 answers
1 votes
#NFA to DFA
When we convert a NFA to a DFA we count dead state in DFA or not?
User Avatar
#4299
248
views
0 answers
1 votes
Deterministic Push down automata
What will be the DPDA of a language L = {aibj|for every prefix of the string |n(a)-n(b)|≤2 where n(a)=number of a & n(b)=number of b}
User Avatar
#4300
177
views
0 answers
1 votes
Context free languages
The number of languages from the below given options that are Deterministic Context Free languages are?(a) apbqcrds | p+q=r+s(b) apbqcrds | p+r=q+s(c) wxwR | w∈(0,1) x∈(a,b)(d) aibjck ... Answer is (4).. Why????
User Avatar
Page: