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

#4361
790
views
1 answers
0 votes
#PropertiesOfRegularLanguage
Union & Concatenation property of regular language are closed for both DFA & NFA. But while doing union or concatenation of 2 DFAs, we have to insert epsilon ... as DFA but make them epsilon-NFA. So is both property closed for DFA?
User Avatar
#4362
1.1k
views
2 answers
0 votes
DCFL or NCFL
L = {ai bj ck | i = k or j = k}Is it a DCFL or an NCFL?
User Avatar
#4363
420
views
1 answers
0 votes
Toc RL and FA
can anyone explain this Let L1 = {w ∈ {0,1}∗ | w has at least as many occurrences of (110)'s as (011)'s}. Let L2 = { ∈ {0,1}∗ | w ... is regular but not L2BL2 is regular but not L!CBoth L2 and L1 are regularDNeither L1 nor L2 are regular
User Avatar
#4364
939
views
2 answers
2 votes
Doubt whether given language is CFL?
L={a^n b^(2n+1) | n>=1}Also can you give acceping PDA diagram...plz
User Avatar
#4365
2.7k
views
2 answers
0 votes
NPDA and DPDA
Can we make NPDA? L= {anbn| n>=0,a,b are input variables}if yes then make it .
User Avatar
#4366
362
views
0 answers
1 votes
#pda #tm #deterministic
How can a DTM can simulate a NTM, but a DPDA can not simulate a NPDA. ? Reason?I read the proedure for a DTM to simulate a NTM but can not get why its not so with pda. Any clue ?
User Avatar
#4367
1.3k
views
1 answers
1 votes
Regular Language to Regular Grammar
I think the below language is Regular-L = {xy | na(x) = nb(y) where x,y $\in$ (a,b)* }Doubt : Since if we consider any string in ... - brackets are just for understanding purpose). Can some one write the regular grammar for this language?
User Avatar
#4368
3.1k
views
1 answers
2 votes
Context Free Grammar (Peter Linz)
Given the Grammar, S -> abB, A -> aaBb,B -> bbAa,A -> ∈Please explain how we get expression:-L = { ab(bbaa)^n bba (ba)^n / n>= 0 }Please explain step by step.
User Avatar
#4369
541
views
0 answers
1 votes
Closure properties
Is ((ab)*,+) closed or not closed?
User Avatar
#4370
2.2k
views
3 answers
1 votes
Peter Linz Edition 4 Exercise 3.1 Question 7 (Page No. 76) Exercise 3.3 Question 9 (Page No. 97)
Regular Expression:-Q1) What languages do the expression (∅*)* and a∅ denote?Q2) Find a regular expression and finite automata for all bit strings, with leading bit 1 interpreted ... / (number of a in w + 3*number of b) in w is even }
User Avatar
#4371
527
views
1 answers
2 votes
Regular Expression
Here is the DFA and I need to convert it to regular expression. I get two different answers when removing states in different order.i get b(c+ab)*d when I remove B ... while I get (bc*a)*bc*d when I eliminate A first. Which one is right?
User Avatar
#4372
694
views
1 answers
1 votes
Regular language
let L1 =a*b* and L2 = {ab} L3 = prefix (L1* intersection L2)where prefix(L) = { u| uv belongs L for any v} find the number of strings in L3????
User Avatar
#4373
185
views
1 answers
1 votes
Regular language
L = { $a^{i}b^{2i} $ | i>=1}Is this language regular or not ?Is there any specific way to check weather language is regular or not ?
User Avatar
#4374
360
views
1 answers
1 votes
TOC: CFG
Consider the statements:S1: Regular Expression for the language over the alphabet Σ={a} containing strings whose length is either multiple of 2 or a multiple of ... even} is a Context free language Which of the above statements are TRUE?
User Avatar
#4375
672
views
1 answers
2 votes
Identify the language
Consider the following languages:L1={an bn:n≥0 and n is not multiple of 5}L2=complement of {(0n 1n )m│m,n>0}
User Avatar
#4376
575
views
1 answers
1 votes
Identify the language
Which of the following is the language L={0n#02n#03n│n≥0}( Marks: -0.33 ) Regular but not Context free Context free but not Regular Not Context free None of these
User Avatar
#4377
373
views
1 answers
1 votes
Self Doubt In Regular Expression
Are r(*) and r* equivalent Regular Expression and What is the meaning of r(*)?
User Avatar
#4378
3.5k
views
3 answers
6 votes
DCFLs
S1: Every DCFL has unambiguous grammarS2: Every language accepted by DPDA with final state is also accepted by DPDA with empty stackS1 is given as true and S2 false.Explain how?!
User Avatar
#4379
396
views
1 answers
1 votes
Identify the language
L = { w | w $\epsilon$ (a,b)* and #a(w) - #b(w) $\leq$ 10}. Is L regular or a CFL?
User Avatar
#4380
555
views
1 answers
1 votes
Identify the language
L1 = {w | length of w is odd and its middle symbol is 0, w $\epsilon$ (0,1)*}Is it regular, a CFL or a CSL?
User Avatar
Page: