Nedeterministični končni avtomat v Mathematici

Iz MaFiRaWiki

Podan imamo nedeterministični končni avtomat nKa s prehodno funkcijo d.

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

naslednje funkcije vrnejo posamezne elemente končnega avtomata, ki jih potrebujemo za generiranje novega končnega avtomata:

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]];

Generiramo deterministični končni avtomat dKa, 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}]]];
koncnaStanjaDKa::usage = "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]]
e1::usage = "Funkcija e1 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, {q0}, "a"];
e[{q0}, "b"] = e1[d, {q0}, "b"];
e[{q1}, "a"] = e1[d, {q1}, "a"];
e[{q1}, "b"] = e1[d, {q1}, "b"];
e[{q2}, "a"] = e1[d, {q2}, "a"];
e[{q2}, "b"] = e1[d, {q2}, "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