Register
Webpage for Theory of Computation:

Recent questions tagged theory-of-computation

0 votes
0 answers
2222
Peter Linz questions
Should i leave out the proving questions in peter linz? I have a good idea about how to use theorems but struggle with proving questions. Since there is a constraint on time, I was thinking about leaving them.
Should i leave out the proving questions in peter linz?I have a good idea about how to use theorems but struggle with proving questions. Since there is a constraint on ti...
User Avatar
0 votes
1 answer
2223
Self Doubt
What is intersection of Context Free languages and Context sensitive languages what is the intersection of Context sensitive and recursive what is the intersection of Context free and recursive
What is intersection of Context Free languages and Context sensitive languageswhat is the intersection of Context sensitive and recursivewhat is the intersection of Conte...
User Avatar
1 votes
1 answer
2224
Theory of computation
What is intersection of Context Free languages and Context sensitive languages what is the intersection of Context sensitive and recursive what is the intersection of Context free and recursiv
What is intersection of Context Free languages and Context sensitive languageswhat is the intersection of Context sensitive and recursivewhat is the intersection of Conte...
User Avatar
0 votes
2 answers
2225
Theory of Computation
Please explain, what is the intersection of Context free language and Context Free language intersection of context free and recursive intersection of context sensitive and recursive
Please explain, what is the intersection of Context free language and Context Free languageintersection of context free and recursiveintersection of context sensitive and...
User Avatar
0 votes
0 answers
2226
PDA Doubt
Please can anyone explain the PDA for reverse of a string via a transition graph
Please can anyone explain the PDA for reverse of a string via a transition graph
User Avatar
0 votes
1 answer
2227
Grammer
A grammar will be meaningless of the (a) terminal set and non-terminal set are not disjoint (b) left hand side of a productions is a single terminal (c) left hand side of a production has no non-terminal (d) all of the above
A grammar will be meaningless of the(a) terminal set and non-terminal set are not disjoint(b) left hand side of a productions is a single terminal(c) left hand side of a ...
User Avatar
0 votes
1 answer
2228
#DFA #TOC #theoryofcomputation
How to construct an automata with even number of a's OR odd number of b's?
How to construct an automata with even number of a's OR odd number of b's?
User Avatar
4 votes
2 answers
2229
DCFL or Not
$\left \{ a^{m+n}b^{m+n}c^{n}|m,n\geq 1 \right \}$ $\left \{ a^{m+n}b^{m+n}c^{k} |m,n,k\geq 1\right \}$ $\left \{ a^{m+n}b^{m+k}c^{n+k} |m,n,k\geq 1\right \}$ Which one DCFL, CFL or CSL?
$\left \{ a^{m+n}b^{m+n}c^{n}|m,n\geq 1 \right \}$$\left \{ a^{m+n}b^{m+n}c^{k} |m,n,k\geq 1\right \}$$\left \{ a^{m+n}b^{m+k}c^{n+k} |m,n,k\geq 1\right \}$Which one DCFL...
User Avatar
0 votes
0 answers
2230
Moore machine
Can Moore machine be minimized without converting into mealy machine?Is minimization possible directly?
Can Moore machine be minimized without converting into mealy machine?Is minimization possible directly?
User Avatar
0 votes
1 answer
2232
Regular Expressions
What is the language produced by.... null*(denoted by phi) doubt from youtube video here
What is the language produced by....null*(denoted by phi) doubt from youtube video here
User Avatar
0 votes
0 answers
2240
Minimal dfa
How many states will be present in L={w/(n(a) + (2 n(b)mod 3)) lessthan 2} ? (I got 7 states is that correct)
How many states will be present in L={w/(n(a) + (2 n(b)mod 3)) lessthan 2} ? (I got 7 states is that correct)
User Avatar
1 votes
1 answer
2241
self made doubt
How to know that the language needs 1 stack or more than one stack in order to know about it is regular, context-free or not. example L1={$a^i b^j c^k│i<j<k$} L2={$a^i b^j c^k│i<j \ or \ k<j$} L3={$a^i b^j c^k│i<j \ and \ k<j$}
How to know that the language needs 1 stack or more than one stack in order to know about it is regular, context-free or not.exampleL1={$a^i b^j c^k│i<j<k$}L2={$a^i b^j...
User Avatar
0 votes
1 answer
2244
Peter Linz
Given L=a^nb ,n>=0.Construct a DFA for L^2
Given L=a^nb ,n>=0.Construct a DFA for L^2
User Avatar
1 votes
0 answers
2248
Introduction to Automata Theory- Properties of regular Languages - Q 4.2.10
Suppose that L is any language , not necessarily regular, whose alphabet is {0}; that is the strings of L consist of 0's only. Prove that L* is regular.
Suppose that L is any language , not necessarily regular, whose alphabet is {0}; that is the strings of L consist of 0's only. Prove that L* is regular.
User Avatar
0 votes
1 answer
2249
Test Series
As all recursive languages are recursively enumerable languages, they also should be Turing Recognizable together with Turing Decidable. This was my logic behind marking the 4th option which says all of the mentioned statements are true. Correct me if I am wrong
As all recursive languages are recursively enumerable languages, they also should be Turing Recognizable together with Turing Decidable. This was my logic behind marking ...
User Avatar
1 votes
2 answers
2250
Toc dfa
The minimum number of state in the DFA for the language $L = \{ w \mid (n_a(w)+2n_b(w))mod \hspace{0.1cm} 3<2 \} $ is
The minimum number of state in the DFA for the language $L = \{ w \mid (n_a(w)+2n_b(w))mod \hspace{0.1cm} 3<2 \} $ is
User Avatar
Page: