View source for Automata Doubts ← Automata Doubts

=='''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$. 
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.
<!--
=='''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: Automata Theory]]