Nedeterministični končni avtomati s praznimi prehodi/Primer epsilon-NKA v Mathematici

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?


Clear[nKa, d]
nKa = avtomat[{{q0}, {
q1}, {q2}, {q3}, {q4}}, {"a", "b", "ϵ"}, {q0}, d, {{q1}, {q3}}];
d[{q0}, "ϵ"] = {q1, q3};
d[{q2}, "b"] = {q2};
d[{q2}, "b"] = {q1};
d[{q3}, "a"] = {q4};
d[{q4}, "a"] = {q3};


Clear[stanja, abeceda, zacetnoStanje, prehodnaFunkcija, koncnaStanja]
stanja[a_avtomat] := a[[1]];
abeceda[a_avtomat] := a[[2]];
zacetnoStanje[a_avtomat] := a[[3]];
prehodnaFunkcija[a_avtomat] := a[[4]];
koncnaStanja[a_avtomat] := a[[5]];

Funkcija stanja vrne stanja končnega avtomata;

funkcija abeceda vrne abecedo, nad katero so sestavljene besede, ki jih končni avtomat razpoznava;

funkcija zacetnoStanje vrne stanje, v katerem je končni avtomat na začetku;

funkcija prehodnaFunkcija vrne funkcijo, ki določa delovanje končnega avtomata;

funkcija koncnaStanja vrne množico stanj, v katerih se končni avtomat lahko ustavi, da besedo,ki jo razpoznava, zares razpozna.


Clear[razpoznava]
razpoznava[a_avtomat, qt_, ""] := MemberQ[koncnaStanja[a], qt];
razpoznava[a_avtomat, qt_, w_] := razpoznava[a, prehodnaFunkcija[
a][qt, StringTake[w, 1]], StringDrop[w, 1]]; 
razpoznava[a_avtomat, w_] := razpoznava[a, zacetnoStanje[a], w];

Torej funkcija razpoznava[a, q, b] vrne True, če končni avtomat a , ki je v stanju q, razpoznava besedo b in False sicer.

stanja[nKa]

abeceda[nKa]
zacetnoStanje[nKa]
prehodnaFunkcija[nKa]
koncnaStanja[nKa]

Generiramo deterministični končni avtomat, ki deluje s podatki prej definiranega nedeterminističnega končnega avtomata.

Clear[dKa, e, e1, koncnaStanjaDKa]

koncnaStanjaDKa = \
Subsets[stanja[nKa]][[Take[Flatten[Position[Subsets[stanja[nKa]], \
koncnaStanja[nKa][[1]]]], {1, Length[Flatten[Position[Subsets[stanja[nKa]], \
koncnaStanja[nKa][[1]]]]], 2}]]];

Funkcija koncnaStanjaDKa vrne množico končnih stanj determinističnega končnega avtomata.

e1[d_, st_, zn_] := Module[{dfja, llist}, dfja = d[st, zn];
If[Head[dfja] == List, llist = dfja];
If[Head[dfja] == Symbol, llist = {dfja}];
Map[{#} &, llist]]

Ta funkcija vrne množico stanj nedeterminističnega končnega avtomata, glede na njegovo prehodno funkcijo, kot množico stanj determinističnega končnega avtomata.

dKa = avtomat[Subsets[stanja[nKa]], abeceda[nKa], {zacetnoStanje[nKa]}, e, \
koncnaStanjaDKa];
e[{q0}, "a"] = e1[d, {}, "a"];
e[{q0}, "b"] = e1[d, {}, "b"];
e[{q0}, "ϵ"] = e1[d, {q1, q2}, "ϵ"];
e[{q1}, "a"] = e1[d, {q1}, "a"];
e[{q1}, "b"] = e1[d, {q2}, "b"];
e[{q2}, "a"] = e1[d, {q2}, "a"];
e[{q2}, "b"] = e1[d, {q1}, "b"];
e[{q3}, "a"] = e1[d, {q4}, "a"];
e[{q3}, "b"] = e1[d, {q3}, "b"];
e[{q4}, "a"] = e1[d, {q3}, "a"];
e[{q4}, "b"] = e1[d, {q4}, "b"];
e[{q0, q1}, "a"] = Union[e1[d, {q0}, "a"], e1[d, {q1}, "a"]];
e[{q0, q1}, "b"] = Union[e1[d, {q0}, "b"], e1[d, {q1}, "b"]];
e[{q0, q2}, "a"] = Union[e1[d, {q0}, "a"], e1[d, {q2}, "a"]];
e[{q0, q2}, "b"] = Union[e1[d, {q0}, "b"], e1[d, {q2}, "b"]];
e[{q1, q2}, "a"] = Union[e1[d, {q1}, "a"], e1[d, {q2}, "a"]];
e[{q1, q2}, "b"] = Union[e1[d, {q1}, "b"], e1[d, {q2}, "b"]];
e[{q0, q1, q2}, "a"] = Union[e1[d, {q0},
"a"], e1[d, {q1}, "a"], e1[d, {q2}, "a"]];
e[{q0, q1, q2}, "b"] = Union[e1[d, {q0}, "b
"], e1[d, {q1}, "b"], e1[d, {q2}, "b"]];
e[{}, "a"] = {};
e[{}, "b"] = {};

Osebna orodja