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

Questions without an upvoted answer in Theory of Computation

27
views
1 answers
0 votes
Regular Expression
Is this language regular or not?xww^R | x,w E (a,b)*
User Avatar
92
views
0 answers
0 votes
Regular Expression
Write Regular expression for the set of string over alphabets {a, b} starting with b and ending with odd number of a’s or even number of b’s.
User Avatar
62
views
0 answers
0 votes
DFA construction
construct a minimal DFA for the regular language L= {W | w contain 'a' in every odd position, w∈{a,b}* }
User Avatar
48
views
0 answers
0 votes
DFA
Identify language accepted by following dfa. A. L = {a^n b^m | n,m >= 1} B. L = {a^n b^m | n >= 1, m >= 0} C. L = {a^n b^m | n,m >= 0} D. None
User Avatar
110
views
0 answers
1 votes
Theory of Computation | Chomsky Hierarchy
A general query,If Regular expression (a+b)* covers the all possible languages over $\sum$= {a,b} then, why we need other type of languages?Are they ... I found these two reasons on internet and nothing else is there any other reasons here?
User Avatar
132
views
1 answers
2 votes
#TOC-regular-language
Captioncreate a DFA for language L={a^n b^m | n=(m%3) } 
User Avatar
92
views
0 answers
0 votes
Scoa021 May/June 2023
Draw a DFA and Transition table for the regular expression (a|b)*abb
User Avatar
61
views
0 answers
0 votes
CMI2024-B-02
Let M1 = (Q1, {q1}, ∆1, F1), where ∆1 ⊆ Q1 (Σ ∪ {ϵ}) Q1, be a non-deterministic finite automaton (NFA) accepting a language L1 ⊆ {0, 1} ∗ . Let ϵ denote ... = ϵ and p ′ = q1) Prove or disprove: The language L2 accepted by M2 is L ∗ 1 .
User Avatar
68
views
0 answers
0 votes
CMI 2024-PART B-02.
Let M1 = (Q1, {q1}, ∆1, F1), where ∆1 ⊆ Q1 (Σ ∪ {ϵ}) Q1, be a non-deterministic finite automaton (NFA) accepting a language L1 ⊆ {0, 1} ∗ . Let ϵ ... F1 and a = ϵ and p ′ = q1) Prove or disprove: The language L2 accepted by M2 is L*
User Avatar
260
views
1 answers
0 votes
self doubt
How a^i b^j | i !=(2j+1) is dcfl?
User Avatar
120
views
0 answers
0 votes
self doubt
what's the condition to draw PDA for a^(2j+1)b^j such that j>=1.Since the language L={aaab,aaaaabb,aaaaaaabbb,.......}.Is pda possible?
User Avatar
93
views
0 answers
0 votes
Ardens's theorem
I have a doubt in ardens theorem problem A=Ba+AbB=Aa+BbAssume B is final state Hence By ardens theorem A becomes A=Bab* .Hence B=Aa+Bb => Bab*a+BbTherefore B=B(ab*a+b) is the ... B=B(ab*a+b)) what to do?Here S=B,T=ab*a+b, Then what is R? 
User Avatar
155
views
1 answers
0 votes
DFA construction
Design a DFA to recognize all strings over {a,b} such that L={awa : w ϵ {a,b}* }.
User Avatar
193
views
1 answers
0 votes
DFA construction
Design a DFA (Deterministic Finite Automaton) that recognizes the language L defined follows: L= {w -> {a, b}* | every a in w is immediately followed by bb}
User Avatar
131
views
0 answers
0 votes
Regular Expresssion And NFA
In certain programming languages, comments appear between delimiters such as (* and ) . Let C be the language of all valid delimited comment strings. Such a string ... language C . (b) Present a regular expression that generates C.
User Avatar
164
views
0 answers
1 votes
How is "All strings {0,1} of length five or more in which the third symbol from the right end is different from the leftmost symbol" solved?
How is "All strings {0,1} of length five or more in which the third symbol from the right end is different from the leftmost symbol" solved? Answer Follow·1 Request  
User Avatar
149
views
1 answers
1 votes
#TOC regular expression
what will be the regular expression of this DFA using Arden's theorem
User Avatar
220
views
2 answers
0 votes
Regular language
Can anyone explain how we can write this regular language for the following diagram ?(in depth)
User Avatar
114
views
1 answers
0 votes
#unacademyDPP
User Avatar
131
views
0 answers
0 votes
Context Free language sample question
Give a context-free grammar for each of the following languages. Consider, Σ={0,1}.A. The language of strings that start with 1B. The language of strings of the form WWR C. The ... | j is a multiple of four or i = 3 + 2j where i, j ≥ 0}
User Avatar
118
views
0 answers
0 votes
Theory of Computation | design of Turing Machine
Is this the correct Turing machine for the language $0^n 1^n0^n$?assuming $ at the end and begining of the input tape
User Avatar
215
views
0 answers
0 votes
Regular Expresssion And NFA (THEORY OF AUTOMATA ASSIGNMENT # 1)
1. Write regular expressions and draw NFA for the following languages over the alphabet Σ = {a, b}: a. All strings that do not end with aa. b. All strings that ... e. All strings that does not ends with double letter.(can end with ab or ba)
User Avatar
298
views
1 answers
0 votes
Regular Expression
Write regular expression for the set of strings of 0's and 1's with at most one pair of consecutive 1's.
User Avatar
159
views
0 answers
0 votes
Hopcroft, Ullman Theorem 9.7 Reductions
There exists a language Ld = {M | M doesn't belong to L(M)}. Ld is the collection of Turing machines (programs) M such that M does not halt and ... -RE. But we know that ATM is Recursively Enumerable and undecidable. How is this possible?
User Avatar
250
views
0 answers
0 votes
CFL and regular language
Consider a regular language R and a context free language C. Let the PDA that recognizes C be called P=(QP,∑,Γ,δP,q0P,FP), and the DFA that reconginzes R be (QR,∑,δR,q0R,FR).
User Avatar
124
views
0 answers
0 votes
Pumping Lemma
Use the Pumping Lemma to show that the following languages over Σ={�,�}Σ={a,b} are not regular. In each case, carefully describe the string that will be pumped and explain why pumping it leads to a contradiction.{aaabnan∣n≥0}{ww∣w∈Σ∗}
User Avatar
217
views
0 answers
0 votes
DFA construction
Each of the following languages is the complement of a simpler language.In each part, construct a DFA for the simpler language, then use it to give the state diagram of a DFA for the ... not in $a^{*}\cup b^{*}$ } ( ∪ is the union )
User Avatar
To see more, click for the full list of questions or popular tags.