Line 55: Line 55:
  
  
[[Category: Automata Theory]]
+
[[Category: Theory of Computation]]

Latest revision as of 00:30, 7 May 2015

1. If $L$ and $L'$ are both recursively enumerable, then $L$ is recursive. Why?

Solution by Arjun Suresh

Given $L$ is $RE$. So there is a $TM$, which accepts and halts for all words in $L$. Now, if $L'$ is $RE$, then there is a $TM$, which accepts and halts for all words not in $L$. So, if a word is given (either from $L$ or not from $L$), give it to both those $TM$s. If it is from $L$, the first $TM$ will halt and we say it belongs to $L$. If it is not from $L$, the second one will halt and we say it doesn't belong to $L$. Thus, $L$ becomes recursive.



blog comments powered by Disqus

1. If $L$ and $L'$ are both recursively enumerable, then $L$ is recursive. Why?[edit]

Solution by Arjun Suresh[edit]

Given $L$ is $RE$. So there is a $TM$, which accepts and halts for all words in $L$. Now, if $L'$ is $RE$, then there is a $TM$, which accepts and halts for all words not in $L$. So, if a word is given (either from $L$ or not from $L$), give it to both those $TM$s. If it is from $L$, the first $TM$ will halt and we say it belongs to $L$. If it is not from $L$, the second one will halt and we say it doesn't belong to $L$. Thus, $L$ becomes recursive.



blog comments powered by Disqus