Kihagyás

3-as nyelvcsalád

NDA \(\to\) VDA - Példa

NDA

\(\delta\) a b
\(\to S\) \(A,C\)
\(\leftarrow A\) \(A\) \(B,S\)
\(B\) \(A\) \(C,S\)
\(\leftarrow C\) \(S\)

VDA

\(\delta\) a b
\(\to\{S\}\) \(\{A,C\}\) \(\varnothing\)
\(\leftarrow\{A,C\}\) \(\{A,S\}\) \(\{B,S\}\)
\(\varnothing\) \(\varnothing\) \(\varnothing\)
\(\leftarrow\{A,S\}\) \(\{A,C\}\) \(\{B,S\}\)
\(\{B,S\}\) \(\{A,C\}\) \(\{C,S\}\)
\(\leftarrow\{C,S\}\) \(\{A,C,S\}\) \(\varnothing\)
\(\leftarrow\{A,C,S\}\) \(\{A,C,S\}\) \(\{B,S\}\)

Ha a halmazban van elfogadó állapot, akkor oda is kerülhetne a vezérlés, azok a halmazak elfogadó állapotok lesznek

Minimalizálás

\(\delta\) sorszám
\(\to\{S\}\) \(1\)
\(\leftarrow\{A,C\}\) \(2\)
\(\varnothing\) \(3\)
\(\leftarrow\{A,S\}\) \(4\)
\(\{B,S\}\) \(5\)
\(\leftarrow\{C,S\}\) \(6\)
\(\leftarrow\{A,C,S\}\) \(7\)
\(\delta\) a b
\(\rightarrow1\) \(2\) \(3\)
\(\leftarrow2\) \(4\) \(5\)
\(~~~~~3\) \(3\) \(3\)
\(\leftarrow4\) \(2\) \(5\)
\(~~~~~5\) \(2\) \(6\)
\(\leftarrow6\) \(7\) \(3\)
\(\leftarrow7\) \(7\) \(5\)

Elérhetőség viszgálat itt nem volt releváns, mert az előállítás már csak elérhető állapotokon keresztül történt

Első particionáláskor az elfogadó állapotok egy partíciókba kerüljenek (minden más külön)

Minimalizálásnál mindíg az előző osztályba képezést ellenőrizzük, és szakadás ott történik, ahol a leképezés külön partíciókba történik.

Megállni akkor lehet, ha minden szétesik, vagy a lépés már nem adott új partíciót..

\(\sim^0:\{1,3,5\},\qquad\{2,4,6,7\}\)

\(\sim^1:\{1\},\quad\{5\},\quad\{3\}\quad\{2,4,6,7\}\)

\(\sim^2:\{1\},\quad\{5\},\quad\{3\}\quad\{2,4,7\},\quad\{6\}\)

\(\green{\sim^3}:\{1\},\quad\{5\},\quad\{3\}\quad\{2,4,7\},\quad\{6\}\)

\(\delta\) a b
\(\rightarrow1\) \(247\) \(3\)
\(\leftarrow\green{247}\) \(247\) \(5\)
\(~~~~~3\) \(3\) \(3\)
\(~~~~~5\) \(247\) \(6\)
\(\leftarrow6\) \(247\) \(3\)

VDA Feladat 2

\(\mathcal{A}=<\{1,2,3,4,5,6,7,8,9\},\;\{a,b\},\;\delta,\;1,\;\{2,3,9\}>\)

\(\delta\) a b
\(\rightarrow1\) \(4\) \(5\)
\(\leftarrow2\) \(3\) \(4\)
\(\leftarrow3\) \(2\) \(8\)
\(4\) \(9\) \(2\)
\(5\) \(2\) \(3\)
\(\red6\) \(\red8\) \(\red7\)
\(\red7\) \(\red8\) \(\red1\)
\(8\) \(9\) \(3\)
\(\leftarrow9\) \(9\) \(9\)
  • Összefüggő?
    • Elérhetők: \(1,4,5,9,2,3,8\)
    • Kimarad a \(6\) és \(7\)

Minimalizálás 2

\(\sim^0:A_0=\{1,4,5,8\},\qquad B_0=\{2,3,9\}\)

\(A_0\)

\(\delta\) a b
\(1\) \(A\) \(A\)
\(4\) \(B\) \(A\)
\(5\) \(B\) \(A\)
\(8\) \(B\) \(A\)

\(B_0\)

\(\delta\) a b
\(2\) \(B\) \(A\)
\(3\) \(B\) \(A\)
\(9\) \(B\) \(B\)

\(\sim^1:A_1=\{1\},\;B_1=\{5\},C_1\{4,8\},D_1=\;\{2,3\},\;E_1=\{9\}\)

  • \(|A_1| = |B_1| = |E_1| = 1\)
    • azokat nem folytatjuk

\(B_1\)

\(\delta\) a b
\(4\) \(E\) \(D\)
\(8\) \(E\) \(D\)

\(D_1\)

\(\delta\) a b
\(2\) \(D\) \(E\)
\(3\) \(D\) \(E\)
\[ \sim^1\;\equiv\;\sim^2\;\blacksquare \]
\(\delta\) a b
\(\rightarrow1\) \(48\) \(5\)
\(\leftarrow23\) \(23\) \(48\)
\(48\) \(9\) \(23\)
\(5\) \(23\) \(23\)
\(\leftarrow9\) \(9\) \(9\)

BNF

Lista fogalma

  • üres lista a \(nil\)
  • \(<lista>:=<tag>.<lista>|nil\)
  • \(<tag>:= a|c\)
  • pl.: alma3.12.korte45.nil
  • \(S\to A.S\,|\,n;\;A\to a\,|\,c\)
    • \(S\implies A.S\implies a.S \implies a.A.S \implies a.c.S\implies\ldots\implies a.c.a.n\)
  • \(c\) tokennek megfelelő leírás ([0-9]+)
    • \(<szam>:=<szj>|<szj><szam>\)
    • \(<szj>:= 0|1|2..|9\)
  • \(a\) tokennek megfelelő leírás ([a-z]+[0-9]*)
    • \(<azon>:=<\text{betű}>|<\text{betű}><azon>|<\text{betű}><szám>\)
    • \(<\text{betű}>:=\ldots\)