Register

Recent questions tagged recursive-and-recursively-enumerable-languages

2 votes
1 answer
153
R.E Language Question
Let A≤mB denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. then what can you say about this - True/False a) A is Recursive, but B is not R.E
Let A≤mB denotes that language A is mapping reducible (also known as many-to-one reducible) to language B.then what can you say about this - True/Falsea) A is Recursive...
User Avatar
1 votes
2 answers
159
language (TM)
what is the difference between recursive, RE and REL language?? confuse...
what is the difference between recursive, RE and REL language?? confuse...
User Avatar
4 votes
1 answer
160
decidability
C = { <G,x> | G is a CFG and x is substring of some y ∈ L(G) } . Then C is - a) undecidable b) Turing unrecognizable c) Recursive enumerable d) decidable
C = { <G,x | G is a CFG and x is substring of some y ∈ L(G) } . Then C is -a) undecidable b) Turing unrecognizable c) Recursive enumerable d) decidable
User Avatar
3 votes
2 answers
161
decidability
C = { <G,k> | G is a CFG and L(G) contains exactly k strings where k>=0 or k=∞ } . Then C will be- a) decidable b) Turing unrecognizable c) Recursive enumerable d) undecidable
C = { <G,k | G is a CFG and L(G) contains exactly k strings where k>=0 or k=∞ } . Then C will be-a) decidableb) Turing unrecognizablec) Recursive enumerabled) undecidab...
User Avatar
7 votes
3 answers
164
decidability
A = { <M> | M is a DFA that accepts some string with more 1s than 0s }. Then A is - a) undecidable b) recursive enumerable c) decidable d) none of the above
A = { <M | M is a DFA that accepts some string with more 1s than 0s }. Then A is - a) undecidable b) recursive enumerablec) decidabled) none of the above
User Avatar
3 votes
3 answers
165
decidability
A = { <R,S> | R and S are regular expressions and L(R) ⊆ L(S) }. Then what about A - a) Turing recognizable b) decidable c) undecidable d) Turing unrecognizable
A = { <R,S | R and S are regular expressions and L(R) ⊆ L(S) }. Then what about A -a) Turing recognizableb) decidablec) undecidabled) Turing unrecognizable
User Avatar
2 votes
1 answer
167
decidability
INFINITEPDA = {<M> | M is a PDA and L(M) is an infinite language } . Then - a) INFINITEPDA is undecidable. b) INFINITEPDA is decidable. c) INFINITEPDA is recursive enumerable. d) INFINITEPDA is Turing co-recognizable.
INFINITEPDA = {<M | M is a PDA and L(M) is an infinite language } . Then -a) INFINITEPDA is undecidable.b) INFINITEPDA is decidable.c) INFINITEPDA is recursive enumerable...
User Avatar
3 votes
1 answer
168
Turing machines and Recursively enumerable languages
If L1 and L2 are Turing-Recognizable then L1 ∪ L2 will be (a) Decidable (b) Turing-recognizable but may not be decidable (c) May not be Turing recognizable (d) None of above
If L1 and L2 are Turing-Recognizable then L1 ∪ L2 will be(a) Decidable(b) Turing-recognizable but may not be decidable(c) May not be Turing recognizable(d) None of abov...
User Avatar
0 votes
1 answer
169
Recursive and Recursively Enumerable
A language in NOT - RE is un-countably infinite. true or false? pls elaborate the answer you post.
A language in NOT - RE is un-countably infinite. true or false? pls elaborate the answer you post.
User Avatar
2 votes
2 answers
175
Self Doubt TOC Enumeration Method
If language L is countable infinite set then, L is Recursive as we can define enumeration method for the countable set. or It can Regular ??
If language L is countable infinite set then, L is Recursive as we can define enumeration method for the countable set.or It can Regular ??
User Avatar
0 votes
1 answer
176
Union of R.E and non R.E
What is the class of the language resulting from Union of R.E and non R.E ? (R.E => recursively enumerable)
What is the class of the language resulting from Union of R.E and non R.E ?(R.E = recursively enumerable)
User Avatar
5 votes
2 answers
180
ISRO2017-77
If $L$ and $P$ are two recursively enumerable languages then they are not closed under Kleene star $L^*$ of $L$ Intersection $L \cap P$ Union $L \cup P$ Set difference
If $L$ and $P$ are two recursively enumerable languages then they are not closed underKleene star $L^*$ of $L$Intersection $L \cap P$Union $L \cup P$Set difference
User Avatar
Page: