Основная цель данной лекции -
доказать еще один критерий автоматности формального языка.
Этот критерий можно сформулировать в терминах
классов эквивалентности слов по взаимозаменяемости
(однако формальные определения будут даны
без использования понятия класса эквивалентности).
Слова x и y считаются взаимозаменяемыми
(относительно языка L ),
если при замене в любом слове из языка L
подслова, совпадающего с x,
на y
снова получится слово из языка L
и наоборот.
В разделе 6.3
фактически доказывается, что язык L
является автоматным тогда и только тогда, когда
соответствующее отношение взаимозаменяемости
разбивает множество всех слов рассматриваемого алфавита
на конечное число классов эквивалентности.
Но сначала мы докажем аналогичный результат для отношения взаимозаменяемости не подслов, а префиксов (раздел 6.1). Соответствующие классы эквивалентности слов позволяют построить минимальный детерминированный конечный автомат для заданного языка. Известен и другой метод нахождения минимального детерминированного конечного автомата (раздел 6.2), но этот метод можно применять только тогда, когда уже имеется какой-нибудь детерминированный конечный автомат, распознающий данный язык. В конце лекции доказывается, что классы эквивалентности по взаимозаменяемости относительно автоматного языка сами являются автоматными языками.
Определение 6.1.1.
Пусть $$L \subseteq \Sigma ^*$$
и $$y \in \Sigma ^*$$.
Тогда множество правых контекстов
слова y относительно языка L
определяется следующим образом:$$\rightcontext_{L} ( y ) \bydef \{ z \in \Sigma ^* \mid y z \in L \} .$$
Пример 6.1.2. Пусть $$\Sigma = \{ a , b \}$$ и $$L = \{ a^n b a^n \mid n \geq 0 \}$$. Тогда
Определение 6.1.3.
Для любого состояния p
полного детерминированного конечного автомата $$\lalg Q , \Sigma , \Delta , I , F \ralg$$
и любого слова w
обозначим через $$\Delta _{ w } ( p )$$
такое состояние q,
что существует путь из p в q с меткой w
(в силу полноты и детерминированности такое состояние
существует и единственно).
Лемма 6.1.4. Если язык L
распознается полным детерминированным конечным автоматом $$\lalg Q , \Sigma , \Delta , I , F \ralg$$,
то$$| \{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \} | \leq | Q | .$$
Доказательство.
Пусть I = {s}.
Введем обозначение$$J \bydef \{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \} .$$
Определим функцию $$f \colon J \farrow Q$$,
положив f(A)
равным $$\Delta _{ y } ( s )$$,
где y -
некоторое слово,
для которого выполнено условие $$\rightcontext_{L} ( y ) = A$$
(если существует несколько таких слов y,
то можно использовать, например, первое среди них
в лексикографическом порядке).
Заметим, что
для любых слов u и v,
если $$\rightcontext_{L} ( u ) \neq \rightcontext_{L} ( v )$$,
то $$\Delta _{ u } ( s ) \neq \Delta _{ v } ( s )$$.
Следовательно, функция f
является инъективной.
Но тогда $$| J | \leq | Q |$$.
Пример 6.1.5.
Рассмотрим язык L,
порождаемый полным детерминированным конечным автоматом $$\lalg Q , \Sigma , \Delta , I , F \ralg$$
из примера 2.6.4.
Тогда$$\begin{align*}
\{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \} =
\{ \rightcontext_{L} ( \varepsilon ) , \rightcontext_{L} ( a ) ,
\rightcontext_{L} ( b ) \} ,\\
\rightcontext_{L} ( \varepsilon ) =
\{ (ab)^n \mid n \geq 0 \} \pcup \{ (ab)^n a \mid n \geq 0 \} ,\\
\rightcontext_{L} ( a ) =
\{ b (ab)^n \mid n \geq 0 \} \cup \{ (ba)^n \mid n \geq 0 \} ,\\
\rightcontext_{L} ( b ) = \varnothing .
\end{align*}$$
Лемма 6.1.6. Если $$L \subseteq \Sigma ^*$$ и множество $$\{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \}$$ конечно, то язык L является автоматным.
Доказательство.
Язык L
распознается полным детерминированным конечным автоматом $$\lalg Q , \Sigma , \Delta , I , F \ralg$$,
где$$\begin{align*}
Q \peq \{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \} ,\\
I \peq \{ \rightcontext_{L} ( \varepsilon ) \} ,\\
F \peq \{ \rightcontext_{L} ( y ) \mid y \in L \} ,\\
\Delta \peq
\{ \lp \rightcontext_{L} ( y ) , a , \rightcontext_{L} ( y a ) \rp
\mid y \in \Sigma ^* , \ a \in \Sigma \} .
\end{align*}$$
Пример 6.1.7.
Пусть $$\Sigma = \{ a , b \}$$.
Рассмотрим автоматный язык L = a+b*.
Обозначим$$\begin{align*}
q_\varepsilon = \rightcontext_{L} ( \varepsilon ) ,\\
q_a = \rightcontext_{L} ( a ) ,\\
q_b = \rightcontext_{L} ( b ) = \varnothing ,\\
q_{ab} = \rightcontext_{L} ( ab ) .
\end{align*}$$
Тогда $$\{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \} =
\{ q_\varepsilon , q_a , q_b , q_{ab} \}$$.
Язык L
распознается полным детерминированным конечным автоматом $$\lalg Q , \Sigma , \Delta , I , F \ralg$$,
где $$Q = \{ q_\varepsilon , q_a , q_b , q_{ab} \}$$, $$I = \{ q_\varepsilon \}$$, $$F = \{ q_a , q_{ab} \}$$,$$\begin{multiline*}
\Delta = \{
\lp q_\varepsilon , a , q_a \rp ,\
\lp q_\varepsilon , b , q_b \rp ,\
\lp q_a , a , q_a \rp ,\
\lp q_a , b , q_{ab} \rp ,\
\\
\lp q_b , a , q_b \rp ,\
\lp q_b , b , q_b \rp ,\
\lp q_{ab} , a , q_b \rp ,\
\lp q_{ab} , b , q_{ab} \rp
\} .
\end{multiline*}$$
$$\objectwidth={7.5mm} \objectheight={7.5mm} \let\objectstyle=\scriptstyle
\xymatrix {
*=[o][F-]{q_\varepsilon}
\ar @`{+/l16mm/} [] ^{}
\ar "1,2" ^{a}
\ar "2,3" _{b}
*=[o][F=]{q_a}
\rloop{0,1} ^{a}
\ar "1,3" ^{b}
*=[o][F=]{q_{ab}}
\ar "2,3" ^{a}
\rloop{0,1} ^{b}
\\
%
*=[o][F-]{q_b}
\rloop{1,0} ^{a}
\rloop{0,-1} ^{b}
}$$
Теорема 6.1.8. Язык $$L \subseteq \Sigma ^*$$ является автоматным тогда и только тогда, когда множество $$\{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \}$$ конечно.
Доказательство. Необходимость доказана в лемме 6.1.4, достаточность - в лемме 6.1.6.
Замечание 6.1.9. В силу леммы 6.1.4 полный детерминированный конечный автомат, построенный в доказательстве леммы 6.1.6, является минимальным (по количеству состояний) среди всех полных детерминированных конечных автоматов, распознающих заданный язык. Можно доказать, что любой минимальный полный детерминированный конечный автомат, распознающий заданный язык, изоморфен этому автомату.
Упражнение 6.1.10. Пусть $$\Sigma = \{a,b\}$$ и$$L = \{ w \in \Sigma ^* \mid | w |_a = 1 \commaand | w |_b = 2 \} .$$ Сколько элементов содержит множество $$\{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \}$$?
Упражнение 6.1.11. Найти минимальный полный детерминированный конечный автомат для языка {ab,abb}*.
Упражнение 6.1.12. Найти минимальный полный детерминированный конечный автомат для языка$$\{ a b^{2n} \mid n \geq 0 \} \cup \{ c b^{2n+1} \mid n \geq 0 \} .$$
Упражнение 6.1.13. Найти минимальный полный детерминированный конечный автомат для языка$$\{ a b^{2n} \mid n \geq 0 \} \cup \{ b^{4n} \mid n \geq 0 \} .$$
Упражнение 6.1.14. Найти минимальный полный детерминированный конечный автомат для языка$$\{ a^m u b^n \mid m \geq 0 ,\ n \geq 0 ,\ | u | \vdots 3 \} .$$
Определение 6.2.1.
Говорят, что слово w различает
состояния p
и q
полного детерминированного конечного автомата $$\lalg Q , \Sigma , \Delta , I , F \ralg$$,
если одно из состояний $$\Delta _w ( p )$$, $$\Delta _w ( q )$$
заключительное, а другое не является заключительным.
Определение 6.2.2.
Состояния p
и q
полного детерминированного конечного автомата $$\lalg Q , \Sigma , \Delta , I , F \ralg$$
называются различимыми
(distinguishable), если существует
слово w,
которое их различает.
Замечание 6.2.3.
Пусть полный детерминированный конечный автомат $$\lalg Q , \Sigma , \Delta , \{ \qinitial \} , F \ralg$$
задает язык L.
Рассмотрим произвольные слова $$u \in \Sigma^*$$
и $$v \in \Sigma^*$$.
Состояния $$\Delta _u ( \qinitial )$$
и $$\Delta _v ( \qinitial )$$
различимы тогда и только тогда, когда $$\rightcontext_{L} ( u ) \neq \rightcontext_{L} ( v )$$.
Теорема 6.2.4. Существует быстрый алгоритм, позволяющий по произвольному детерминированному конечному автомату находить минимальный (по количеству состояний) автомат среди детерминированных конечных автоматов, эквивалентных исходному автомату.
Доказательство.
Без ограничения общности можно предположить,
что дан
полный детерминированный конечный автомат $$\lalg Q , \Sigma , \Delta , I , F \ralg$$,
все состояния которого достижимы из начального состояния
(для обеспечения полноты достаточно добавить одно состояние).
Для каждого натурального числа i
определим на множестве Q
отношение эквивалентности $$\equiv _i$$:$$\begin{align*}
p \equiv _0 q \iff
( p \in F \rusand q \in F ) \rusor ( p \notin F \rusand q \notin F ) ,\\
p \equiv _{i+1} q \iff p \equiv _i q \rusand
\Delta _a ( p ) \equiv _i \Delta _a ( q )
\mathspace\text{для каждого}\mathspace a \in \Sigma .
\end{align*}$$
Легко видеть, что $$p \equiv _i q$$
тогда и только тогда, когда
никакое слово длины не больше i
не различает p и q.
Обозначим n =|Q|.
Легко проверить, что для любого $$k \geq n$$
отношение $$\equiv _k$$
совпадает с отношением $$\equiv _{n-1}$$.
Используя классы эквивалентности
отношения $$\equiv _{n-1}$$
как состояния, можно построить минимальный
полный детерминированный конечный автомат.
Удалив из него бесполезное состояние
(из которого не достижимо ни одно заключительное состояние),
если такое имеется,
получим искомый минимальный
детерминированный конечный автомат.
Пример 6.2.5. Рассмотрим полный детерминированный конечный автомат $$\lalg \{ 1 , 2 , 3 , 4 , 5 , 6 \} , \{ a , b \} , \Delta , \{ 1 \} , \{ 1 , 3 \} \ralg$$, где$$\begin{multiline*} \Delta = \{ \lp 1 , a , 2 \rp ,\ \lp 2 , b , 3 \rp ,\ \lp 3 , a , 4 \rp ,\ \lp 4 , b , 1 \rp ,\ \lp 4 , a , 5 \rp ,\ \lp 5 , a , 5 \rp ,\ \\ \lp 1 , b , 6 \rp ,\ \lp 2 , a , 6 \rp ,\ \lp 3 , b , 6 \rp ,\ \lp 5 , b , 6 \rp ,\ \lp 6 , a , 6 \rp ,\ \lp 6 , b , 6 \rp \} . \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F=]{1} \ar @`{+/l16mm/} [] ^{} \ar "1,2" ^{a} \ar "2,2" ^{b} *=[o][F-]{2} \ar "1,3" ^{b} \ar "2,2" ^{a} *=[o][F=]{3} \ar "1,4" ^{a} \ar "2,2" ^{b} *=[o][F-]{4} \ar `ul^l{+/u7mm/}`l^dl{[0,-3]}_{b} "1,1" \ar "2,4" ^{a} \\ % *=[o][F-]{6} \rloop{0,-1} ^{a} \rloop{-1,0} ^{b} *=[o][F-]{5} \rloop{0,-1} ^{a} \ar "2,2" ^{b} }$$ Он эквивалентен минимальному детерминированному конечному автомату $$\lalg \{ \{ 1 , 3 \} , \{ 2 , 4 \} \} , \{ a , b \} , \Delta' , \{ \{ 1 , 3 \} \} , \{ \{ 1 , 3 \} \} \ralg$$, где$$\Delta' = \{ \lp \{ 1 , 3 \} , a , \{ 2 , 4 \} \rp ,\ \lp \{ 2 , 4 \} , b , \{ 1 , 3 \} \rp \} .$$ $$\objectwidth={7.5mm} \objectheight={7.5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F=]{1,3} \ar @`{+/l16mm/} [] ^{} \ar "1,2" <0.6mm> ^{a} *=[o][F-]{2,4} \ar "1,1" <0.6mm> ^{b} }$$
Замечание 6.2.6. Неизвестно, существует ли быстрый (полиномиальный) алгоритм, позволяющий по произвольному конечному автомату находить минимальный автомат среди всех (не обязательно детерминированных) конечных автоматов, эквивалентных исходному автомату.
Упражнение 6.2.7. Найти минимальный полный детерминированный конечный автомат для языка, порождаемого грамматикой$$\begin{align*} C \; {\to} \; a D , H \; {\to} \; a C , \\ C \; {\to} \; b E , H \; {\to} \; b E , \\ D \; {\to} \; a E , D \; {\to} \; \varepsilon , \\ D \; {\to} \; b H , H \; {\to} \; \varepsilon . \\ E \; {\to} \; a D , \\ E \; {\to} \; b C , \\ \end{align*}$$
Упражнение 6.2.8. Найти минимальный полный детерминированный конечный автомат для языка
(1+(a+b)*b)b(a+b)*.
Упражнение 6.2.9. Найти минимальный полный детерминированный конечный автомат для языка
(a+b)*(aaba+(aabb+bbaa)abbb)(a+b)*.
Упражнение 6.2.10. Равны ли регулярные выражения
(aa+b+ab)* и ((a+b)*b+1)(aa)*?
Упражнение 6.2.11. Равны ли регулярные выражения
(a+b)*aa(a+b)*bb(a+b)* и (ab+b)*aa(a+b)*bb(a+ba)*?
Упражнение 6.2.12. Равны ли регулярные выражения
((ba+bb)(aa+ab)*)*a и b(aa+ab+ba+bb)*(aa+ba)?
Упражнение 6.2.13. Равны ли регулярные выражения
(ca+cb+cc+(a+b+(a+c))+c)(a+b+c)*
и
c(a+b+bc)++(a+b+c)*(ac+cc)(a+b+bc)*?
Определение 6.3.1.
Пусть $$L \subseteq \Sigma ^*$$
и $$y \in \Sigma ^*$$.
Тогда множество контекстов
( множество двусторонних контекстов )
слова y относительно языка L
определяется следующим образом:$$\bothcontext_{L} ( y ) \mymathrel{\bydef}
\{ \lp x , z \rp \in \Sigma ^* \times \Sigma ^*
\mid x y z \in L \} .$$
Пример 6.3.2. Пусть $$\Sigma = \{ a , b \}$$ и $$L = \{ a^n b a^n \mid n \geq 0 \}$$. Тогда$$\begin{align*} \bothcontext_{L} ( a^i ) = \{ \lp a^m , a^k b a^{k+i+m} \rp \mid m \geq 0 \commaand k \geq 0 \} \cup {} \\ \myqquad \cup \{ \lp a^{k+i+m} b a^k , a^m \rp \mid k \geq 0 \commaand m \geq 0 \} ,\\ \bothcontext_{L} ( a^i b a^j ) = \{ \lp a^k , a^m \rp \mid k \geq 0 ,\ m \geq 0 \commaand k + i = m + j \} ,\\ \rightcontext_{L} ( y ) = \varnothing ,\mathspace\text{если}\mathspace | y |_b > 1 . \end{align*}$$
Лемма 6.3.3. Если $$\bothcontext_{L} ( u_1 ) = \bothcontext_{L} ( u_2 )$$, то $$\rightcontext_{L} ( u_1 ) = \rightcontext_{L} ( u_2 )$$.
Доказательство. Из определений следует, что$$\rightcontext_{L} ( y ) \peq \{ z \in \Sigma ^* \mid \lp \varepsilon , z \rp \in \bothcontext_{L} ( y ) \} .$$
Лемма 6.3.4. Если $$\bothcontext_{L} ( u_1 ) = \bothcontext_{L} ( u_2 )$$, то $$\bothcontext_{L} ( u_1 v ) = \bothcontext_{L} ( u_2 v )$$ и $$\bothcontext_{L} ( v u_1 ) = \bothcontext_{L} ( v u_2 )$$.
Доказательство. Пусть $$\bothcontext_{L} ( u_1 ) = \bothcontext_{L} ( u_2 )$$ и $$\lp x , z \rp \in \bothcontext_{L} ( u_1 v )$$. Тогда $$x u_1 v z \in L$$. Следовательно, $$\lp x , v z \rp \in \bothcontext_{L} ( u_1 )$$. Далее, получаем, что $$\lp x , v z \rp \in \bothcontext_{L} ( u_2 )$$, $$x u_2 v z \in L$$ и $$\lp x , z \rp \in \bothcontext_{L} ( u_2 v )$$. Второе равенство доказывается аналогично.
Лемма 6.3.5. Если $$\bothcontext_{L} ( u_1 ) = \bothcontext_{L} ( u_2 )$$ и $$\bothcontext_{L} ( v_1 ) = \bothcontext_{L} ( v_2 )$$, то $$\bothcontext_{L} ( u_1 v_1 ) = \bothcontext_{L} ( u_2 v_2 )$$.
Определение 6.3.6.
Пусть $$L \subseteq \Sigma ^*$$.
Тогда множество$$\SM ( L ) \bydef
\{ \bothcontext_{L} ( y ) \mid y \in \Sigma ^* \}$$
называется синтаксическим моноидом
(L.
Определение 6.3.7*. Полугруппой
(semigroup) $$\lp M , \star \rp$$
называется непустое множество M
с ассоциативной бинарной операцией $$\star$$.
Определение 6.3.8*. Пусть $$\lp M , \star \rp$$ - полугруппа. Элемент $$e \in M$$ называется единицей (unit), если $$e \star x = x = x \star e$$ для каждого $$x \in M$$.
Определение 6.3.9*. Моноид $$\lp M , \star , e \rp$$ - это полугруппа $$\lp M , \star \rp$$ с единицей $$e \in M$$.
Теорема 6.3.10*. Определим бинарную операцию на Synt(L) следующим образом:$$\bothcontext_{L} ( u ) \star \bothcontext_{L} ( v ) \bydef
\bothcontext_{L} ( u v ) .$$
Тогда $$\lp \SM ( L ) , \star ,
\bothcontext_{L} ( \varepsilon ) \rp$$ является моноидом.
Теорема 6.3.11. Синтаксический моноид Synt(L) конечен тогда и только тогда, когда
язык L является автоматным.
Доказательство
Пусть множество Synt(L)
конечно.
Согласно лемме 6.3.3
множество $$\{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \}$$
тоже конечно.
В силу леммы 6.1.6
язык L является автоматным.
Обратно, пусть язык L
распознается некоторым конечным автоматом $$M = \lalg Q , \Sigma , \Delta , I , F \ralg$$,
не содержащим переходов с метками длины больше единицы.
Поставим в соответствие
каждому слову y
множество $$\mathrm{Tr}_M( y ) \subseteq Q \times Q$$,
определенное следующим образом:$$\mathrm{Tr}_M( y ) \peq
\{ \lp p , q \rp \in Q \times Q
\mid \text{существует путь из }p \text{ в } q \text{ с меткой } y \} .$$
Легко проверить, что если $$\mathrm{Tr}_M( y_1 ) = \mathrm{Tr}_M( y_2 )$$,
то $$\bothcontext_{L} ( y_1 ) \peq \bothcontext_{L} ( y_2 )$$.
Следовательно, $$| \SM ( L ) | \leq 2^{n^2}$$,
где n = |Q|.
Пример 6.3.12.
Рассмотрим конечный автомат M
из примера 2.1.14.
Тогда
Лемма 6.3.13. Пусть $$L \subseteq \Sigma ^*$$, $$n \in \mathbb{N}$$ и для каждого слова $$y \in \Sigma ^*$$
длины n найдется такое слово $$x \in \Sigma ^*$$, что $$| x | < n$$ и $$\bothcontext_{L} ( x ) = \bothcontext_{L} ( y )$$. Тогда$$\SM ( L ) =
\{ \bothcontext_{L} ( y ) \mid y \in \Sigma ^* \commaand | y | < n \} .$$
Доказательство.
Индукцией по $$k \geq n$$
можно доказать, что
для каждого слова $$y \in \Sigma ^*$$
длины k
найдется такое слово $$x \in \Sigma ^*$$,
что $$| x | < n$$
и $$\bothcontext_{L} ( x ) = \bothcontext_{L} ( y )$$.
В
Упражнение 6.3.14. Сколько элементов в синтаксическом a+b над алфавитом {a,b}?
Упражнение 6.3.15. Сколько элементов в синтаксическом b+a+ над алфавитом {a,b}?
Упражнение 6.3.16. Сколько элементов в синтаксическом (aa+b)* над алфавитом {a,b}?
Упражнение 6.3.17. Сколько элементов в синтаксическом (ab)*(ba)*+a* над алфавитом {a,b}?
Упражнение 6.3.18. Сколько элементов в синтаксическом a(b+c)*a(a+b+c)*+b(a+c)*b(a+b+c)*+c(a+b)*c(a+b+c)*
над алфавитом {a,b,c}?
Лемма 6.4.1. Пусть $$L \subseteq \Sigma ^*$$ и $$y \in \Sigma ^*$$. Тогда$$\begin{align*} \rightcontext_{\Sigma ^* \sminus L} ( y ) = \Sigma ^* \sminus \rightcontext_{L} ( y ) ,\\ \bothcontext_{\Sigma ^* \sminus L} ( y ) = (\Sigma ^* \times \Sigma ^*) \sminus \bothcontext_{L} ( y ) . \end{align*}$$
Определение 6.4.2. Пусть $$L \subseteq \Sigma ^*$$ и $$x \in \Sigma ^*$$. Обозначим через $$[ x ]\supright_{L}$$ язык $$\{ y \in \Sigma ^* \mid \rightcontext_{L} ( y ) = \rightcontext_{L} ( x ) \}$$. Обозначим через $$[ x ]_{L}$$ язык $$\{ y \in \Sigma ^* \mid \bothcontext_{L} ( y ) = \bothcontext_{L} ( x ) \}$$.
Пример 6.4.3. Пусть $$L \subseteq \Sigma ^*$$. Множества вида $$[ x ]\supright_{L}$$ образуют разбиение множества $$\Sigma ^*$$ на классы эквивалентности. Множества вида $$[ x ]_{L}$$ образуют разбиение множества $$\Sigma ^*$$ на классы эквивалентности.
Пример 6.4.4. Пусть $$\Sigma = \{ a , b \}$$ и $$L = \{ a^n b a^n \mid n \geq 0 \}$$. Тогда$$\begin{align*} [baa]\supright_{L} = \{ a^i b a^j \mid 0 \leq i < j \} \cup \{ y \in \Sigma ^* \mid | y |_b > 1 \} ,\\ [baa]_{L} = \{ a^i b a^{i+2} \mid i \geq 0 \} . \end{align*}$$
Лемма 6.4.5. Если язык $$L \subseteq \Sigma ^*$$ является автоматным, то для каждого слова $$x \in \Sigma ^*$$ языки $$[ x ]\supright_{L}$$ и $$[ x ]_{L}$$ являются автоматными.
Доказательство.
Пусть язык L
распознается конечным автоматом $$M = \lalg Q , \Sigma , \Delta , I , F \ralg$$,
не содержащим переходов с метками длины больше единицы.
Будем использовать обозначение TrM
из доказательства теоремы 6.3.11.
При любой фиксированной паре $$\lp p , q \rp \in Q \times Q$$
язык $$\cala _{ p , q , M } =
\{ y \in \Sigma ^* \mid \lp p , q \rp \in \mathrm{Tr}_M( y ) \}$$
является автоматным
(он распознается конечным автоматом $$\lalg Q , \Sigma , \Delta , \{ p \} , \{ q \} \ralg$$ ).
Для каждого слова $$z \in \Sigma ^*$$
язык $$\calb _{ z , M } =
\{ y \in \Sigma ^* \mid \mathrm{Tr}_M( y ) = \mathrm{Tr}_M( z ) \}$$
является автоматным, так как он
представим в виде пересечения конечного семейства автоматных языков:$$\calb _{ z , M } =
\biggl(\,
\raisebox{0pt}[\height][0.95\depth]{\displaystyle
\bigcap _{ \lp p , q \rp \in \mathrm{Tr}_M( z ) }}
\cala _{ p , q , M } \biggr)
\cap
\biggl(\,
\raisebox{0pt}[\height][0.95\depth]{\displaystyle
\bigcap _{ \lp p , q \rp \notin \mathrm{Tr}_M( z ) }}
( \Sigma ^* \sminus \cala _{ p , q , M } )\biggr) .$$
Каждый из языков [x]L
и $$[ x ]\supright_{L}$$
является объединением конечного семейства автоматных языков:$$\raisebox{0pt}[\height][0pt]{\displaystyle
[ x ]_{L} = \bigcup _{ z \in [ x ]_{L} } \calb _{ z , M }} ,
\qquad
\raisebox{0pt}[\height][0pt]{\displaystyle
[ x ]\supright_{L} =
\bigcup _{ z \in [ x ]\supright_{L} } \calb _{ z , M }} .$$
Замечание 6.4.6.
Из теоремы 6.1.8
вытекает, что если язык L
автоматный, то существует лишь конечное число
различных множеств $$[ x ]\supright_{L}$$.
Аналогичное утверждение верно для множеств $$[ x ]_{L}$$
(см. теорему 6.3.11).
Пример 6.4.7. Рассмотрим язык$$L = \{ (ab)^n \mid n \geq 0 \} \cup \{ (ab)^n a \mid n \geq 0 \}$$ над алфавитом $$\Sigma = \{ a , b \}$$. Тогда$$\begin{align*} [ \varepsilon ]\supright_{L} = (ab)^* ;\\ [ a ]\supright_{L} = (ab)^* a ;\\ [ b ]\supright_{L} = b (a \replus b)^* \replus (a \replus b)^* (aa \replus bb) (a \replus b)^* ;\\ [ \varepsilon ]_{L} = 1 ;\\ [ ab ]_{L} = (ab)^+ ;\\ [ ba ]_{L} = (ba)^+ ;\\ [ a ]_{L} = (ab)^* a ;\\ [ b ]_{L} = b (ab)^* ;\\ [ aa ]_{L} = (a \replus b)^* (aa \replus bb) (a \replus b)^* . \end{align*}$$
Упражнение 6.4.8.
Существуют ли такие языки $$L_1 \subseteq \Sigma ^*$$
и $$L_2 \subseteq \Sigma ^*$$,
что язык L1
является автоматным, но язык$$L_3 = \{ x \in \Sigma ^* \mid
x y \in L_1 \mathspace\text{для некоторого слова}\mathspace y \in L_2 \}$$
не является автоматным?
Упражнение 6.4.9.
Существуют ли такие языки $$L_1 \subseteq \Sigma ^*$$
и $$L_2 \subseteq \Sigma ^*$$,
что язык L1
является автоматным, но язык$$L_3 = \{ x \in \Sigma ^* \mid
x y \in L_1 \mathspace\text{для всех слов}\mathspace y \in L_2 \}$$
не является автоматным?
Упражнение 6.4.10. Существует ли такой автоматный язык $$L \subseteq \Sigma ^*$$, что язык$$\mathrm{Max} ( L ) \bydef \{ x \in L \mid x y \notin L \mathspace\text{для всех слов}\mathspace y \in \Sigma ^+ \}$$ не является автоматным?
Теорема 6.4.11. Язык $$L \subseteq \Sigma ^*$$ является автоматным тогда и только тогда, когда
существует такое отношение эквивалентности $$R \subseteq \Sigma ^* \times \Sigma ^*$$,
что R разбивает $$\Sigma ^*$$
на конечное множество классов эквивалентности, L является объединением некоторых из этих классов эквивалентности
и для любых $$x \in \Sigma ^*$$, $$y \in \Sigma ^*$$, $$z \in \Sigma ^*$$
из xRy следует xzRyz.
Замечание 6.4.12. Теоремы 6.1.8 и 6.4.11 образуют теорему Майхилла-Нерода.
Основная цель данной лекции -
доказать еще один критерий автоматности формального языка.
Этот критерий можно сформулировать в терминах
классов эквивалентности слов по взаимозаменяемости
(однако формальные определения будут даны
без использования понятия класса эквивалентности).
Слова x и y считаются взаимозаменяемыми
(относительно языка L ),
если при замене в любом слове из языка L
подслова, совпадающего с x,
на y
снова получится слово из языка L
и наоборот.
В разделе 6.3
фактически доказывается, что язык L
является автоматным тогда и только тогда, когда
соответствующее отношение взаимозаменяемости
разбивает множество всех слов рассматриваемого алфавита
на конечное число классов эквивалентности.
Но сначала мы докажем аналогичный результат для отношения взаимозаменяемости не подслов, а префиксов (раздел 6.1). Соответствующие классы эквивалентности слов позволяют построить минимальный детерминированный конечный автомат для заданного языка. Известен и другой метод нахождения минимального детерминированного конечного автомата (раздел 6.2), но этот метод можно применять только тогда, когда уже имеется какой-нибудь детерминированный конечный автомат, распознающий данный язык. В конце лекции доказывается, что классы эквивалентности по взаимозаменяемости относительно автоматного языка сами являются автоматными языками.
Определение 6.1.1.
Пусть $$L \subseteq \Sigma ^*$$
и $$y \in \Sigma ^*$$.
Тогда множество правых контекстов
слова y относительно языка L
определяется следующим образом:$$\rightcontext_{L} ( y ) \bydef \{ z \in \Sigma ^* \mid y z \in L \} .$$
Пример 6.1.2. Пусть $$\Sigma = \{ a , b \}$$ и $$L = \{ a^n b a^n \mid n \geq 0 \}$$. Тогда
Определение 6.1.3.
Для любого состояния p
полного детерминированного конечного автомата $$\lalg Q , \Sigma , \Delta , I , F \ralg$$
и любого слова w
обозначим через $$\Delta _{ w } ( p )$$
такое состояние q,
что существует путь из p в q с меткой w
(в силу полноты и детерминированности такое состояние
существует и единственно).
Лемма 6.1.4. Если язык L
распознается полным детерминированным конечным автоматом $$\lalg Q , \Sigma , \Delta , I , F \ralg$$,
то$$| \{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \} | \leq | Q | .$$
Доказательство.
Пусть I = {s}.
Введем обозначение$$J \bydef \{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \} .$$
Определим функцию $$f \colon J \farrow Q$$,
положив f(A)
равным $$\Delta _{ y } ( s )$$,
где y -
некоторое слово,
для которого выполнено условие $$\rightcontext_{L} ( y ) = A$$
(если существует несколько таких слов y,
то можно использовать, например, первое среди них
в лексикографическом порядке).
Заметим, что
для любых слов u и v,
если $$\rightcontext_{L} ( u ) \neq \rightcontext_{L} ( v )$$,
то $$\Delta _{ u } ( s ) \neq \Delta _{ v } ( s )$$.
Следовательно, функция f
является инъективной.
Но тогда $$| J | \leq | Q |$$.
Пример 6.1.5.
Рассмотрим язык L,
порождаемый полным детерминированным конечным автоматом $$\lalg Q , \Sigma , \Delta , I , F \ralg$$
из примера 2.6.4.
Тогда$$\begin{align*}
\{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \} =
\{ \rightcontext_{L} ( \varepsilon ) , \rightcontext_{L} ( a ) ,
\rightcontext_{L} ( b ) \} ,\\
\rightcontext_{L} ( \varepsilon ) =
\{ (ab)^n \mid n \geq 0 \} \pcup \{ (ab)^n a \mid n \geq 0 \} ,\\
\rightcontext_{L} ( a ) =
\{ b (ab)^n \mid n \geq 0 \} \cup \{ (ba)^n \mid n \geq 0 \} ,\\
\rightcontext_{L} ( b ) = \varnothing .
\end{align*}$$
Лемма 6.1.6. Если $$L \subseteq \Sigma ^*$$ и множество $$\{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \}$$ конечно, то язык L является автоматным.
Доказательство.
Язык L
распознается полным детерминированным конечным автоматом $$\lalg Q , \Sigma , \Delta , I , F \ralg$$,
где$$\begin{align*}
Q \peq \{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \} ,\\
I \peq \{ \rightcontext_{L} ( \varepsilon ) \} ,\\
F \peq \{ \rightcontext_{L} ( y ) \mid y \in L \} ,\\
\Delta \peq
\{ \lp \rightcontext_{L} ( y ) , a , \rightcontext_{L} ( y a ) \rp
\mid y \in \Sigma ^* , \ a \in \Sigma \} .
\end{align*}$$
Пример 6.1.7.
Пусть $$\Sigma = \{ a , b \}$$.
Рассмотрим автоматный язык L = a+b*.
Обозначим$$\begin{align*}
q_\varepsilon = \rightcontext_{L} ( \varepsilon ) ,\\
q_a = \rightcontext_{L} ( a ) ,\\
q_b = \rightcontext_{L} ( b ) = \varnothing ,\\
q_{ab} = \rightcontext_{L} ( ab ) .
\end{align*}$$
Тогда $$\{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \} =
\{ q_\varepsilon , q_a , q_b , q_{ab} \}$$.
Язык L
распознается полным детерминированным конечным автоматом $$\lalg Q , \Sigma , \Delta , I , F \ralg$$,
где $$Q = \{ q_\varepsilon , q_a , q_b , q_{ab} \}$$, $$I = \{ q_\varepsilon \}$$, $$F = \{ q_a , q_{ab} \}$$,$$\begin{multiline*}
\Delta = \{
\lp q_\varepsilon , a , q_a \rp ,\
\lp q_\varepsilon , b , q_b \rp ,\
\lp q_a , a , q_a \rp ,\
\lp q_a , b , q_{ab} \rp ,\
\\
\lp q_b , a , q_b \rp ,\
\lp q_b , b , q_b \rp ,\
\lp q_{ab} , a , q_b \rp ,\
\lp q_{ab} , b , q_{ab} \rp
\} .
\end{multiline*}$$
$$\objectwidth={7.5mm} \objectheight={7.5mm} \let\objectstyle=\scriptstyle
\xymatrix {
*=[o][F-]{q_\varepsilon}
\ar @`{+/l16mm/} [] ^{}
\ar "1,2" ^{a}
\ar "2,3" _{b}
*=[o][F=]{q_a}
\rloop{0,1} ^{a}
\ar "1,3" ^{b}
*=[o][F=]{q_{ab}}
\ar "2,3" ^{a}
\rloop{0,1} ^{b}
\\
%
*=[o][F-]{q_b}
\rloop{1,0} ^{a}
\rloop{0,-1} ^{b}
}$$
Теорема 6.1.8. Язык $$L \subseteq \Sigma ^*$$ является автоматным тогда и только тогда, когда множество $$\{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \}$$ конечно.
Доказательство. Необходимость доказана в лемме 6.1.4, достаточность - в лемме 6.1.6.
Замечание 6.1.9. В силу леммы 6.1.4 полный детерминированный конечный автомат, построенный в доказательстве леммы 6.1.6, является минимальным (по количеству состояний) среди всех полных детерминированных конечных автоматов, распознающих заданный язык. Можно доказать, что любой минимальный полный детерминированный конечный автомат, распознающий заданный язык, изоморфен этому автомату.
Упражнение 6.1.10. Пусть $$\Sigma = \{a,b\}$$ и$$L = \{ w \in \Sigma ^* \mid | w |_a = 1 \commaand | w |_b = 2 \} .$$ Сколько элементов содержит множество $$\{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \}$$?
Упражнение 6.1.11. Найти минимальный полный детерминированный конечный автомат для языка {ab,abb}*.
Упражнение 6.1.12. Найти минимальный полный детерминированный конечный автомат для языка$$\{ a b^{2n} \mid n \geq 0 \} \cup \{ c b^{2n+1} \mid n \geq 0 \} .$$
Упражнение 6.1.13. Найти минимальный полный детерминированный конечный автомат для языка$$\{ a b^{2n} \mid n \geq 0 \} \cup \{ b^{4n} \mid n \geq 0 \} .$$
Упражнение 6.1.14. Найти минимальный полный детерминированный конечный автомат для языка$$\{ a^m u b^n \mid m \geq 0 ,\ n \geq 0 ,\ | u | \vdots 3 \} .$$
Определение 6.2.1.
Говорят, что слово w различает
состояния p
и q
полного детерминированного конечного автомата $$\lalg Q , \Sigma , \Delta , I , F \ralg$$,
если одно из состояний $$\Delta _w ( p )$$, $$\Delta _w ( q )$$
заключительное, а другое не является заключительным.
Определение 6.2.2.
Состояния p
и q
полного детерминированного конечного автомата $$\lalg Q , \Sigma , \Delta , I , F \ralg$$
называются различимыми
(distinguishable), если существует
слово w,
которое их различает.
Замечание 6.2.3.
Пусть полный детерминированный конечный автомат $$\lalg Q , \Sigma , \Delta , \{ \qinitial \} , F \ralg$$
задает язык L.
Рассмотрим произвольные слова $$u \in \Sigma^*$$
и $$v \in \Sigma^*$$.
Состояния $$\Delta _u ( \qinitial )$$
и $$\Delta _v ( \qinitial )$$
различимы тогда и только тогда, когда $$\rightcontext_{L} ( u ) \neq \rightcontext_{L} ( v )$$.
Теорема 6.2.4. Существует быстрый алгоритм, позволяющий по произвольному детерминированному конечному автомату находить минимальный (по количеству состояний) автомат среди детерминированных конечных автоматов, эквивалентных исходному автомату.
Доказательство.
Без ограничения общности можно предположить,
что дан
полный детерминированный конечный автомат $$\lalg Q , \Sigma , \Delta , I , F \ralg$$,
все состояния которого достижимы из начального состояния
(для обеспечения полноты достаточно добавить одно состояние).
Для каждого натурального числа i
определим на множестве Q
отношение эквивалентности $$\equiv _i$$:$$\begin{align*}
p \equiv _0 q \iff
( p \in F \rusand q \in F ) \rusor ( p \notin F \rusand q \notin F ) ,\\
p \equiv _{i+1} q \iff p \equiv _i q \rusand
\Delta _a ( p ) \equiv _i \Delta _a ( q )
\mathspace\text{для каждого}\mathspace a \in \Sigma .
\end{align*}$$
Легко видеть, что $$p \equiv _i q$$
тогда и только тогда, когда
никакое слово длины не больше i
не различает p и q.
Обозначим n =|Q|.
Легко проверить, что для любого $$k \geq n$$
отношение $$\equiv _k$$
совпадает с отношением $$\equiv _{n-1}$$.
Используя классы эквивалентности
отношения $$\equiv _{n-1}$$
как состояния, можно построить минимальный
полный детерминированный конечный автомат.
Удалив из него бесполезное состояние
(из которого не достижимо ни одно заключительное состояние),
если такое имеется,
получим искомый минимальный
детерминированный конечный автомат.
Пример 6.2.5. Рассмотрим полный детерминированный конечный автомат $$\lalg \{ 1 , 2 , 3 , 4 , 5 , 6 \} , \{ a , b \} , \Delta , \{ 1 \} , \{ 1 , 3 \} \ralg$$, где$$\begin{multiline*} \Delta = \{ \lp 1 , a , 2 \rp ,\ \lp 2 , b , 3 \rp ,\ \lp 3 , a , 4 \rp ,\ \lp 4 , b , 1 \rp ,\ \lp 4 , a , 5 \rp ,\ \lp 5 , a , 5 \rp ,\ \\ \lp 1 , b , 6 \rp ,\ \lp 2 , a , 6 \rp ,\ \lp 3 , b , 6 \rp ,\ \lp 5 , b , 6 \rp ,\ \lp 6 , a , 6 \rp ,\ \lp 6 , b , 6 \rp \} . \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F=]{1} \ar @`{+/l16mm/} [] ^{} \ar "1,2" ^{a} \ar "2,2" ^{b} *=[o][F-]{2} \ar "1,3" ^{b} \ar "2,2" ^{a} *=[o][F=]{3} \ar "1,4" ^{a} \ar "2,2" ^{b} *=[o][F-]{4} \ar `ul^l{+/u7mm/}`l^dl{[0,-3]}_{b} "1,1" \ar "2,4" ^{a} \\ % *=[o][F-]{6} \rloop{0,-1} ^{a} \rloop{-1,0} ^{b} *=[o][F-]{5} \rloop{0,-1} ^{a} \ar "2,2" ^{b} }$$ Он эквивалентен минимальному детерминированному конечному автомату $$\lalg \{ \{ 1 , 3 \} , \{ 2 , 4 \} \} , \{ a , b \} , \Delta' , \{ \{ 1 , 3 \} \} , \{ \{ 1 , 3 \} \} \ralg$$, где$$\Delta' = \{ \lp \{ 1 , 3 \} , a , \{ 2 , 4 \} \rp ,\ \lp \{ 2 , 4 \} , b , \{ 1 , 3 \} \rp \} .$$ $$\objectwidth={7.5mm} \objectheight={7.5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F=]{1,3} \ar @`{+/l16mm/} [] ^{} \ar "1,2" <0.6mm> ^{a} *=[o][F-]{2,4} \ar "1,1" <0.6mm> ^{b} }$$
Замечание 6.2.6. Неизвестно, существует ли быстрый (полиномиальный) алгоритм, позволяющий по произвольному конечному автомату находить минимальный автомат среди всех (не обязательно детерминированных) конечных автоматов, эквивалентных исходному автомату.
Упражнение 6.2.7. Найти минимальный полный детерминированный конечный автомат для языка, порождаемого грамматикой$$\begin{align*} C \; {\to} \; a D , H \; {\to} \; a C , \\ C \; {\to} \; b E , H \; {\to} \; b E , \\ D \; {\to} \; a E , D \; {\to} \; \varepsilon , \\ D \; {\to} \; b H , H \; {\to} \; \varepsilon . \\ E \; {\to} \; a D , \\ E \; {\to} \; b C , \\ \end{align*}$$
Упражнение 6.2.8. Найти минимальный полный детерминированный конечный автомат для языка
(1+(a+b)*b)b(a+b)*.
Упражнение 6.2.9. Найти минимальный полный детерминированный конечный автомат для языка
(a+b)*(aaba+(aabb+bbaa)abbb)(a+b)*.
Упражнение 6.2.10. Равны ли регулярные выражения
(aa+b+ab)* и ((a+b)*b+1)(aa)*?
Упражнение 6.2.11. Равны ли регулярные выражения
(a+b)*aa(a+b)*bb(a+b)* и (ab+b)*aa(a+b)*bb(a+ba)*?
Упражнение 6.2.12. Равны ли регулярные выражения
((ba+bb)(aa+ab)*)*a и b(aa+ab+ba+bb)*(aa+ba)?
Упражнение 6.2.13. Равны ли регулярные выражения
(ca+cb+cc+(a+b+(a+c))+c)(a+b+c)*
и
c(a+b+bc)++(a+b+c)*(ac+cc)(a+b+bc)*?
Определение 6.3.1.
Пусть $$L \subseteq \Sigma ^*$$
и $$y \in \Sigma ^*$$.
Тогда множество контекстов
( множество двусторонних контекстов )
слова y относительно языка L
определяется следующим образом:$$\bothcontext_{L} ( y ) \mymathrel{\bydef}
\{ \lp x , z \rp \in \Sigma ^* \times \Sigma ^*
\mid x y z \in L \} .$$
Пример 6.3.2. Пусть $$\Sigma = \{ a , b \}$$ и $$L = \{ a^n b a^n \mid n \geq 0 \}$$. Тогда$$\begin{align*} \bothcontext_{L} ( a^i ) = \{ \lp a^m , a^k b a^{k+i+m} \rp \mid m \geq 0 \commaand k \geq 0 \} \cup {} \\ \myqquad \cup \{ \lp a^{k+i+m} b a^k , a^m \rp \mid k \geq 0 \commaand m \geq 0 \} ,\\ \bothcontext_{L} ( a^i b a^j ) = \{ \lp a^k , a^m \rp \mid k \geq 0 ,\ m \geq 0 \commaand k + i = m + j \} ,\\ \rightcontext_{L} ( y ) = \varnothing ,\mathspace\text{если}\mathspace | y |_b > 1 . \end{align*}$$
Лемма 6.3.3. Если $$\bothcontext_{L} ( u_1 ) = \bothcontext_{L} ( u_2 )$$, то $$\rightcontext_{L} ( u_1 ) = \rightcontext_{L} ( u_2 )$$.
Доказательство. Из определений следует, что$$\rightcontext_{L} ( y ) \peq \{ z \in \Sigma ^* \mid \lp \varepsilon , z \rp \in \bothcontext_{L} ( y ) \} .$$
Лемма 6.3.4. Если $$\bothcontext_{L} ( u_1 ) = \bothcontext_{L} ( u_2 )$$, то $$\bothcontext_{L} ( u_1 v ) = \bothcontext_{L} ( u_2 v )$$ и $$\bothcontext_{L} ( v u_1 ) = \bothcontext_{L} ( v u_2 )$$.
Доказательство. Пусть $$\bothcontext_{L} ( u_1 ) = \bothcontext_{L} ( u_2 )$$ и $$\lp x , z \rp \in \bothcontext_{L} ( u_1 v )$$. Тогда $$x u_1 v z \in L$$. Следовательно, $$\lp x , v z \rp \in \bothcontext_{L} ( u_1 )$$. Далее, получаем, что $$\lp x , v z \rp \in \bothcontext_{L} ( u_2 )$$, $$x u_2 v z \in L$$ и $$\lp x , z \rp \in \bothcontext_{L} ( u_2 v )$$. Второе равенство доказывается аналогично.
Лемма 6.3.5. Если $$\bothcontext_{L} ( u_1 ) = \bothcontext_{L} ( u_2 )$$ и $$\bothcontext_{L} ( v_1 ) = \bothcontext_{L} ( v_2 )$$, то $$\bothcontext_{L} ( u_1 v_1 ) = \bothcontext_{L} ( u_2 v_2 )$$.
Определение 6.3.6.
Пусть $$L \subseteq \Sigma ^*$$.
Тогда множество$$\SM ( L ) \bydef
\{ \bothcontext_{L} ( y ) \mid y \in \Sigma ^* \}$$
называется синтаксическим моноидом
(L.
Определение 6.3.7*. Полугруппой
(semigroup) $$\lp M , \star \rp$$
называется непустое множество M
с ассоциативной бинарной операцией $$\star$$.
Определение 6.3.8*. Пусть $$\lp M , \star \rp$$ - полугруппа. Элемент $$e \in M$$ называется единицей (unit), если $$e \star x = x = x \star e$$ для каждого $$x \in M$$.
Определение 6.3.9*. Моноид $$\lp M , \star , e \rp$$ - это полугруппа $$\lp M , \star \rp$$ с единицей $$e \in M$$.
Теорема 6.3.10*. Определим бинарную операцию на Synt(L) следующим образом:$$\bothcontext_{L} ( u ) \star \bothcontext_{L} ( v ) \bydef
\bothcontext_{L} ( u v ) .$$
Тогда $$\lp \SM ( L ) , \star ,
\bothcontext_{L} ( \varepsilon ) \rp$$ является моноидом.
Теорема 6.3.11. Синтаксический моноид Synt(L) конечен тогда и только тогда, когда
язык L является автоматным.
Доказательство
Пусть множество Synt(L)
конечно.
Согласно лемме 6.3.3
множество $$\{ \rightcontext_{L} ( y ) \mid y \in \Sigma ^* \}$$
тоже конечно.
В силу леммы 6.1.6
язык L является автоматным.
Обратно, пусть язык L
распознается некоторым конечным автоматом $$M = \lalg Q , \Sigma , \Delta , I , F \ralg$$,
не содержащим переходов с метками длины больше единицы.
Поставим в соответствие
каждому слову y
множество $$\mathrm{Tr}_M( y ) \subseteq Q \times Q$$,
определенное следующим образом:$$\mathrm{Tr}_M( y ) \peq
\{ \lp p , q \rp \in Q \times Q
\mid \text{существует путь из }p \text{ в } q \text{ с меткой } y \} .$$
Легко проверить, что если $$\mathrm{Tr}_M( y_1 ) = \mathrm{Tr}_M( y_2 )$$,
то $$\bothcontext_{L} ( y_1 ) \peq \bothcontext_{L} ( y_2 )$$.
Следовательно, $$| \SM ( L ) | \leq 2^{n^2}$$,
где n = |Q|.
Пример 6.3.12.
Рассмотрим конечный автомат M
из примера 2.1.14.
Тогда
Лемма 6.3.13. Пусть $$L \subseteq \Sigma ^*$$, $$n \in \mathbb{N}$$ и для каждого слова $$y \in \Sigma ^*$$
длины n найдется такое слово $$x \in \Sigma ^*$$, что $$| x | < n$$ и $$\bothcontext_{L} ( x ) = \bothcontext_{L} ( y )$$. Тогда$$\SM ( L ) =
\{ \bothcontext_{L} ( y ) \mid y \in \Sigma ^* \commaand | y | < n \} .$$
Доказательство.
Индукцией по $$k \geq n$$
можно доказать, что
для каждого слова $$y \in \Sigma ^*$$
длины k
найдется такое слово $$x \in \Sigma ^*$$,
что $$| x | < n$$
и $$\bothcontext_{L} ( x ) = \bothcontext_{L} ( y )$$.
В
Упражнение 6.3.14. Сколько элементов в синтаксическом a+b над алфавитом {a,b}?
Упражнение 6.3.15. Сколько элементов в синтаксическом b+a+ над алфавитом {a,b}?
Упражнение 6.3.16. Сколько элементов в синтаксическом (aa+b)* над алфавитом {a,b}?
Упражнение 6.3.17. Сколько элементов в синтаксическом (ab)*(ba)*+a* над алфавитом {a,b}?
Упражнение 6.3.18. Сколько элементов в синтаксическом a(b+c)*a(a+b+c)*+b(a+c)*b(a+b+c)*+c(a+b)*c(a+b+c)*
над алфавитом {a,b,c}?
Лемма 6.4.1. Пусть $$L \subseteq \Sigma ^*$$ и $$y \in \Sigma ^*$$. Тогда$$\begin{align*} \rightcontext_{\Sigma ^* \sminus L} ( y ) = \Sigma ^* \sminus \rightcontext_{L} ( y ) ,\\ \bothcontext_{\Sigma ^* \sminus L} ( y ) = (\Sigma ^* \times \Sigma ^*) \sminus \bothcontext_{L} ( y ) . \end{align*}$$
Определение 6.4.2. Пусть $$L \subseteq \Sigma ^*$$ и $$x \in \Sigma ^*$$. Обозначим через $$[ x ]\supright_{L}$$ язык $$\{ y \in \Sigma ^* \mid \rightcontext_{L} ( y ) = \rightcontext_{L} ( x ) \}$$. Обозначим через $$[ x ]_{L}$$ язык $$\{ y \in \Sigma ^* \mid \bothcontext_{L} ( y ) = \bothcontext_{L} ( x ) \}$$.
Пример 6.4.3. Пусть $$L \subseteq \Sigma ^*$$. Множества вида $$[ x ]\supright_{L}$$ образуют разбиение множества $$\Sigma ^*$$ на классы эквивалентности. Множества вида $$[ x ]_{L}$$ образуют разбиение множества $$\Sigma ^*$$ на классы эквивалентности.
Пример 6.4.4. Пусть $$\Sigma = \{ a , b \}$$ и $$L = \{ a^n b a^n \mid n \geq 0 \}$$. Тогда$$\begin{align*} [baa]\supright_{L} = \{ a^i b a^j \mid 0 \leq i < j \} \cup \{ y \in \Sigma ^* \mid | y |_b > 1 \} ,\\ [baa]_{L} = \{ a^i b a^{i+2} \mid i \geq 0 \} . \end{align*}$$
Лемма 6.4.5. Если язык $$L \subseteq \Sigma ^*$$ является автоматным, то для каждого слова $$x \in \Sigma ^*$$ языки $$[ x ]\supright_{L}$$ и $$[ x ]_{L}$$ являются автоматными.
Доказательство.
Пусть язык L
распознается конечным автоматом $$M = \lalg Q , \Sigma , \Delta , I , F \ralg$$,
не содержащим переходов с метками длины больше единицы.
Будем использовать обозначение TrM
из доказательства теоремы 6.3.11.
При любой фиксированной паре $$\lp p , q \rp \in Q \times Q$$
язык $$\cala _{ p , q , M } =
\{ y \in \Sigma ^* \mid \lp p , q \rp \in \mathrm{Tr}_M( y ) \}$$
является автоматным
(он распознается конечным автоматом $$\lalg Q , \Sigma , \Delta , \{ p \} , \{ q \} \ralg$$ ).
Для каждого слова $$z \in \Sigma ^*$$
язык $$\calb _{ z , M } =
\{ y \in \Sigma ^* \mid \mathrm{Tr}_M( y ) = \mathrm{Tr}_M( z ) \}$$
является автоматным, так как он
представим в виде пересечения конечного семейства автоматных языков:$$\calb _{ z , M } =
\biggl(\,
\raisebox{0pt}[\height][0.95\depth]{\displaystyle
\bigcap _{ \lp p , q \rp \in \mathrm{Tr}_M( z ) }}
\cala _{ p , q , M } \biggr)
\cap
\biggl(\,
\raisebox{0pt}[\height][0.95\depth]{\displaystyle
\bigcap _{ \lp p , q \rp \notin \mathrm{Tr}_M( z ) }}
( \Sigma ^* \sminus \cala _{ p , q , M } )\biggr) .$$
Каждый из языков [x]L
и $$[ x ]\supright_{L}$$
является объединением конечного семейства автоматных языков:$$\raisebox{0pt}[\height][0pt]{\displaystyle
[ x ]_{L} = \bigcup _{ z \in [ x ]_{L} } \calb _{ z , M }} ,
\qquad
\raisebox{0pt}[\height][0pt]{\displaystyle
[ x ]\supright_{L} =
\bigcup _{ z \in [ x ]\supright_{L} } \calb _{ z , M }} .$$
Замечание 6.4.6.
Из теоремы 6.1.8
вытекает, что если язык L
автоматный, то существует лишь конечное число
различных множеств $$[ x ]\supright_{L}$$.
Аналогичное утверждение верно для множеств $$[ x ]_{L}$$
(см. теорему 6.3.11).
Пример 6.4.7. Рассмотрим язык$$L = \{ (ab)^n \mid n \geq 0 \} \cup \{ (ab)^n a \mid n \geq 0 \}$$ над алфавитом $$\Sigma = \{ a , b \}$$. Тогда$$\begin{align*} [ \varepsilon ]\supright_{L} = (ab)^* ;\\ [ a ]\supright_{L} = (ab)^* a ;\\ [ b ]\supright_{L} = b (a \replus b)^* \replus (a \replus b)^* (aa \replus bb) (a \replus b)^* ;\\ [ \varepsilon ]_{L} = 1 ;\\ [ ab ]_{L} = (ab)^+ ;\\ [ ba ]_{L} = (ba)^+ ;\\ [ a ]_{L} = (ab)^* a ;\\ [ b ]_{L} = b (ab)^* ;\\ [ aa ]_{L} = (a \replus b)^* (aa \replus bb) (a \replus b)^* . \end{align*}$$
Упражнение 6.4.8.
Существуют ли такие языки $$L_1 \subseteq \Sigma ^*$$
и $$L_2 \subseteq \Sigma ^*$$,
что язык L1
является автоматным, но язык$$L_3 = \{ x \in \Sigma ^* \mid
x y \in L_1 \mathspace\text{для некоторого слова}\mathspace y \in L_2 \}$$
не является автоматным?
Упражнение 6.4.9.
Существуют ли такие языки $$L_1 \subseteq \Sigma ^*$$
и $$L_2 \subseteq \Sigma ^*$$,
что язык L1
является автоматным, но язык$$L_3 = \{ x \in \Sigma ^* \mid
x y \in L_1 \mathspace\text{для всех слов}\mathspace y \in L_2 \}$$
не является автоматным?
Упражнение 6.4.10. Существует ли такой автоматный язык $$L \subseteq \Sigma ^*$$, что язык$$\mathrm{Max} ( L ) \bydef \{ x \in L \mid x y \notin L \mathspace\text{для всех слов}\mathspace y \in \Sigma ^+ \}$$ не является автоматным?
Теорема 6.4.11. Язык $$L \subseteq \Sigma ^*$$ является автоматным тогда и только тогда, когда
существует такое отношение эквивалентности $$R \subseteq \Sigma ^* \times \Sigma ^*$$,
что R разбивает $$\Sigma ^*$$
на конечное множество классов эквивалентности, L является объединением некоторых из этих классов эквивалентности
и для любых $$x \in \Sigma ^*$$, $$y \in \Sigma ^*$$, $$z \in \Sigma ^*$$
из xRy следует xzRyz.
Замечание 6.4.12. Теоремы 6.1.8 и 6.4.11 образуют теорему Майхилла-Нерода.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.