Register

Ace Test Series: Theory Of Computation - Decidablity

• edited by
400 views
0 votes
0 votes

• edited by
User Avatar

1 Answer

0 votes
0 votes
in L1) We are getting T yes and T no so...not recognizable

while in L2) we r not getting T yes subset of T no,……...so it’s not non-monotonic property of rice’ theorem hence it’s turing recognizable

so ,  ans is B
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
Kalpataru Bose asked Sep 4, 2018
594 views
Ace Test Series: Theory Of Computation - Decidablity
Can someone explain this problem?
Can someone explain this problem?
User Avatar
0 votes
0 votes
1 answer
4
Rahul Jain25 asked Feb 7, 2017
827 views
Decidablity+DCFL
I) L-R where L is DCFl and R is regular. Is L-R also DCFL decidable or not??? II)If L1 is reducible to L2 and L2 is non-RE then L1 is also Non-RE??? III) If L1 is reducible to L2 and L1 is non-RE then L2 is also non-RE??
I) L-R where L is DCFl and R is regular. Is L-R also DCFL decidable or not???II)If L1 is reducible to L2 and L2 is non-RE then L1 is also Non-RE??? III) If L1 is reducibl...
User Avatar
Link Copied!