Automata Doubts - Revision history

Starry Starr at 00:30, 7 May 2015

2015-05-07T00:30:28Z

Arjun Suresh at 14:00, 2 September 2014

2014-09-02T14:00:39Z

Arjun Suresh: /* {{Template:Author|Arjun Suresh|{{arjunweb}} }} */

2014-06-14T12:51:44Z

‎{{Template:Author|Arjun Suresh|{{arjunweb}} }}

Arjun Suresh at 16:14, 24 May 2014

2014-05-24T16:14:07Z

Arjun Suresh at 15:17, 24 May 2014

2014-05-24T15:17:06Z

Arjun Suresh at 15:16, 24 May 2014

2014-05-24T15:16:31Z

Arjun Suresh at 15:14, 24 May 2014

2014-05-24T15:14:17Z

Arjun Suresh at 15:13, 24 May 2014

2014-05-24T15:13:53Z

Arjun Suresh at 15:12, 24 May 2014

2014-05-24T15:12:04Z

Arjun Suresh at 15:04, 24 May 2014

2014-05-24T15:04:36Z

← Older revision		Revision as of 00:30, 7 May 2015
Line 55:		Line 55:


−	[[Category: ~~Automata~~ Theory]]	+	[[Category: Theory of Computation]]

@@ 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}} }}===
-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 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 <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 } ==

@@ Line 6: / Line 6: @@
 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.
+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 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 <math>L</math>. Thus, <math>L</math> becomes recursive.
 <!--
 =='''2.''' CYCLE(L) ={xy | yx is in L,L is regular } ==

@@ Line 7: / Line 7: @@
 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 ?
@@ Line 50: / Line 50: @@
+}
 </graphviz>
 {{Template:FBD}}

@@ Line 30: / Line 30: @@
 -> 2 [ label = "b" ];
+}
+</graphviz>
 digraph finite_state_machine2 {
 	rankdir=LR;

@@ Line 36: / Line 36: @@
 	rankdir=LR;
 	size="8,5"
-	node [shape = doublecircle]; LR_0;
+	node [shape = doublecircle]; 0,1,2,3;
 	node [shape = circle];
 -> 1 [ label = "a" ];
 -> 0 [ label = "b" ];
+}

@@ Line 12: / Line 12: @@
 ==={{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>
 digraph finite_state_machine {
 	rankdir=LR;
 	size="8,5"
-	node [shape = doublecircle]; LR_3;
+	node [shape = doublecircle]; 3;
 	node [shape = circle];
-	LR_0 -> LR_1 [ label = "a" ];
+-> 1 [ label = "a" ];
-	LR_1 -> LR_2 [ label = "a" ];
+-> 2 [ label = "a" ];
-	LR_2 -> LR_3 [ label = "a" ];
+-> 3 [ label = "a" ];
-	LR_3 -> LR_2 [ label = "a" ];
+-> 2 [ label = "a" ];
-	LR_0-> LR_2 [ label = "b" ];
+-> 2 [ label = "b" ];
-	LR_1 -> LR_0 [ label = "b" ];
+-> 0 [ label = "b" ];
-	LR_2 -> LR_2 [ label = "b" ];
+-> 2 [ label = "b" ];
-	LR_3 -> LR_2 [ label = "b" ];
+-> 2 [ label = "b" ];
+}
 </graphviz>
@@ Line 38: / Line 38: @@
 	node [shape = doublecircle]; LR_0;
 	node [shape = circle];
-	LR_1 -> LR_0 [ label = "a" ];
+-> 1 [ label = "a" ];
+}