Register
Webpage for Theory of Computation:

Recent questions tagged theory-of-computation

0 votes
0 answers
2161
Regular language
$L=\left \{ a^{n}:\text{n is the product of two prime number} \right \}$L$ is regular or non regular?
$L=\left \{ a^{n}:\text{n is the product of two prime number} \right \}$$L$ is regular or non regular?
User Avatar
0 votes
0 answers
2162
Regular language
Whether the language $L=\left \{ a^{n}b^{l}a^{k}:n+l+k> 5 \right \}$ is regular or not???
Whether the language $L=\left \{ a^{n}b^{l}a^{k}:n+l+k 5 \right \}$ is regular or not???
User Avatar
2 votes
3 answers
2163
TOC self doubt
$\text{Is the language L is DCFL or CFL ?}$
$\text{Is the language L is DCFL or CFL ?}$
User Avatar
1 votes
1 answer
2166
Made Easy Theory Book
Can somebody please explain the meaning of the following statement : An automation is a cognitive device and a grammar is a generative device.
Can somebody please explain the meaning of the following statement : An automation is a cognitive device and a grammar is a generative device.
User Avatar
0 votes
2 answers
2167
Regular expression
Is a*b* + b*a* = ( a + b)* ______
Is a*b* + b*a* = ( a + b)* ______
User Avatar
0 votes
3 answers
2168
Theory of Computation - Finite Automata
Can someone please help me understand these two points about minimum DFA and Minimum NFA, thank you
Can someone please help me understand these two points about minimum DFA and Minimum NFA, thank you
User Avatar
0 votes
1 answer
2170
Gate overflow old question
Referring to the question https://gateoverflow.in/227957/self-doubt If the TM accepts exactly 100 strings can we not design a FA for it which would make it a regular language?
Referring to the question https://gateoverflow.in/227957/self-doubtIf the TM accepts exactly 100 strings can we not design a FA for it which would make it a regular langu...
User Avatar
1 votes
0 answers
2174
DPDA acceptance by empty stack
Is this approach of acceptance by empty stack correct ? I am confused because i have read that acceptance by empty stack may not be able to accept all regular languages.
Is this approach of acceptance by empty stack correct ?I am confused because i have read that acceptance by empty stack may not be able to accept all regular languages.
User Avatar
0 votes
1 answer
2175
TOC AUTOMATA
User Avatar
0 votes
0 answers
2176
TOC AUTOMATA
User Avatar
1 votes
0 answers
2177
TOC AUTOMATA
User Avatar
0 votes
1 answer
2178
#selfdoubt
Dpda acceptance by empty stack is equivalent in power as dpda acceptance by final state? explain
Dpda acceptance by empty stack is equivalent in power as dpda acceptance by final state?explain
User Avatar
1 votes
2 answers
2179
self doubt
(11+1111)* minimized number of states ???
(11+1111)* minimized number of states ???
User Avatar
0 votes
1 answer
2180
theory of computation
check whether given language is regular or not 1) (an) n where n ≥1 2) ( am ) n where n ≥ 1 3) w= { (( a 2 ) n) * (( an )2 )* } where n ≥ 1
check whether given language is regular or not 1) (an) n where n ≥12) ( am ) n where n ≥ 13) w= { (( a 2 ) n) * (( an )2 )* } where n ≥ 1
User Avatar
2 votes
1 answer
2182
self doubt
Given a TM, M accepts 100 strings. Is it decidable, semi decidable or fully undecidable??
Given a TM, M accepts 100 strings. Is it decidable, semi decidable or fully undecidable??
User Avatar
0 votes
1 answer
2183
minimum dfa
minimized dfa for strings starts with ab and ends with aba over Σ={a,b}
minimized dfa for strings starts with ab and ends with aba over Σ={a,b}
User Avatar
1 votes
0 answers
2184
self doubt
is it necessary for the gate exam that minimisation of dfa can be solved by partitiong method ?? will it be safe to escape partitining method and problem can be solved by table filling method??
is it necessary for the gate exam that minimisation of dfa can be solved by partitiong method ?? will it be safe to escape partitining method and problem can be solved by...
User Avatar
1 votes
1 answer
2186
Self Doubt
Can pumping lemma be used to prove that a given grammar is not regular .
Can pumping lemma be used to prove that a given grammar is not regular .
User Avatar
0 votes
1 answer
2187
GATE - TOC Regular Languages & FA
Let L(r1)=(b*ab*ab*ab*)* & L(r2)=(b*ab*ab*)*. What is L(r1) Intersection L(r2)? a) (b*ab*ab*ab*)* b) (b*ab*ab*)* c) (b*ab*ab*)^6 d) (b*ab*ab*ab*ab*ab*ab*)* Please do explain also.
Let L(r1)=(b*ab*ab*ab*)* & L(r2)=(b*ab*ab*)*. What is L(r1) Intersection L(r2)?a) (b*ab*ab*ab*)*b) (b*ab*ab*)*c) (b*ab*ab*)^6d) (b*ab*ab*ab*ab*ab*ab*)*Please do explain a...
User Avatar
0 votes
0 answers
2188
Countable uncountable functions
How the set of all non-decreasing functions from N to N are countable? How the set of all finite partitions of N are uncountable?
How the set of all non-decreasing functions from N to N are countable?How the set of all finite partitions of N are uncountable?
User Avatar
0 votes
0 answers
2189
Existence of a 2 state NPDA
How can we convert an arbitrary NPDA into an NPDA with at most 2 states? I know the existence of a 3 state PDA, but how can it be done by using just 2 states?
How can we convert an arbitrary NPDA into an NPDA with at most 2 states? I know the existence of a 3 state PDA, but how can it be done by using just 2 states?
User Avatar
Page: