(14 intermediate revisions by one other user not shown)
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 $L$ and $L'$ are both recursively enumerable, then $L$ is recursive. Why?==
  
 
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
 
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
  
  
Given <math>L</math> is $RE$. So there is a $TM$, which accepts and halts for all words in <math>L</math>.  
+
Given $L$ is $RE$. So there is a $TM$, which accepts and halts for all words in $L$.  
Now, if <math>L'</math> is $RE$, then there is a $TM$, which accepts and halts for all words not in <math>L</math>.
+
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 <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 $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]; LR_4;
+
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];
 
node [shape = circle];
LR_0 -> LR_1 [ label = "a" ];
+
0 -> 1 [ label = "a" ];
LR_1 -> LR_2 [ label = "a" ];
+
      1 -> 0 [ label = "b" ];
LR_2 -> LR_3 [ label = "a" ];
+
        1 -> 0 [ label = "a" ];
LR_3 -> LR_4 [ label = "a" ];
+
2 -> 1 [ label = "a" ];
LR_2 -> LR_5 [ label = "b" ];
+
3 -> 2 [ label = "a" ];
LR_0-> LR_2 [ label = "b" ];
+
2 -> 3 [ label = "a" ];
LR_1 -> LR_0 [ label = "b" ];
+
2-> 0 [ label = "b" ];
LR_2 -> LR_2 [ label = "b" ];
+
0 -> 1 [ label = "b" ];
LR_3 -> LR_2 [ label = "b" ];
+
2 -> 2 [ label = "b" ];
LR_4 -> LR_4 [ label = "b" ];
+
2 -> 3 [ label = "b" ];
LR_4 -> LR_0 [ label = "a" ];
 
 
 
 
}
 
}
 
</graphviz>
 
</graphviz>
 +
-->
 
{{Template:FBD}}
 
{{Template:FBD}}
  
  
  
[[Category: Automata Theory]]
+
[[Category: Theory of Computation]]

Latest revision as of 00:30, 7 May 2015

1. If $L$ and $L'$ are both recursively enumerable, then $L$ is recursive. Why?

Solution by Arjun Suresh

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.



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?[edit]

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.

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

Is this statement true or false ?

Solution by Arjun Suresh[edit]

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