Arjun Suresh (talk | contribs) |
Starry Starr (talk | contribs) |
||
| (7 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 ? | ||
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}=== | ==={{Template:Author|Arjun Suresh|{{arjunweb}} }}=== | ||
| Line 31: | Line 31: | ||
} | } | ||
</graphviz> | </graphviz> | ||
| − | |||
<graphviz> | <graphviz> | ||
digraph finite_state_machine2 { | digraph finite_state_machine2 { | ||
rankdir=LR; | rankdir=LR; | ||
size="8,5" | size="8,5" | ||
| − | node [shape = doublecircle]; | + | node [shape = doublecircle]; 0,1,2,3; |
node [shape = circle]; | node [shape = circle]; | ||
0 -> 1 [ label = "a" ]; | 0 -> 1 [ label = "a" ]; | ||
1 -> 0 [ label = "b" ]; | 1 -> 0 [ label = "b" ]; | ||
| + | 1 -> 0 [ label = "a" ]; | ||
| + | 2 -> 1 [ label = "a" ]; | ||
| + | 3 -> 2 [ label = "a" ]; | ||
| + | 2 -> 3 [ label = "a" ]; | ||
| + | 2-> 0 [ label = "b" ]; | ||
| + | 0 -> 1 [ label = "b" ]; | ||
| + | 2 -> 2 [ label = "b" ]; | ||
| + | 2 -> 3 [ label = "b" ]; | ||
} | } | ||
</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