Line 1: Line 1:
'''1.''' If <math>L</math> and <math>L'</math> are both recursively enumerable, then <math>L</math> is recursive. Why?
+
=='''1.''' If <math>L</math> and <math>L'</math> are both recursively enumerable, then <math>L</math> is recursive. Why?==
  
 
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
 
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
Line 8: Line 8:
 
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.
 
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.
  
 +
=='''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 for L' as follows:
  
 +
For every state of D,
 +
<graphviz>
 +
digraph finite_state_machine {
 +
rankdir=LR;
 +
size="8,5"
 +
node [shape = doublecircle]; LR_0 LR_3 LR_4 LR_8;
 +
node [shape = circle];
 +
LR_0 -> LR_2 [ label = "SS(B)" ];
 +
LR_0 -> LR_1 [ label = "SS(S)" ];
 +
LR_1 -> LR_3 [ label = "S($end)" ];
 +
LR_2 -> LR_6 [ label = "SS(b)" ];
 +
LR_2 -> LR_5 [ label = "SS(a)" ];
 +
LR_2 -> LR_4 [ label = "S(A)" ];
 +
LR_5 -> LR_7 [ label = "S(b)" ];
 +
LR_5 -> LR_5 [ label = "S(a)" ];
 +
LR_6 -> LR_6 [ label = "S(b)" ];
 +
LR_6 -> LR_5 [ label = "S(a)" ];
 +
LR_7 -> LR_8 [ label = "S(b)" ];
 +
LR_7 -> LR_5 [ label = "S(a)" ];
 +
LR_8 -> LR_6 [ label = "S(b)" ];
 +
LR_8 -> LR_5 [ label = "S(a)" ];
 +
}
 +
</graphviz>
 
{{Template:FBD}}
 
{{Template:FBD}}
  

Revision as of 14:53, 24 May 2014

1. If <math>L</math> and <math>L'</math> are both recursively enumerable, then <math>L</math> is recursive. Why?

Solution by Arjun Suresh

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.

2. CYCLE(L) ={xy | yx is in L ,L is regular }

Is this statement true or false ?

Solution by Arjun Suresh

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,

This is a graph with borders and nodes. Maybe there is an Imagemap used so the nodes may be linking to some Pages.



blog comments powered by Disqus

1. If <math>L</math> and <math>L'</math> are both recursively enumerable, then <math>L</math> is recursive. Why?

Solution by Arjun Suresh[edit]

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.





blog comments powered by Disqus