Z´ akladn´ı pojmy Regul´ arn´ı jazyky Operace s regul´ arn´ımi jazyky Minimalizace automat˚ u
Koneˇcn´e automaty Jan Hora ˇ a zemˇ Cesk´ edˇ elsk´ a univerzita
17. ˇr´ıjna 2011
Jan Hora
Koneˇ cn´ e automaty
Z´ akladn´ı pojmy Regul´ arn´ı jazyky Operace s regul´ arn´ımi jazyky Minimalizace automat˚ u
Od p´ısmenek ke slov˚ um I
Definice Abeceda je koneˇcn´a mnoˇzina symbol˚ u (znak˚ u). Abecedu budeme obvykle znaˇcit symbolem Σ (velk´e ˇreck´e p´ısmeno Sigma).
I
Definice Slovo nad abecedou Σ je kaˇzd´a koneˇcn´a posloupnost znak˚ u t´eto abecedy.
I
Definice D´elkou slova w rozum´ıme poˇcet jeho znak˚ u a znaˇc´ıme | w |.
I
Znaˇcen´ı Pr´azdn´e slovo (ˇcili slovo neobsahuj´ıc´ı ˇz´adn´y znak) znaˇc´ıme ε (ˇcti epsilon), | ε |= 0. Jan Hora
Koneˇ cn´ e automaty
Z´ akladn´ı pojmy Regul´ arn´ı jazyky Operace s regul´ arn´ımi jazyky Minimalizace automat˚ u
Od slov k jazyku
I
Znaˇcen´ı Mnoˇzinu vˇsech slov nad abecedou Σ znaˇc´ıme Σ∗ .
I
Definice Jazyk je jak´akoli podmnoˇzina mnoˇziny Σ∗ .
Jan Hora
Koneˇ cn´ e automaty
Z´ akladn´ı pojmy Regul´ arn´ı jazyky Operace s regul´ arn´ımi jazyky Minimalizace automat˚ u
Koneˇcnˇe koneˇcn´y automat I
Definice Koneˇcn´y automat (d´ale jen automat) je uspoˇr´adan´a pˇetice (Q, Σ, δ, q0 , F ), kde Q je koneˇcn´a mnoˇzina stav˚ u, Σ je koneˇcn´a vstupn´ı abeceda, δ : Q × Σ → Q je pˇrechodov´a funkce, q0 ∈ F je inici´aln´ı stav a F ⊆ Q je mnoˇzina pˇrij´ımaj´ıc´ıch stav˚ u.
I
Definice V´ypoˇcet automatu nad slovem w = x1 . . . xn je posloupnost stav˚ u r0 , . . . , rn tak, ˇze δ(ri−1 , xi ) = ri , i = 1, . . . n.
I
Definice Automat dan´e slovo pˇrij´ım´a, pokud v´ypoˇcet nad t´ımto slovem konˇc´ı ve stavu n´aleˇzej´ıc´ım do F . Jan Hora
Koneˇ cn´ e automaty
Z´ akladn´ı pojmy Regul´ arn´ı jazyky Operace s regul´ arn´ımi jazyky Minimalizace automat˚ u
Pˇr´ıklady Pˇr´ıklad Navrhnˇete koneˇcn´y automat nad abecedou Σ = {0, 1} pˇrij´ımaj´ıc´ı pr´avˇe slova, kter´a 1. obsahuj´ı alespoˇ n dva znaky, 2. maj´ı poˇcet jedniˇcek dˇeliteln´y tˇremi, 3. maj´ı prvn´ı a posledn´ı znak stejn´y,
Pˇr´ıklad Navrhnˇete koneˇcn´y automat nad abecedou Σ = {A, B} pˇrij´ımaj´ıc´ı pr´avˇe slova, kter´a 1. zaˇc´ınaj´ı na BABA, 2. obsahuj´ı BABA, 3. konˇc´ı na BABA. Jan Hora
Koneˇ cn´ e automaty
Z´ akladn´ı pojmy Regul´ arn´ı jazyky Operace s regul´ arn´ımi jazyky Minimalizace automat˚ u
Pˇr´ıklady
Pˇr´ıklad Zjistˇete jak´y jazyk pˇrij´ımaj´ı automaty
→A B a) C ←D E
0 E C D E E
1 B E E E E
b)
→1 ←2 3
Jan Hora
a 2 1 3
b 3 3 3
Koneˇ cn´ e automaty
Z´ akladn´ı pojmy Regul´ arn´ı jazyky Operace s regul´ arn´ımi jazyky Minimalizace automat˚ u
Regul´arn´ı nen´ı regul´ern´ı
I
Definice Jazyk automatu A je mnoˇzina slov, kter´e automat pˇrij´ım´a. Znaˇc´ıme L(A).
I
Definice Jazyk L se naz´yv´a regul´arn´ı, pokud existuje koneˇcn´y automat A, kter´y ho pˇrij´ım´a, tedy L = L(A).
Jan Hora
Koneˇ cn´ e automaty
Z´ akladn´ı pojmy Regul´ arn´ı jazyky Operace s regul´ arn´ımi jazyky Minimalizace automat˚ u
Doplnˇek
Pˇr´ıklad Navrhnˇete koneˇcn´y automat, kter´y pˇrij´ım´a pr´avˇe slova neobsahuj´ıc´ı 001.
Vˇeta Doplnˇek L0 = Σ∗ \L regul´arn´ıho jazyka L je regul´arn´ı jazyk.
Jan Hora
Koneˇ cn´ e automaty
Z´ akladn´ı pojmy Regul´ arn´ı jazyky Operace s regul´ arn´ımi jazyky Minimalizace automat˚ u
Pr˚ unik
Pˇr´ıklad Navrhnˇete koneˇcn´y automat pˇrij´ımaj´ıc´ı pr´avˇe slova, kter´a konˇc´ı na 1 a z´aroveˇ n obsahuj´ı sekvenci 110.
Vˇeta Pr˚ unik dvou (koneˇcnˇe mnoha) regul´arn´ıch jazyk˚ u je regul´arn´ı jazyk.
Jan Hora
Koneˇ cn´ e automaty
Z´ akladn´ı pojmy Regul´ arn´ı jazyky Operace s regul´ arn´ımi jazyky Minimalizace automat˚ u
Sjednocen´ı
Pˇr´ıklad Navrhnˇete koneˇcn´y automat pˇrij´ımaj´ıc´ı pr´avˇe slova, kter´a konˇc´ı na 1 nebo obsahuj´ı sekvenci 110.
Vˇeta Sjednocen´ı dvou (koneˇcnˇe mnoha) regul´arn´ıch jazyk˚ u je regul´arn´ı jazyk.
Jan Hora
Koneˇ cn´ e automaty
Z´ akladn´ı pojmy Regul´ arn´ı jazyky Operace s regul´ arn´ımi jazyky Minimalizace automat˚ u
Neˇreˇsiteln´y pˇr´ıklad
Pˇr´ıklad Navrhnˇete koneˇcn´y automat, kter´y pˇrij´ım´a pr´avˇe slova {ε, ab, aabb, aaabbb, . . .} = {an b n , n ∈ N}.
Jan Hora
Koneˇ cn´ e automaty
Z´ akladn´ı pojmy Regul´ arn´ı jazyky Operace s regul´ arn´ımi jazyky Minimalizace automat˚ u
Hospody, do kter´ych nevede cesta, jsou zbyteˇcn´e Pˇr´ıklad →← A B Zjistˇete, jak´y jazyk pˇrij´ım´a automat ←C D ←E
0 B D C B B
1 D B B D D
Definice Stav q se naz´yv´a dosaˇziteln´y, pokud existuje slovo w takov´e, ˇze v´ypoˇcet nad t´ımto slovem konˇc´ı ve stavu q.
Definice Koneˇcn´y automat se naz´yv´a dosaˇziteln´y, pokud jsou dosaˇziteln´e vˇsechny jeho stavy. Jan Hora
Koneˇ cn´ e automaty
Z´ akladn´ı pojmy Regul´ arn´ı jazyky Operace s regul´ arn´ımi jazyky Minimalizace automat˚ u
Pˇr´ıklad Pˇr´ıklad Naleznˇete dosaˇzitelnou ˇc´ast automatu A a n´aslednˇe urˇcete, jak´y jazyk dan´y automat pˇrij´ım´a. A →1 ←2 3 4 5 6 7 ←8 Jan Hora
a 5 2 4 6 1 5 8 2
b 5 7 6 1 3 4 1 5
Koneˇ cn´ e automaty
Z´ akladn´ı pojmy Regul´ arn´ı jazyky Operace s regul´ arn´ımi jazyky Minimalizace automat˚ u
Kdyˇz dva dˇelaj´ı tot´eˇz, je to tot´eˇz Definice Dva automaty se naz´yvaj´ı ekvivalentn´ı, pokud pˇrij´ımaj´ı stejn´y jazyk.
Pˇr´ıklad Naleznˇete minim´aln´ı automat, kter´y pˇrij´ım´a stejn´y jazyk jako automat A. A →1 2 ←3 4 5 ←6 Jan Hora
a 1 1 6 1 2 6
b 3 3 5 5 4 2
Koneˇ cn´ e automaty
Z´ akladn´ı pojmy Regul´ arn´ı jazyky Operace s regul´ arn´ımi jazyky Minimalizace automat˚ u
Maxim´aln´ı faktorizace
Definice Bud’ A = (Q, Σ, δ, q0 , F ) koneˇcn´y automat. Stavy q1 a q2 se naz´yvaj´ı ekvivalentn´ı (znaˇc´ıme q1 ∼ q2 ), pokud automaty (Q, Σ, δ, q1 , F ) a (Q, Σ, δ, q2 , F ), pˇrij´ımaj´ı stejn´y jazyk.
Definice Automat A/∼ = (Q/∼, Σ, δ/∼, [q0 ]∼ , F /∼) se naz´yv´a maxim´aln´ı faktorizace automatu A.
Jan Hora
Koneˇ cn´ e automaty
Z´ akladn´ı pojmy Regul´ arn´ı jazyky Operace s regul´ arn´ımi jazyky Minimalizace automat˚ u
Proˇc to dˇelat sloˇzitˇe, kdyˇz to jde jednoduˇse
I
Vˇeta Maxim´aln´ı faktorizace automatu A pˇrij´ım´a stejn´y jazyk jako automat A. Pokud byl automat A dosaˇziteln´y, je tato maxim´aln´ı faktorizace minim´aln´ım automatem (vzhledem k poˇctu stav˚ u) pˇrij´ımaj´ıc´ım jazyk L(A).
I
Definice Automat A se naz´yv´a redukovan´y, pokud je dosaˇziteln´y a jeho maxim´aln´ı faktorizace m´a stejn´y poˇcet stav˚ u jako automat p˚ uvodn´ı.
Jan Hora
Koneˇ cn´ e automaty
Z´ akladn´ı pojmy Regul´ arn´ı jazyky Operace s regul´ arn´ımi jazyky Minimalizace automat˚ u
Svat´y gr´al teorie koneˇcn´ych automat˚ u
I
Vˇeta Bud’te A1 a A2 dva redukovan´e automaty pˇrij´ımaj´ıc´ı stejn´y jazyk. Pak jsou tyto automaty stejn´e aˇz na pˇrejmenov´an´ı stav˚ u.
I
Vˇeta Dva automaty jsou ekvivalentn´ı (pˇrij´ımaj´ı stejn´y jazyk) pr´avˇe tehdy, kdyˇz maxim´aln´ı faktorizace dosaˇziteln´ych ˇc´ast´ı tˇechto automat˚ u jsou shodn´e aˇz na pˇrejmenov´an´ı stav˚ u.
Jan Hora
Koneˇ cn´ e automaty
