Register

$L= { <G>$ is a CFG & not ambiguous $}$ RE or not?

372 views
3 votes
3 votes

$L= { <G>$ is a CFG & not ambiguous $}$ RE or not? We can have 2 TMs where $T_{yes}\subset T_{no}$ just by adding additional ambiguous productions to an existing non ambigous CFG. So it seems to me it is not RE, but given answer is RE. Where I am wrong? 

User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

11 votes
11 votes
2 answers
2
sourav. asked Sep 9, 2017
4,534 views
$\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$
My Question $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$I have to check that it is Turing Recogniza...
User Avatar
2 votes
2 votes
0 answers
3
bts1jimin asked Jan 8, 2019
611 views
RE or non RE
CONSIDER THE FLLOWING LANGUAGE L={<M>| M is a TM and L(M)=empty} Which of the following is true? a- Decidable REC B- Undecidable and RE c-Undecidable and non RE d- Decidable but RE
CONSIDER THE FLLOWING LANGUAGE L={<M>| M is a TM and L(M)=empty}Which of the following is true?a- Decidable RECB- Undecidable and REc-Undecidable and non REd- Decidable ...
User Avatar
2 votes
2 votes
2 answers
4
Sandeep Singh asked Dec 30, 2015
462 views
Is $ a terminal or not ?
Follow(S) comes as {(, ). $ } So, do we count $ ... is also marker to identify that parsing of string has been successfully completed.
Follow(S) comes as {(, ). $ }So, do we count $ as terminal or not.Could anyone please tell me, $ should be considered as terminal or not ? Although I think, I should not...
User Avatar
Link Copied!