Register

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

474 views
3 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? 

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← Previous · Gate 2002Next → · SLR(1) or Not
← Previous in category · How i) is correct??Next in category → · Random
Position:
Show:

Related questions

7 7 votes
2 answers 2 answers
4.9k
4.9k views
Manu Thakur asked Nov 15, 2014
4,895 views
Given Language is REC or Non RE
Which of the following is true for the given language?$L=$ {<TM | TM halts on every input}<TM is encoding of the Turing machine(A) $L$ is Recursive and $\overline{L}$ is ...
12 12 votes
2 2 answers
6.9k
6.9k views
sourav. asked Sep 9, 2017
6,863 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...
2 2 votes
0 0 answers
1.6k
1.6k views
bts1jimin asked Jan 8, 2019
1,602 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 RECB- Undecidable and REc-Undecidable and non REd- Decidable ...
2 2 votes
2 2 answers
913
913 views
Sandeep Singh asked Dec 30, 2015
913 views
Is $ a terminal or not ?
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...