Arjun Suresh (talk | contribs) |
Starry Starr (talk | contribs) |
||
| (22 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
| − | If L and L' are both recursively enumerable, then L is recursive. Why? | + | =='''1.''' If $L$ and $L'$ are both recursively enumerable, then $L$ is recursive. Why?== |
| − | === | + | ==={{Template:Author|Arjun Suresh|{{arjunweb}} }}=== |
| − | Given L is RE. So there is a TM, which accepts and halts for all words in L. | + | 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. | + | Now, if $L'$ is $RE$, then there is a $TM$, which accepts and halts for all words not in $L$. |
| − | So, if a word | + | 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 } == | ||
| + | Is this statement true or false ? | ||
| + | ==={{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 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 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> | ||
| + | digraph finite_state_machine { | ||
| + | rankdir=LR; | ||
| + | size="8,5" | ||
| + | node [shape = doublecircle]; 3; | ||
| + | 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> | ||
| + | digraph finite_state_machine2 { | ||
| + | rankdir=LR; | ||
| + | size="8,5" | ||
| + | node [shape = doublecircle]; 0,1,2,3; | ||
| + | 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> | ||
| + | --> | ||
| + | {{Template:FBD}} | ||
| − | |||
| − | + | [[Category: Theory of Computation]] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | [[Category: | ||
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.
If L and L' are both recursively enumerable, then L is recursive. Why?
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, from L or not from L,is given, give it to both those TMs. 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 L. Thus L becomes recursive.
GATECSE