Arjun Suresh (talk | contribs) |
Starry Starr (talk | contribs) |
||
| (11 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}} }}=== | ||
| − | We have a DFA for L, let it be D and have n states. Now we can make a NFA for L' as follows: | + | We have a DFA for L, let it be D and have n states. Now we can make a NFA N for L' as follows: |
| − | + | Our start state will be the final state of D. For every transition on a symbol s from state x to y in D, we will have a transition from y to x. Further we add the following modification to the DFA: | |
| − | For every state of D, | + | For every state of N, we append the part of D till that state (all reachable transitions reaching that state). For example, for the start state in N(the final state in D), we'll append the whole D as it is. (This would mean every string accepted by D will be accepted by N also). For the below DFA, the appending is shown for state 1 |
<graphviz> | <graphviz> | ||
digraph finite_state_machine { | digraph finite_state_machine { | ||
rankdir=LR; | rankdir=LR; | ||
size="8,5" | size="8,5" | ||
| − | node [shape = doublecircle]; | + | node [shape = doublecircle]; 3; |
node [shape = circle]; | node [shape = circle]; | ||
| − | + | 0 -> 1 [ label = "a" ]; | |
| − | + | 1 -> 2 [ label = "a" ]; | |
| − | + | 2 -> 3 [ label = "a" ]; | |
| − | + | 3 -> 2 [ label = "a" ]; | |
| − | + | 0-> 2 [ label = "b" ]; | |
| − | + | 1 -> 0 [ label = "b" ]; | |
| − | + | 2 -> 2 [ label = "b" ]; | |
| − | + | 3 -> 2 [ label = "b" ]; | |
} | } | ||
</graphviz> | </graphviz> | ||
<graphviz> | <graphviz> | ||
| − | digraph | + | 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" ]; | |
| + | 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.
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 its from $L$, the first $TM$ will halt and we say it belongs to $L$. If its 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.
Is this statement true or false ?
We have a DFA for L, let it be D and have n states. Now we can make a NFA for L' as follows:
For every state of D,
GATECSE