Register
Webpage for Theory of Computation:

Recent questions tagged theory-of-computation

–1 votes
0 answers
2821
How i) is correct??
User Avatar
3 votes
1 answer
2822
self doubt
DOES TURING MACHINE ACCEPT EPSILON IS THIS PROBLEM DECIDABLE ?? PLEASE SOME ONE CLARIFY THIS
DOES TURING MACHINE ACCEPT EPSILON IS THIS PROBLEM DECIDABLE ??PLEASE SOME ONE CLARIFY THIS
User Avatar
3 votes
1 answer
2823
DPDA: One Liners
1) Can a Deterministic PDA has two epsilon transition each reading different Stack symbol to perform a transition? 2) Can a transition be performed without reading Stack symbol at all. Like $ a, λ/ λ$?
1) Can a Deterministic PDA has two epsilon transition each reading different Stack symbol to perform a transition?2) Can a transition be performed without reading Stack s...
User Avatar
3 votes
2 answers
2824
GA TesT
Designer mealy machine to decrement a binary number by 1
Designer mealy machine to decrement a binary number by 1
User Avatar
3 votes
1 answer
2825
Self doubt
Design a dfa in which accepts all the strings in which every prefix the difference of 0 and 1 is not more than 2?
Design a dfa in which accepts all the strings in which every prefix the difference of 0 and 1 is not more than 2?
User Avatar
1 votes
0 answers
2829
Doubt regarding Turing Machine
I have read that T.M does not accept ε , but then in questions I have read T.M taking input ε ? Well, if T.M can't accept ε then why we are giving T.M the input ε ? Thank you!
I have read that T.M does not accept ε , but then in questions I have read T.M taking input ε ?Well, if T.M can't accept ε then why we are giving T.M the input ε ?Th...
User Avatar
3 votes
1 answer
2830
Closure Property
L3 and L4 are CFL,L5 is regular. L1=(L3 Union L4)c L2=(L3R Union L4) Intersection L5 L1 and L2 are a.Both CFL b.CSL and CFL c.Recursive and CFL d.None of these
L3 and L4 are CFL,L5 is regular.L1=(L3 Union L4)cL2=(L3R Union L4) Intersection L5L1 and L2 area.Both CFLb.CSL and CFLc.Recursive and CFLd.None of these
User Avatar
3 votes
0 answers
2833
Closure Properties
Which of the following are closed/ not closed under infinite Union? a.DCFL b.CFL c.CSL d.Recursive Languages e.Recursively enumerable languages
Which of the following are closed/ not closed under infinite Union?a.DCFLb.CFLc.CSLd.Recursive Languagese.Recursively enumerable languages
User Avatar
0 votes
1 answer
2836
Converting NFA to DFA
Is it possible to convert a NFA having 'n' states to some DFA having less than 'n' states?
Is it possible to convert a NFA having 'n' states to some DFA having less than 'n' states?
User Avatar
0 votes
0 answers
2837
self doubt
is implementation of LBA for CSL not possible ?????? is Context sensitive grammer used for type checking ??
is implementation of LBA for CSL not possible ??????is Context sensitive grammer used for type checking ??
User Avatar
5 votes
3 answers
2842
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
2843
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
2845
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
2846
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
2847
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
2850
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
Page: