The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
42 views

In this lecture by Shai Simonson : https://youtu.be/77OG6ziPMu4 
At 33:04 he mentions that "A = CFL that does not accept $\sum^*$ " is Undecidable.
Also, we already know that "A' = CFL that accept $\sum ^*$ " is Undecidable as well.
so if A and A' both are Recursively Enumerable sets, then wouldn't that make A a recursive set ?

 

closed with the note: Understood
asked in Theory of Computation by Active (1.8k points)
closed by | 42 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,162 questions
43,620 answers
124,005 comments
42,880 users