Arjun Suresh (talk | contribs) (→{{Template:Author|Arjun Suresh|{{arjunweb}} }}) |
Arjun Suresh (talk | contribs) |
||
| Line 19: | Line 19: | ||
rankdir=LR; | rankdir=LR; | ||
size="8,5" | size="8,5" | ||
| − | node [shape = doublecircle]; | + | node [shape = doublecircle]; LR_3; |
node [shape = circle]; | node [shape = circle]; | ||
LR_0 -> LR_1 [ label = "a" ]; | LR_0 -> LR_1 [ label = "a" ]; | ||
LR_1 -> LR_2 [ label = "a" ]; | LR_1 -> LR_2 [ label = "a" ]; | ||
LR_2 -> LR_3 [ label = "a" ]; | LR_2 -> LR_3 [ label = "a" ]; | ||
| − | LR_3 -> | + | LR_3 -> LR_2 [ label = "a" ]; |
LR_0-> LR_2 [ label = "b" ]; | LR_0-> LR_2 [ label = "b" ]; | ||
LR_1 -> LR_0 [ label = "b" ]; | LR_1 -> LR_0 [ label = "b" ]; | ||
LR_2 -> LR_2 [ label = "b" ]; | LR_2 -> LR_2 [ label = "b" ]; | ||
LR_3 -> LR_2 [ label = "b" ]; | LR_3 -> LR_2 [ label = "b" ]; | ||
| − | + | } | |
| − | + | digraph finite_state_machine { | |
| + | rankdir=LR; | ||
| + | size="8,5" | ||
| + | node [shape = doublecircle]; LR_0; | ||
| + | node [shape = circle]; | ||
| + | LR_1 -> LR_0 [ label = "a" ]; | ||
} | } | ||
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,
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