Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| 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; | ||
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 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
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 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
GATECSE