New answers tagged


The property of being EVEN-CFL of c.e. languages is not trivial, by Rice's theorem this is not decidable.


Enumerate the c.e. set, keep only entries that appear in increasing lexocographic order. As the c.e. set is infinite, there will be new elements larger than the last kept one (thus the subset is infinite). To decide the subset, enumerate until hitting the element or a larger one.


To address your first question, this DFA will do the trick: The starting state is marked with an 'S' and it is also the only accepting state. Any string that has a prefix with 3 or more a's than it does b's will go out the right side and end up trapped in the trash state, and similarly, with b's to the left. Furthermore, it will only end up in the center if ...


No, it is not necessarily recursively enumerable. There are languages that are recursively enumerable but not recursive. Thus, their complement is not recursively enumerable. From that, you should be able to prove that the answer to the question in the final sentence of your post is no (I'll let you fill in the details from there).


Here is one possible approach. Since $L$ is c.e., there is some enumerator that outputs a list of the word in $L$: $w_1,w_2,\ldots$. Let $D$ consist of all words $w_i$ which are longer than all words appearing before them. I claim that $D$ is infinite. If not, let $w_m$ be the last word in $D$. Then all other words have length at most $|w_m|$. However, this ...


Your argument "goes backwards." Note that your definition of $R$ depends on $D$ (step $2$). This means you can't conclude that no machine decides $A_R$, merely that $D$ specifically doesn't. Basically, what you've written looks like this: CLAIM: there is some $x$ such that no $y$ does [task involving $x$]. PROOF: picking some $y$, we build an $x$ such ...


It's your second bullet point - something odd in the recursive relationship. The argument is trying to show a contradiction by exhibiting a finite language that is undecidable. In other words, the argument needs to show that there exists a finite language $L$ such that for every decider $D$, there is some input $w$ such that $D$ incorrectly decides whether ...

Top 50 recent answers are included