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

#4341
1.7k
views
1 answers
1 votes
Count the Number of Dfa's
How many DFA's can be constructed with 3 states and 2 input symbols which accept empty language?
User Avatar
#4342
497
views
1 answers
2 votes
minimal dfa , ,is final dfa below drawn by me is correct ,from epsilon NFA , thanks
...
User Avatar
#4343
510
views
0 answers
1 votes
Toc peter Linz ex 4.4
Can anybody plzz explain how we got the diagram of L1/L2 in the example given in book???
User Avatar
#4344
836
views
2 answers
4 votes
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 ????
User Avatar
#4345
343
views
1 answers
1 votes
Toc peter Linz example 3.13
According the Peter Linz Book, the two example the Grammar G1 = ({S},{a,b},S,P1) with P1 given asS -> abS|aand G2 = ({S,S1,S2,},{a,b},S,P2)S -> S1abS1 - ... it's regular expression can't be a(ab)* .In the book it show its aab(ab)* but how.
User Avatar
#4346
635
views
1 answers
1 votes
made easy work book
how many strings of at most 4 bits that start with and end with "0" belongs to the language described by (01+10)* 0 (0+1)* ?? please give explanation..
User Avatar
#4347
1.7k
views
3 answers
3 votes
dfa problem
Construct a minimal DFA, which accepts set of all strings over {0, 1}, which when interpreted as binary number is divisible by ‘3’. , IS IS this solution right because null string is also accepted which is not in language
User Avatar
#4348
1.5k
views
2 answers
1 votes
made easy work book
the regular expression is given by R=( ab|abb)* bbab which of the following does not belong to R??a) ab ab abb) ab bb abc) ababbabbbabd) abbabbbab
User Avatar
#4349
1.1k
views
1 answers
2 votes
dfa design
Design a DFA over w ∈ {a,b}* such that number of a = 2 and there is no restriction over length of b.AnswerWe will explain this intuitive approachStep 1 Make ... to accept null string too ???? in dfa and we should make A as also final
User Avatar
#4350
1.2k
views
1 answers
1 votes
DFA/NFA
How many number of states will be there in minimal DFA for the regular expression a* b* c* d* ??
User Avatar
#4351
1.6k
views
1 answers
1 votes
Toc Peter Linz
can anyone provide solution of Toc Peter Linz 6th edition ?
User Avatar
#4352
285
views
1 answers
1 votes
Σ*∙Σ^+ = Σ^+∙Σ* = Σ^+
How it is true ?can somebody explain it?Thanks lot :)
User Avatar
#4353
428
views
0 answers
1 votes
peter linz
a) Find a regular expression and finite automata for all bit strings, with leading bit 1 interpreted as a binary integer, with values not between 10 and 30.b) is L={w1cw2:w1,w2 ={ ... L={w1cw2:w1,w2 ={a,b}*,w1!=w2^R, with alphabet={a,b,c}
User Avatar
#4354
221
views
0 answers
1 votes
Self Dubt
Epsilon is terminal or non terminal in cfg?
User Avatar
#4355
772
views
1 answers
1 votes
Regular Languages and Finite Automata
A language L = {w|w contain 'a' in every odd position, w belongs to {a, b}*}Doubt: Here, null string will be accepted or not. Please explain? ... questions whether to include null string or not. Please suggest some way to sort this out.
User Avatar
#4356
1.2k
views
2 answers
4 votes
peter linz ex
User Avatar
#4357
249
views
1 answers
2 votes
peter linz ex. (regular languages)
User Avatar
#4358
2.0k
views
1 answers
2 votes
Peter Linz Edition 4 Exercise 7.1 Question 3.c,3.d,4.f,4.j (Page No. 183)
Q3) Given,$L_1 = (aaa^*b)$L_2 = (aab^*aba^*)$Find (c) the union of $L_1$ and $L_2$, and also find (d) $L_1 - L_2$.Q4) Find the npda's of the following:f) $L = \{ a^nb ... $L = \{w : 2n_a(w) \leq n_b(w)) \leq 3n_a(w) \}$.
User Avatar
#4359
388
views
1 answers
1 votes
Finite Atomata
Complement of non regular language is regular or not?
User Avatar
#4360
515
views
1 answers
0 votes
made easy theory book
Let r1= (b* ab* ab* ab*)*, r2= (b* ab* ab*)* what is L(r1) intersection L(r2)???
User Avatar
Page: