As we can see in this example that from the state diagram from S$\rightarrow$q2 through b we can't come back on the final state no matter whatever the input be(a or b).\\
So,we can remove that state from the Regular Expression.\\
\begin{tikzpicture}[shorten >=2pt,node distance=2cm,on grid,auto]
\node[state,initial ](s) {s};
\node[state](q_0) [right=of s] {$q_0$};
\node[state,accepting](q_1) [right=of q_0] {$q_1$};
\path[->]
(s) edge node{a} (q_0)
(q_0) edge node{b} (q_1)
edge [loop above ] node {a} ()
(q_1) edge [loop above ] node {b} ();
\end{tikzpicture}
\\
Therefore, the regular expression is much simpler now\\
= a.a*b.b*\\
Regular Expression=a$^{+}b^{+}$\\
\\
Minimized DFA:\\
The Transition Table is:\\
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
&a&b\\
\hline
s &q0&q2\\
\hline
q0 &q0&*q1\\
\hline
q2 &q3&q2\\
\hline
*q1 &q3&*q1 \\
\hline
q2 &q3&q2\\
\hline
\end{tabular}\\
\end{center}
Now, as we have already discussed again we will find the 0 equivalent set i.e. separate the final and the non-final states, [s,q0,q2,q3][q1](0 equivalent set).\\
Now, 1 equivalent sets as we see whether s and q0 are equivalent or not. as we can see for transition b q0 is going to transition q1 which is the final state and does not belong to the same state and hence q0 separates out.\\
Now, similarly seeing q2 and q3 with s, concludes that they all are in the same group for 1 transition.\\
[s,q2,q3][q0][q1]\\
Now, for 2 transition we see whether s and q2 belong to the same set or not and we see that they also don't belong to the same set as s is going to different state for a i.e. it is going to q0 which does not belong to the same group form 1 equivalent set.Hence, s separates to form a single set s.\\
Then, we check for q2 and q3 we see that they belong to the same group for a transition and b as well.So, they are in the same set.\\
[q2,q3][s][q0][q1]\\
Now, when we check for 3 equivalent set we get the same equivalent set as for 2 transition and hence that concludes our minimization of the DFA.\\
\begin{tikzpicture}[shorten >=2pt,node distance=2cm,on grid,auto]
\node[state,initial ](s) {$s$};
\node[state](q_0) [right=of s] {$q_0$};
\node[state,accepting](q_1) [right=of q_0] {$q_1$};
\node[state](q_2q_3) [below=of s] {$q_2q_3$};
\path[->]
(s) edge node{a} (q_0)
(q_0) edge node{b} (q_1)
edge [loop above ] node {a} ()
(q_1) edge node {a} (q_2q_3)
edge [loop above ] node {b} ()
(s) edge node{b} (q_2q_3)
(q_2q_3) edge[loop above] node{a,b} (q_2q_3);
\end{tikzpicture}
\\
Complement:\\
\begin{tikzpicture}[shorten >=2pt,node distance=2cm,on grid,auto]
\node[state,initial,accepting](s) {s};
\node[state,accepting](q_0) [right=of s] {$q_0$};
\node[state](q_1) [right=of q_0] {$q_1$};
\node[state,accepting](q_2) [below=of s] {$q_2$};
\node[state,accepting](q_3) [below=of q_2] {$q_3$};
\path[->]
(s) edge node{a} (q_0)
(q_0) edge node{b} (q_1)
edge [loop above ] node {a} ()
(q_1) edge node {a} (q_3)
edge [loop above ] node {b} ()
(s) edge node{b} (q_2)
(q_2) edge node{a} (q_3)
edge [loop right ] node {b} ()
(q_3) edge [bend left =30] node {b} (q_2)
edge [loop below ] node {a} ();
\end{tikzpicture}
\\
Reverse:\\
\begin{tikzpicture}[shorten >=2pt,node distance=2cm,on grid,auto]
\node[state,accepting](s) {s};
\node[state](q_0) [right=of s] {$q_0$};
\node[state,initial](q_1) [right=of q_0] {$q_1$};
\node[state](q_2) [below=of s] {$q_2$};
\node[state ](q_3) [below=of q_2] {$q_3$};
\path[->]
(q0) edge node{a} (s)
(q_1) edge node{b} (q_0)
edge [loop above ] node {b} ()
(q_3) edge node {a} (q_1)
edge [loop below ] node {a} ()
(q_2) edge node{b} (s)
(q_3) edge node{a} (q_2)
(q_2) edge [loop right ] node {a} ()
(q_2) edge [bend left =30] node {b} (q_3);
\end{tikzpicture}
\\
Left Linear:\\
q$_{0}$$\rightarrow$q$_{0}$a$\backslash$sa\\
q$_{1}$$\rightarrow$q$_{1}$b$\backslash$q$_{0}$b\\
q$_{2}$$\rightarrow$q$_{2}$a$\backslash$q$_{3}$b$\backslash$sb\\
q$_{3}$$\rightarrow$q$_{3}$a$\backslash$q$_{2}$aq$_{1}$a\\\\
Right Linear:\\
s$\rightarrow$aq$_{0}$\\
q$_{0}$$\rightarrow$aq$_{0}$$\backslash$bq$_{1}$\\
q$_{1}$$\rightarrow$bq$_{1}$$\backslash$aq$_{3}$\\
q$_{2}$$\rightarrow$aq$_{2}$$\backslash$aq$_{3}$\\
q$_{3}$$\rightarrow$aq$_{3}$$\backslash$bq$_{2}$\\
\\
\\
1 Answer
If you
- end a line by
\\
- and start the next line by
[
you need to separate \\
and [
, otherwise the line break considers it as argument. That's because \\[1cm]
, for example, is a valid syntax which makes a line break plus an additional 1 cm vertical space.
For example, insert a \relax
(which does nothing visible) in your code:
concludes that they all are in the same group for 1 transition.\\\relax
[s,q2,q3][q0][q1]
\\
that are not inside thetabular
.\\ [q2,.q3]
so it is taking the[
as optional argument which should be a length like\\[2pt]
you need to hide the[
by{}[q2
...array
situation. Anyway, answered it before the answer-the-unanswered session today, so gone :-)