Register

Turing Recognizable Languages

• retagged by
623 views

1 Answer

0 0 votes
I think none of the option is correct.

A. RE are not closed under Complement operation. So it is not evern Turing Recognizable

B and C and E options. Since RE' is not even Turing Recognizable and we don't know anything about those languages. So we cannot comment on any operation on those Languages. Threrefore all are False.

D. LUR is Recursive Enumerable but not Recursive. To find the Union Move L to upper Level in Chomsky Hierarchy to RE languages. Since RE are closed under Union. Therefore LUR is RE and not Recursive. So this statement is also False.
Voting & Accepting an answer helps improve the community
← Previous · Operating system con...Next → · doubt
← Previous in category · finite autometaNext in category → · Decidability
Position:
Show:

Related questions

1 1 vote
2 2 answers
1.2k
1.2k views
asterixbachman asked Jan 25, 2017
1,214 views
Turing Recognizable and Turing Decidable
CaptionCan someone give a clear explanation to this answer?
0 0 votes
1 answers 1 answer
1.2k
1.2k views
Akriti sood asked Dec 18, 2016
1,167 views
Let A, B, C be recognizable languages over an alphabet Σ,
Let A, B, C be recognizable languages over an alphabet Σ, such that A∪B∪C=Σ and A∩B=∅,B∩C=∅,A∩C=∅ then Only A is Turing decidable Only B is Turing decidable Both A and...
3 3 votes
1 1 answer
1.9k
1.9k views
Utkarsh Anand asked Jul 31, 2017
1,909 views
Turing Decidable Languages
Are Turing decidable languages are closed under Complementation, Reversal, Homomorphism, Inverse Homomorphism and Substitution?
0 0 votes
1 1 answer
18
18 views
GO Classes asked 1 day ago
18 views
GO Classes DPP | GATE CS | Theory of Computation | Recognizable vs Decidable Closure
Select all the true statements.Recognizable languages are closed under complement. Decidable languages are closed under complement. Recognizable languages are closed unde...