DKA minimizacija

Pod DKA minimizacijom se podrazumeva nalaženje determinističkog konačnog automata (DKA) sa najmanjim brojem stanja koji prepoznaje isti regularan jezik kao i zadati DKA. Pokazuje se da je ovaj automat jedinstven do na izomorfizam! Naime, za dva DKA ${\mathcal {A}}=(\Sigma ,Q,i,F,\delta )$ i ${\mathcal {B}}=(\Sigma ,Q',i',F',\delta {}')$ kažemo da su izomorfni ukoliko postoji bijekcija $f:Q\to Q'$ tako da je zadovoljeno :

1. $f(i)=i'$
2. $f[F]=F'$
3. $(\forall a\in \Sigma ,p\in Q)(\,f(\delta (p,a))=\delta '(f(p),a)\,)$

Neformalno govoreći, ovo zapravo znači da ako imamo iscrtan multigraf kojim je predstavljen automat ${\mathcal {A}}$, možemo preimenovati stanja tog grafa (ostavljajući grane netaknutim i ne uvodeći nova početna niti završna stanja ) tako da se dobije multigraf automata ${\mathcal {B}}$. Dakle pri minimizaciji ne možemo dobiti suštinski različite automate i time se rešava pitanje jedinstvenosti. U daljem izlaganju koristićemo mestimično i proiširenu funkciju prelaza $\delta ^{*}(p,\omega )$
gde $p\in Q,\,\omega \in \Sigma ^{*}$, koja se definiše ovako:

• $\delta ^{*}(p,a)=\delta (p,a)$ kada $a\in \Sigma$
• $\delta ^{*}(p,\epsilon )=p$
• $\delta ^{*}(p,\omega a)=\delta (\delta ^{*}(p,\omega ),a)$ gde je $\omega$ neka reč: $|w|\geq 1$ i $a\in \Sigma$

U narednim sekcijama biće izložen skelet teorije koja se tiče minimalnog automata, a zatim će biti izloženo nekoliko algoritama za konstrukciju MDKA uz detaljna objašnjenja.

Minimalni automat preko levih količnika

Neka je dat regularan jezik $L$ nad azbukom $\Sigma$.

• Tada postoji neki DKA ${\mathcal {A}}$ koji ga prepoznaje, odnosno ${\mathcal {L}}({\mathcal {A}})=L$.
• Za $u\in \Sigma ^{*}$ definišemo $u^{-1}X=\{w\in \Sigma ^{*}:uw\in X\}$ gde $X\subset \Sigma ^{*}$(Levi količnik skupa $X$ po reči $u$)
• Definišemo i $Q(L)=\{u^{-1}L:u\in \Sigma ^{*}\}$

Literatura

• Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), „4.13 Partitioning”, The Design and Analysis of Computer Algorithms, Addison-Wesley, стр. 157—162 .
• Berstel, Jean; Boasson, Luc; Carton, Olivier; Fagnot, Isabelle (2010), „Minimization of Automata”, Automata: from Mathematics to Applications, European Mathematical Society, arXiv:1010.5318  
• Brzozowski, J. A. (1963), „Canonical regular expressions and minimal state graphs for definite events”, Proc. Sympos. Math. Theory of Automata (New York, 1962), Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y., стр. 529—561, MR 0175719 .
• Câmpeanu, Cezar; Culik, Karel, II; Salomaa, Kai; Yu, Sheng (2001), „State Complexity of Basic Operations on Finite Languages”, 4th International Workshop on Automata Implementation (WIA '99), Lecture Notes in Computer Science, 2214, Springer-Verlag, стр. 60—70, doi:10.1007/3-540-45526-4_6 .
• David, Julien (2012), „Average complexity of Moore’s and Hopcroft’s algorithms”, Theoretical Computer Science, 417: 50—65, doi:10.1016/j.tcs.2011.10.011 .
• Hopcroft, John (1971), „An n log n algorithm for minimizing states in a finite automaton”, Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971), New York: Academic Press, стр. 189—196, MR 0403320 . See also preliminary version, Technical Report STAN-CS-71-190, Stanford University, Computer Science Department, January 1971.
• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001), Introduction to Automata Theory, Languages, and Computation (2nd изд.), Addison-Wesley .
• Kameda, Tsunehiko; Weiner, Peter (1970), „On the state minimization of nondeterministic finite automata”, IEEE Transactions on Computers, 100 (7), doi:10.1109/T-C.1970.222994 .
• Knuutila, Timo (2001), „Re-describing an algorithm by Hopcroft”, Theoretical Computer Science, 250 (1-2): 333—363, MR 1795249, doi:10.1016/S0304-3975(99)00150-4 .
• Leiss, Ernst (1981), „Succinct representation of regular languages by Boolean automata” (PDF), Theoretical Computer Science, 13 (3): 323—330, MR 603263, doi:10.1016/S0304-3975(81)80005-9 .
• Leiss, Ernst (1985), „Succinct representation of regular languages by Boolean automata II” (PDF), Theoretical Computer Science, 38: 133—136, doi:10.1016/0304-3975(85)90215-4 
• Moore, Edward F. (1956), „Gedanken-experiments on sequential machines”, Automata studies, Annals of mathematics studies, no. 34, Princeton, N. J.: Princeton University Press, стр. 129—153, MR 0078059 .
• Sakarovitch, Jacques (2009), Elements of automata theory, Translated from the French by Reuben Thomas, Cambridge University Press, ISBN 978-0-521-84425-3, Zbl 1188.68177 

Spoljašnje veze

• DFA minimization using the Myhill-Nerode theorem