Kihagyás

RegEx

\(\varepsilon\) - mentesítés

Példa - 1

\(G:\)

\[ \begin{array}{lcll} S & \to & AV & \\ V &\to & \varepsilon&\;|\;aSV \\ A& \to & c &\;|\;bSb\end{array} \]

\(H=\{V\}\)

\(G':\)

\[ \begin{array}{lcll} S & \to & AV &\;|\;A \\ V &\to & aS&\;|\;aSV \\ A& \to & c &\;|\;bSb\end{array} \]

Példa - 2

\(G:\)

\[ \begin{array}{lcll} S & \to & BA &\;|\;aa \\ A &\to & BB&\;|\;aAb \\ B& \to & \varepsilon &\;|\;SbA\end{array} \]

\(H_1=\{B\}\)

\(H_2=H_1\cup\{A\}=\{A,B\}\)

\(H_3=H_2\cup\{S\}=\{S,A,B\}\)

\(G':\)

\[ \begin{array}{rlllll} S & \to & BA &\;|A&\;|B\;&\;|\;aa \\ A &\to & BB&\;|\;B&\;|\;aAb&\;|ab \\ B& \to & SbA &\;|\;bA&\;|\;Sb&\;|\;b \\ S'&\to & S&\;|\;\varepsilon\end{array} \]

Példa - 3

\(G:\)

\[ \begin{array}{lcll} S & \to & aSb &\;|\;SS &\;|\;\varepsilon\end{array} \]

\(H:\{S\}\)

\(G':\)

\[ \begin{array}{lcll} S & \to & aSb &\;|\;ab&\\ S'&\to&\varepsilon&\;|\;S\end{array} \]

(Véges) Automaták

  • \(A=(Q,T,\delta,q_0,F)\) rendezett ötös
    • \(Q\)
      • Az állapotok nem üres véges halmaza
    • \(T\)
      • Az input szimbólumok halmaza
    • \(\delta:\;Q\times T\to Q\)
      • leképezés állapot átmeneti függvény
    • \(q_0\in Q\)
      • Kezdőállapot
    • \(F\subseteq Q\)
      • Elfogadóállapotok hamlmaza

Véges, determinisztikus automata

  • \(\delta:\;Q\times T\to Q\)
  • Determinisztikus

Automata megadás táblázattal

\(\delta\) \(a\) \(b\)
\(\underset{\rightarrow}{\leftarrow}\) \(q_0\) \(q_2\) \(q_1\)
\(q_1\) \(q_3\) \(q_0\)
\(q_2\) \(q_0\) \(q_3\)
\(q_3\) \(q_1\) \(q_2\)

Automata megadása gráffal

  • sorry :c, but unfinished
  • érdemes megjelöli a belépési pontot (kívülrő érkező nyíl)
  • Dupla körben vannak a lehetséges megállási pontok
\[ \begin{CD} \textcircled{~\textcircled{\;q_0\;}} @>>> \textcircled{q_1} \\ @VVV @AAA \\ \textcircled{q_2} @<<< \textcircled{q_3} \\ \end{CD} \]

Szabály alkalmazása (alternatív jelölés)

\(\delta(q,a)=p\quad\) helyett \(\quad qa\to p\)

3-as normálforma

\(A\to aB\quad a\in T\)

\(A\to \varepsilon\)

\(L=\{u\in\{a,b\}^*\;|\;u=awb\;\land\;w\in\{a,b\}^*\}\)

\(S\to aA\) \(A\to aA\;|\;bB\) \(B\to \varepsilon\;|\;bB\;|aA\) \(H\to aH\;|\;bH\)

\[ \begin{CD} \rightarrow S @>{a}>> A @>{b}>> \textcircled{B} \\ @V{b}VV \\ H \\ \end{CD} \]

Missing connections:

  • a->a
  • b->b
  • b->a

Konfiguráció

\(qu\quad q\in Q,\;u\in T^*\)

\(w= abbab\)

\(Sabbab\)

Automata

  • \(Sa\to A\)
  • \(Sb\to H\)
  • \(Aa \to A\)
  • \(Ab \to B\)
  • \(Ba \to A\)
  • \(Bb \to B\)

\(F=\{B\}\)

Levezetés

\[ Sabbab \to Abbab\to Bbab \to Bab \to Ab \to B \]
\[ B\in F\implies \text{A szó helyes!} \]

Példa feladat

Bináris, 4-gyel osztható számok automatája 0|1(0|1)*00

  • \(S1\to A\)
  • \(A1\to A\)
  • \(S0\to D\)
  • \(A0\to B\)
  • \(B0\to C\)
  • \(B1\to A\)
  • \(C0\to C\)
  • \(C1\to A\)

\(F=\{C,D\}\)

Akár extra lépések (hibának):

  • \(D0\to H\)
  • \(D1\to H\)
  • \(H0\to H\)
  • \(H1\to H\)

Példa feladat - 2

(a|b|c)^* páratlan b, és nincs 2 c egymás mellett

  • \(Sa \to S\)
  • \(Sb \to B\)

  • \(Sc \to C\)

  • \(Ca \to S\)

  • \(Cb \to B\)

  • \(Cc \to H\)

  • \(Ba \to B\)

  • \(Bb \to S\)

  • \(Bc \to D\)

  • \(Da \to B\)

  • \(Db \to S\)

  • \(Dc \to H\)

  • \(Ha \to H\)

  • \(Hb \to H\)
  • \(Hc \to H\)

\(F=\{B,D\}\)

\[ \begin{array}{rlllll} S & \to & aaB &\;|\;aC \\ B&\to & C&\;|\;b& \\ C& \to & aS &\;|\;\varepsilon\end{array} \]
\[ \begin{array}{rlllll} S & \to & aZ &\;|\;aB \\ Z&\to & aB&\;|\;b& \\ S& \to & aC \\ B&\to&aS&\;|\;\varepsilon&\;|\;bV \\ V&\to&\varepsilon\\C&\to&aS&\;|\;\varepsilon\end{array} \]