Arjun Suresh (talk | contribs) |
Starry Starr (talk | contribs) |
||
| (4 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
| − | =='''1.''' If | + | =='''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 | + | Given $L$ is $RE$. So there is a $TM$, which accepts and halts for all words in $L$. |
| − | Now, if | + | 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 | + | 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 } == | ||
Is this statement true or false ? | Is this statement true or false ? | ||
| Line 30: | Line 30: | ||
3 -> 2 [ label = "b" ]; | 3 -> 2 [ label = "b" ]; | ||
} | } | ||
| − | + | </graphviz> | |
| + | <graphviz> | ||
digraph finite_state_machine2 { | digraph finite_state_machine2 { | ||
rankdir=LR; | rankdir=LR; | ||
| Line 49: | Line 50: | ||
} | } | ||
</graphviz> | </graphviz> | ||
| + | --> | ||
{{Template:FBD}} | {{Template:FBD}} | ||
| − | [[Category: | + | [[Category: Theory of Computation]] |
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.
GATECSE