☰

缺失数字视为零。(s)

tag-icon • tag-icon errors
缺失数字视为零。(s) 
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

如果你

  • 结束一行\\
  • 并在下一行开始[

您需要将\\和分开[，否则换行符会将其视为参数。这是因为\\[1cm]，例如 是一种有效的语法，它会在换行符后加上额外的 1 厘米垂直空间。

例如，\relax在您的代码中插入（不执行任何可见操作）：

concludes that they all are in the same group for 1 transition.\\\relax
[s,q2,q3][q0][q1]

相关内容