Difference between revisions of "Automata Doubts"

(→‎{{Template:Author|Arjun Suresh|{{arjunweb}} }})
Line 1: Line 1:
−
=='''1.''' If <math>L</math> and <math>L'</math> are both recursively enumerable, then <math>L</math> is recursive. Why?==
+
=='''1.''' If $L$ and $L'$ are both recursively enumerable, then $L$ is recursive. Why?==
  
 
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
 
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
  
  
−
Given <math>L</math> is $RE$. So there is a $TM$, which accepts and halts for all words in <math>L</math>.  
+
Given $L$ is $RE$. So there is a $TM$, which accepts and halts for all words in $L$.  
−
Now, if <math>L'</math> is $RE$, then there is a $TM$, which accepts and halts for all words not in <math>L</math>.
+
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 <math>L</math> or not from <math>L</math>), 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 <math>L</math>. Thus, <math>L</math> becomes recursive.
+
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.
 
<!--
 
<!--
 
=='''2.''' CYCLE(L) ={xy | yx is in L,L is regular } ==
 
=='''2.''' CYCLE(L) ={xy | yx is in L,L is regular } ==

Revision as of 14:00, 2 September 2014

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
Retrieved from "https://gatecse.in/w/index.php?title=Automata_Doubts&oldid=4232"

1. If <math>L</math> and <math>L'</math> are both recursively enumerable, then <math>L</math> is recursive. Why?[edit]

Solution by Arjun Suresh[edit]

Given <math>L</math> is $RE$. So there is a $TM$, which accepts and halts for all words in <math>L</math>. Now, if <math>L'</math> is $RE$, then there is a $TM$, which accepts and halts for all words not in <math>L</math>. So, if a word is given (either from <math>L</math> or not from <math>L</math>), 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 <math>L</math>. Thus, <math>L</math> becomes recursive.



blog comments powered by Disqus