188
правок
Изменения
Нет описания правки
|definition =
Пусть дан [[Детерминированные_конечные_автоматы|автомат]] <tex>\mathcal{A}</tex>. Требуется построить автомат <tex>\mathcal{A}_{min}</tex> с наименьшим количеством состояний, распознающий тот же язык, что и <tex>\mathcal{A}</tex>.
}}
==Описание==
Пусть <tex>q</tex> {{---}} состояние автомата <tex>\mathcal{A} = \langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle</tex>.
{{Определение
|definition=
'''Правым языком''' (англ. ''right language'') {{---}} называется язык <tex>L_d(q)</tex>, принимаемый автоматом <tex>\mathcal{A}_{d}(q) = \langle \Sigma , Q , q , T , \delta \rangle</tex>, полученным из <tex>\mathcal{A}</tex> путём добавления уникального начального состояния <tex>q</tex>.
}}
{{Определение
|definition=
'''Левым языком''' (англ. ''left language'') {{---}} называется язык <tex>L_g(q)</tex>, принимаемый автоматом <tex>\mathcal{A}_{g}(q) = \langle \Sigma , Q , q , T , \delta \rangle</tex>, полученным из <tex>\mathcal{A}</tex> путём добавления уникального терминального состояния <tex>q</tex>.
}}
{{Утверждение
|about=1
|statement=
Автомат является детерминированным тогда и только тогда, когда левые языки его состояний попарно не пересекаются.
}}
{{Определение
|definition=
'''Обратное слово''' <tex>r(u)</tex> для слова <tex>u</tex> определяется следующим образом: <tex>r(\varepsilon) = \varepsilon</tex> и если <tex>u = u_1 u_2 u_3 \dotsc u_p</tex>, тогда <tex>r(u) = v_1 v_2 v_3 \dotsc v_p</tex>, где <tex>v_i = u_{p - i + 1}</tex>.
}}
{{Определение
|definition=
'''Обратный язык''' для языка <tex>L</tex> {{---}} язык <tex>r(L) = \{ u \mid r(u) \in L \}</tex>
}}
{{Определение
|definition=
'''Обратный автомат''' для автомата <tex>\mathcal{A} = \langle \Sigma , Q , S , T , \delta \rangle</tex> {{---}} автомат <tex>r(\mathcal{A}) = \langle \Sigma , Q , T , I , r(\delta) \rangle</tex>, полученный из <tex>\mathcal{A}</tex> сменой местами начальных и конечных состояний и сменой направлений переходов.
}}
{{Утверждение
|about=2
|statement=
Если <tex>\mathcal{A}</tex> распознает язык <tex>L</tex>, то <tex>r(\mathcal{A})</tex> распознает <tex>r(L)</tex>.
}}
{{Утверждение
|about=3
|statement=
Если левый язык состояния <tex>q</tex> в <tex>\mathcal{A}</tex> {{---}} <tex>L_g(q)</tex>, тогда его левый язык в <tex>r(A)</tex> {{---}} <tex>L_d(q)</tex>. Аналогично для правого языка <tex>q</tex>.
}}
