2
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}$\\
    \\

\\
  • you have posted a lot (too much) code but as it is just a fragment not a complete document no one can run it to see what error you get, and you have not described the error. just at first sight you need to remove all the \\ that are not inside the tabular. – David Carlisle Oct 3 '15 at 16:09
  • oh that is the problem you have \\ [q2,.q3] so it is taking the [ as optional argument which should be a length like \\[2pt] you need to hide the [ by {}[q2... – David Carlisle Oct 3 '15 at 16:10
  • @DavidCarlisle I wrote an answer in parallel, you may convert your comment to an answer if you like. I can remove mine. Alas, a solution should not stay just a comment and the question "unanswered". – Stefan Kottwitz Oct 3 '15 at 16:15
  • @StefanKottwitz no your answer can stand, although it must be a dup I'd guess:-) – David Carlisle Oct 3 '15 at 16:26
  • @DavidCarlisle Possibly! In the meantime I found a similar one, but in an array situation. Anyway, answered it before the answer-the-unanswered session today, so gone :-) – Stefan Kottwitz Oct 3 '15 at 16:42
3

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]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.