Register
Webpage for Theory of Computation:

Recent questions tagged theory-of-computation

5 votes
3 answers
2851
TOC: Number of states in minimum DFA
I think, there will be 4 states in minimum DFA, following states will be merged in the resulted DFA {q0&q3}, {q4&q5}, {q1&q6}, {q2&q7}
I think, there will be 4 states in minimum DFA, following states will be merged in the resulted DFA{q0&q3}, {q4&q5}, {q1&q6}, {q2&q7}
User Avatar
4 votes
1 answer
2852
Computation Theory - Show that the family of regular languages is closed under tail(L) = {y : xy ∈ L for some x ∈ Σ ∗ }
The tail of a language is the set of all suffixes of its strings, that is tail(L) = {y : xy ∈ L for some x ∈ Σ ∗ }.How do I show that the family of regular languag...
User Avatar
0 votes
1 answer
2854
Removing E productions
We need to remover E productions from the grammar Vertices-{A,B,C,S} Terminals={a,b,c,E} S->ABAC A->aA/E B->bB/E C->c
We need to remover E productions from the grammarVertices-{A,B,C,S} Terminals={a,b,c,E}S->ABACA->aA/EB->bB/EC->c
User Avatar
2 votes
2 answers
2855
MadeEasy Workbook: Theory of Computation - Regular Expressions
find regular expression over {a,b} corresponding to "set of strings containing at most 2a's." a) b*+ b*ab* + b*ab*ab* b) b*(a+ε)b*(a+ε) c) none
find regular expression over {a,b} corresponding to "set of strings containing at most 2a's."a) b*+ b*ab* + b*ab*ab*b) b*(a+ε)b*(a+ε)c) none
User Avatar
2 votes
2 answers
2856
MadeEasy Workbook: Theory of Computation - Regular Expressions
find the length of string of minimum length in {0,1}* not in the language corresponding to the given RE (0*+1*)* a) 0 b) 1 c) more than 1 d) can't be determined
find the length of string of minimum length in {0,1}* not in the language corresponding to the given RE(0*+1*)*a) 0b) 1c) more than 1d) can't be determined
User Avatar
0 votes
1 answer
2859
self doubt
what is the relation between P AND NP PROBLEMS and decidability?? .. please suggest me a resource to learn in short time or explain in brief
what is the relation between P AND NP PROBLEMS and decidability?? .. please suggest me a resource to learn in short time or explain in brief
User Avatar
0 votes
0 answers
2860
Regular language
{XWWrY} is regular or not? XYW € (0,1)+
{XWWrY} is regular or not?XYW € (0,1)+
User Avatar
2 votes
1 answer
2861
Theory of Computation - Show that an algorithm exists for determining if L contains any strings of even length.
Let L be any regular language on Σ = {a, b}. Show that an algorithm exists for determining if L contains any strings of even length.
User Avatar
1 votes
1 answer
2864
Theory-of-computation DFA
Design a minimal DFA accepting L={w ; atleast one 'a' in w is not immediately followed by 'b'}
Design a minimal DFA accepting L={w ; atleast one 'a' in w is not immediately followed by 'b'}
User Avatar
1 votes
1 answer
2866
Reducibility
Why this is incorrect? For any two languages A and B, if A ⊆ B, then A is reducible to B.
Why this is incorrect? For any two languages A and B, if A ⊆ B, then A is reducible to B.
User Avatar
3 votes
1 answer
2868
CFL Language
For A, B ⊆ Σ*, define A/B = {x ∈ Σ* | ∃y ∈ B, xy ∈ A} If L is a CFL and R is regular, then L/R is (A) Regular (B) CFL but not regular (C) Recursive but not CFL (D) None of the above
For A, B ⊆ Σ*, defineA/B = {x ∈ Σ* | ∃y ∈ B, xy ∈ A}If L is a CFL and R is regular, then L/R is(A) Regular(B) CFL but not regular(C) Recursive but not CFL(D)...
User Avatar
1 votes
2 answers
2869
Regular expressions
Are regular expressions (a+b)* and (a*b*)* over alphabet set {a,b} same? If not, which strings are acceptable in one and not in other...
Are regular expressions (a+b)* and (a*b*)* over alphabet set {a,b} same?If not, which strings are acceptable in one and not in other...
User Avatar
0 votes
0 answers
2870
TOC: Complement of the given language
Is the following language CFL? L = complement of {$a^ib^jc^k$ | i!=j and j!=k}
Is the following language CFL?L = complement of {$a^ib^jc^k$ | i!=j and j!=k}
User Avatar
1 votes
1 answer
2871
MadeEasy Workbook: Theory of Computation - Finite Automata
If an input string w has n symbols and can be recognized by a mealy machine M1 and equivalent Moore machine M2 then number of output symbols by M1 and M2 are respectively?
If an input string w has n symbols and can be recognized by a mealy machine M1 and equivalent Moore machine M2 then number of output symbols by M1 and M2 are respectively...
User Avatar
2 votes
1 answer
2872
test series
consider a tùring mchine which accepts the empty language i.e TM = { (M) | M accepts empty language} the complement of the language that is generated by Turing machine is?
consider a tùring mchine which accepts the empty language i.e TM = { (M) | M accepts empty language} the complement of the language that is generated by Turing machine i...
User Avatar
2 votes
1 answer
2873
theory-of-computation
User Avatar
0 votes
4 answers
2878
minimal DFA
construct the minimal DFA for the language L={ 3rd symbol from the R.H.S is 'a'} and ∈={a.b}.
construct the minimal DFA for the language L={ 3rd symbol from the R.H.S is 'a'} and ∈={a.b}.
User Avatar
5 votes
1 answer
2879
UTM REDUCTION
please give proper reasoning.
please give proper reasoning.
User Avatar
6 votes
1 answer
2880
DCFL,AMBIGUITY
User Avatar
Page: