339 views
1 votes
1 votes

Please someone explain this...how the language is phi  and explain the problem..????

Thanks in advance

1 Answer

0 votes
0 votes
It is given to us that the Turing Machine halts for language L. That means that the language L is accepted by the turing machine. Any Language which is accepted by the turing machine is:decidable and recursively ennumerable i.e. Type 0 grammar.

But it is also given to us that this language is equal to L' which is undecidable language. Now a decidable language can be equal to an undecidable language in only one case when it is phi i.e. it contains nothing.So it is decidable as it is accepted by the turing machine and recursive. It is a type 0 grammar so it is not undecidable.

Related questions

1 votes
1 votes
0 answers
1
prashant dubey asked Apr 12, 2019
4,608 views
The no. Of state in minimal dfa for string starting with abb and ending with b over the alphabet a,b .Please construct dfa
0 votes
0 votes
1 answer
2
Kashyap Avinash asked Dec 9, 2016
617 views
Confusion in last printf Statement..Can anyone explain what printf Statement want to say...
0 votes
0 votes
1 answer
3
sardendu asked Sep 29, 2018
472 views
For question like :-Find minimum number of variable required to solve the expression in three address code. (not SSA)Do we need to consider the given variable also?Exampl...
0 votes
0 votes
0 answers
4
AmitPatil asked Jan 26, 2017
826 views
L1 = {an bm | n ≤ m ≤ 2n}L2 = {an bm│m≠n & m≠2n}Which of the following is true?A. Only L1 is CFGB. Only L2 is CFGC. Both are CFGD. None of them is CFG