Контексты и синтаксические моноиды — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Примеры)
м (rollbackEdits.php mass rollback)
 
(не показано 60 промежуточных версий 5 участников)
Строка 10: Строка 10:
 
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L^R(y) \mid y \in \Sigma^*\}</tex> его правых контекстов конечно.
 
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L^R(y) \mid y \in \Sigma^*\}</tex> его правых контекстов конечно.
 
|proof=
 
|proof=
 +
[[Файл:Автомат и правые контексты 1.png|315px|thumb|right|Автомат на правых контекстах. Легенда: <font color=orchit>начальное</font> / <font color=orange>промежуточное</font> / <font color=red>дьявольское</font> / <font color=yelloworange>терминальное</font> состояния; <font color=grey>контекст</font>]]
 
<tex>\Leftarrow</tex>
 
<tex>\Leftarrow</tex>
<br/>
+
 
Пусть множество правых контекстов языка конечно. Построим распознающий его автомат. Состояния автомата будут соответствовать различным правым контекстам. Таким образом, каждая вершина автомата соответствует множеству допустимых «продолжений» считанного на данный момент слова. Переход по некоторому символу из одного состояния в другое осуществляется, если контекст, соответствующий первому состоянию, содержит все элементы, которые получаются приписыванием этого символа в начало элементам контекста, соответствующего второму. Вершина, соответствующая контексту пустого слова, является стартовой (<tex>C_L^R(\varepsilon) = L</tex>). Вершины, контексты которых содержат <tex>\varepsilon</tex>, должны быть допускающими.
+
:Пусть множество правых контекстов языка конечно. Построим распознающий его автомат. Состояния автомата будут соответствовать различным правым контекстам. Таким образом, каждая вершина автомата соответствует множеству допустимых «продолжений» считанного на данный момент слова. Переход по некоторому символу из одного состояния в другое осуществляется, если контекст, соответствующий первому состоянию, содержит все элементы, которые получаются приписыванием этого символа в начало элементам контекста, соответствующего второму. Вершина, соответствующая контексту пустого слова, является стартовой <tex>\left( C_L^R(\varepsilon) = L \right)</tex>. Вершины, контексты которых содержат <tex>\varepsilon</tex>, должны быть допускающими.
 +
 
 +
:Покажем что полученный автомат допускает в точности указанный язык. Выпишем свойства, которые мы стремились удовлетворить при построении:
 +
:: 1. <tex> u \quad \leftrightarrow \quad C_L^R(x) ,\ v \quad \leftrightarrow \quad C_L^R(xc) \quad \leftrightarrow \quad \langle u,c \rangle \vdash \langle v, \varepsilon \rangle </tex>
 +
:: 2. <tex> s \quad \leftrightarrow \quad C_L^R(\varepsilon), </tex> где <tex> s </tex> {{---}} стартовое состояние.
 +
:: 3. <tex> \varepsilon \in C_L^R(\omega) \quad \Leftrightarrow \quad v \in T \quad ( v \quad \leftrightarrow \quad C_L^R(\omega) ) </tex>
 +
:Из 1 следует
 +
:: 1*. <tex> u \quad \leftrightarrow \quad C_L^R(x) ,\ v \quad \leftrightarrow \quad C_L^R(x \omega) \quad \Leftrightarrow \quad \langle u,\omega \rangle \vdash^* \langle v, \varepsilon \rangle </tex>
 +
:Положив <tex> s = u </tex> и учтя 2, получим
 +
:: <tex> v \quad \leftrightarrow \quad C_L^R(\omega) \quad \Leftrightarrow \quad \langle s,\omega \rangle \vdash^* \langle v, \varepsilon \rangle </tex>
 +
:Теперь зафиксируем за состоянием <tex> v </tex> контекст <tex> C_L^R(\omega) </tex>. Тогда левая часть 3 равносильна <tex> \omega \in L </tex>, а правая, с учётом <tex> \langle s,\omega \rangle \vdash^* \langle v, \varepsilon \rangle </tex>, означает, что автомат допускает <tex> \omega </tex>.
  
 
<tex>\Rightarrow</tex>
 
<tex>\Rightarrow</tex>
 
<br/>
 
<br/>
Пусть <tex>L</tex> {{---}} регулярный. Тогда существует автомат <tex>A</tex>, распознающий его. Рассмотрим произвольное слово <tex>y</tex>. Пусть <tex>u</tex> {{---}} состояние <tex>A</tex>, в которое можно перейти из начального по слову <tex>y</tex>. Тогда <tex>C_L^R(y)</tex> совпадает с множеством слов, по которым из состояния <tex>u</tex> можно попасть в допускающее. Причем если по какому-то слову <tex>z</tex> тоже можно перейти из начального состояния в <tex>u</tex>, то <tex>C_L^R(y) = C_L^R(z)</tex>. Наоборот, если <tex>C_L^R(y) = C_L^R(z)</tex>, то состояния, в которые можно перейти по словам <tex>y</tex> и <tex>z</tex>, эквивалентны. Таким образом, можно установить взаимное соответствие между правыми контекстами и классами эквивалентности вершин автомата, которых конечное число.
+
 
 +
:Пусть <tex>L</tex> {{---}} регулярный. В таком случае существует автомат <tex>\mathcal{A}</tex>, распознающий его.  
 +
:Рассмотрим произвольное слово <tex>y</tex>. Положим <tex>u</tex> {{---}} такое состояние <tex>\mathcal{A}</tex>, в которое можно перейти из начального по слову <tex>y</tex>. Тогда <tex>C_L^R(y)</tex> совпадает с множеством слов, по которым из состояния <tex>u</tex> можно попасть в допускающее.  
 +
:Причем если по какому-то слову <tex>z</tex> тоже можно перейти из начального состояния в <tex>u</tex>, то <tex>C_L^R(y) = C_L^R(z)</tex>. Наоборот, если <tex>C_L^R(y) = C_L^R(z)</tex>, то состояния, в которые можно перейти по словам <tex>y</tex> и <tex>z</tex>, эквивалентны. Таким образом, можно установить взаимное соответствие между правыми контекстами и классами эквивалентности вершин автомата, которых конечное число.
 
}}
 
}}
  
 
=== Примеры ===  
 
=== Примеры ===  
 
Здесь будем понимать под <tex> C_L^R(X) = Y </tex> не стандартное отображение множества в множество, а <tex> \forall x \in X :\ C_L^R(x) = Y </tex>. Рассмотрим правые контексты следующих языков:
 
Здесь будем понимать под <tex> C_L^R(X) = Y </tex> не стандартное отображение множества в множество, а <tex> \forall x \in X :\ C_L^R(x) = Y </tex>. Рассмотрим правые контексты следующих языков:
# Язык слов над бинарным алфавитом, в которых остаток от деления числа единиц на <tex> 5 </tex> нечётен.
+
[[Файл:Автомат и правые контексты 2.png|500px|thumb|right|Автомат к языку <tex> \{ 001, 111, 100 \} </tex>]]
#: Пусть <tex> P_k = (0^*1)^k0^* </tex> (слова содержащие <tex> k </tex> единиц). Рассмотрим возможные правые контексты.
+
==== Пример 1 ====
#::0. <tex> C_L^R(P_5^*) = (P_1 | P_3) P_5^* </tex>  
+
<tex> \{ 001, 111, 100 \} </tex>
#::1. <tex> C_L^R(P_1P_5^*) = (\varepsilon | P_2) P_5^* </tex>  
+
: Возникающие контексты:
#::2. <tex> C_L^R(P_2P_5^*) = (P_4 | P_1) P_5^* </tex>  
+
:: <tex>a) C_L^R(\varepsilon) = \{ 001, 111, 100 \} </tex> <br><br />
#::3. <tex> C_L^R(P_3P_5^*) = (P_3 | \varepsilon) P_5^* </tex>  
+
:: <tex>b) C_L^R(0) = \{ 01 \} </tex> <br><br />
#::4. <tex> C_L^R(P_4P_5^*) = (P_2 | P_4) P_5^* </tex>  
+
:: <tex>c) C_L^R(00) = \{ 1 \} </tex> <br><br />
#: Таким образом, автомат построенный на правых контекстах будет содержать 5 состояний.
+
:: <tex>d) C_L^R(001) = \{ \varepsilon \} </tex> <br><br />
#: <tex> C_L^R(\varepsilon) </tex> было рассмотрено в пункте 0 (это начальное состояние).
+
:: <tex>e) C_L^R(1) = \{ 11, 00 \} </tex> <br><br />
#: <tex> \varepsilon \in C_L^R(X) </tex> в пунктах 1 и 3 (это терминальные состояния).
+
:: <tex>f) C_L^R(10) = \{ 0 \} </tex> <br><br />
#: При подаче автомату нуля номер текущего состояния не меняется (если у любого правого контекста отрезать слева <tex> 0 </tex>, он не изменится); при подаче единицы номер текущего состояния увеличивается на <tex> 1 </tex> по модулю <tex> 5 </tex> (правый контекст укорачивается на одну единицу).
+
:: <tex>g) C_L^R(100) = \{ \varepsilon \} </tex> <br><br />
# <tex> 0^*11 </tex>
+
:: <tex>h) C_L^R(11) = \{ 1 \} </tex>  <br><br />
#: Возможные правые контексты (аргументы упорядочены в лексикографическом порядке):
+
:: <tex>j) C_L^R(111) = \{ \varepsilon \} </tex> <br><br />
#:# <tex> C_L^R(0^*) = 0^*(\varepsilon | 1 | 11) </tex>  
+
:: <tex>k) C_L^R(X) = \varnothing </tex>, где <tex> X </tex> {{---}} множество остальных аргументов. <br><br />
#:# <tex> C_L^R(0^*1) = 1 </tex>  
+
: Начальное состояние {{---}} <tex>a</tex> . Допускающие состояния: <tex>d, g, j</tex> (в них <tex> \varepsilon \in C_L^R(\ldots) </tex>). Состояние <tex>k</tex> {{---}} [[Детерминированные_конечные_автоматы#допускает|дьявольское]]. Всего 8 состояний (именно столько имеется различных контекстов).
#:# <tex> C_L^R(0^*10(0|1)^*) = \varnothing </tex>  
+
:[[Файл:Автомат и правые контексты 3.png|350px|thumb|right|Автомат к языку <tex> 0^*11 </tex>]]
#:# <tex> C_L^R(0^*11) = \varepsilon </tex>
+
==== Пример 2  ====
#:# <tex> C_L^R(0^*11(0|1)^+) = \varnothing </tex>
+
<tex> 0^*11 </tex>
#: Итого 4 состояния; начальное состояние 1, допускающее 4, состояние 3&5 {{---}} [[Детерминированные_конечные_автоматы#допускает|тупиковое]].
+
: Возможные контексты (аргументы упорядочены в лексикографическом порядке):
 +
:: <tex>a) C_L^R(0^*) = 0^*11 </tex> <br><br />
 +
:: <tex>b) C_L^R(0^*1) = 1 </tex> <br><br />
 +
:: <tex>c) C_L^R(0^*10(0|1)^*) = \varnothing </tex> <br><br />
 +
:: <tex>d) C_L^R(0^*11) = \varepsilon </tex> <br><br />
 +
:: <tex>e) C_L^R(0^*11(0|1)^+) = \varnothing </tex> <br><br />
 +
: Итого 4 состояния; начальное состояние <tex>a</tex>, допускающее <tex>d</tex>, состояние <tex>c</tex>&<tex>e</tex> {{---}} дьявольское.
  
 
=== Левый контекст ===
 
=== Левый контекст ===
Строка 59: Строка 79:
 
'''Двухсторонним контекстом''' (англ. ''two-sided context'') <tex>C_L(y)</tex> слова <tex>y</tex> в языке <tex>L</tex> называется множество <tex>\{\langle x,z\rangle \mid xyz \in L\}</tex>.
 
'''Двухсторонним контекстом''' (англ. ''two-sided context'') <tex>C_L(y)</tex> слова <tex>y</tex> в языке <tex>L</tex> называется множество <tex>\{\langle x,z\rangle \mid xyz \in L\}</tex>.
 
}}
 
}}
Заметим, что <tex>C_L(\varepsilon)</tex> состоит из всех пар строк, которые при конкатенации дают слово из языка.
+
'''Любопытное замечание:''' <tex>C_L(\varepsilon)</tex> состоит из всех пар строк, которые при конкатенации дают слово из языка.
 +
 
 +
 
 +
Для доказательства последующих утверждений будем использовать бинарное отображение <tex> (\cdot) :\ Q \times \Sigma^* \rightarrow Q </tex> со свойством <tex> q \cdot \omega = q' \Leftrightarrow \langle q,\omega \rangle \vdash^* \langle q', \varepsilon \rangle</tex>.
  
 
{{Лемма
 
{{Лемма
Строка 66: Строка 89:
 
|proof=
 
|proof=
 
<tex>\Leftarrow</tex>
 
<tex>\Leftarrow</tex>
<br />Если множество двухсторонних контекстов языка конечно, то конечно и множество его правых контекстов, а это значит, что язык регулярный.
+
:Заметим, что <tex> \{ z \mid \langle \varepsilon, z \rangle \in C_L(y) \} = C_L^R(y) </tex>. Следовательно, если множество двухсторонних контекстов языка конечно, то конечно и множество его правых контекстов, а это значит, что язык регулярный.
 
<br /><tex>\Rightarrow</tex>
 
<br /><tex>\Rightarrow</tex>
Пусть <tex>L</tex> {{---}} регулярный. Тогда существует автомат <tex>A</tex>, распознающий его. Рассмотрим произвольное слово <tex>y</tex>. Пусть <tex>\langle i,y \rangle \vdash^* \langle u_i(y), \varepsilon \rangle, i = 1,2,\ldots,n</tex> (<tex>n</tex> — число состояний <tex>A</tex>). Если для какого-то слова <tex>z</tex> выполняется <tex>u_i(y) = u_i(z), i = 1,2,\ldots,n</tex>, то <tex>C_L(y) = C_L(z)</tex>. Наоборот, если <tex>C_L(y) = C_L(z)</tex>, то <tex>u_i(y) \sim u_i(z), i = 1,2,\ldots,n</tex>. Таким образом, можно установить взаимное соответствие между двухсторонними контекстами и классами эквивалентности наборов <tex>u_i</tex>, которых конечное число, поскольку каждое число <tex>u_i</tex> принимает значения от <tex>1</tex> до <tex>n</tex>.
+
:Пусть <tex>L</tex> {{---}} регулярный. В таком случае существует детерминированный автомат <tex>\mathcal{A}</tex>, распознающий его. Понятно, что для любого слова <tex> xyz </tex>, допускаемого автоматом, существуют <tex> u ,\ v </tex> такие, что <tex> s \cdot x = u ,\ u \cdot y = v ,\ v \cdot z \in T </tex> (где <tex> s </tex> {{---}} начальное состояние).  
 +
:Тогда справедливо равенство <tex> C_L(y) = \bigcup\limits_{(u, v) :\ u \cdot y = v} \{ \langle x, z \rangle \mid s \cdot x = u ,\ v \cdot z \in T \} </tex>. Учитывая <tex> | \{ (u, v) \mid u,v \in Q \} | = |Q|^2 </tex>, получаем <tex> | \{ C_L(y) \mid y \in \Sigma^* \} | \leqslant 2^{|Q|^2} </tex>, то есть множество контекстов конечно.
 
}}
 
}}
  
Строка 75: Строка 99:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Синтаксическим моноидом''' (англ. ''syntactic monoid'') <tex>M(L)</tex> языка <tex>L</tex> называется множество, состоящее из его классов эквивалентности <tex>[[x]] = \{ y \in \Sigma^* \mid C_L(x) = C_L(y) \}</tex>, с введённым на нём операцией конкатенации <tex>\circ</tex>, где <tex>[[x]]\circ[[y]] = [[xy]]</tex>. Нейтральным элементом в нём является <tex>[[\varepsilon]]</tex>.
+
'''Синтаксическим моноидом''' (англ. ''syntactic monoid'') <tex>M(L)</tex> языка <tex>L</tex> называется множество, состоящее из его классов эквивалентности <tex>[[x]] = \{ y \in \Sigma^* \mid C_L(x) = C_L(y) \} \ </tex>, с введённым на нём операцией конкатенации <tex>\circ</tex>, где <tex>[[x]]\circ[[y]] = [[xy]] \ \ </tex>. Нейтральным элементом в нём является <tex>[[\varepsilon]]</tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
Строка 81: Строка 105:
 
'''Групповой язык''' (англ. ''group language'') {{---}} это язык, синтаксический моноид которого является [[Группа|группой]].
 
'''Групповой язык''' (англ. ''group language'') {{---}} это язык, синтаксический моноид которого является [[Группа|группой]].
 
}}
 
}}
 +
 
=== Свойства ===
 
=== Свойства ===
 
Синтаксический моноид <tex>M(L)</tex> определён для любого <tex>L \in \Sigma^*</tex>, однако некоторые свойства языка можно определить по структуре его синтаксического моноида. Размер синтаксического моноида является мерой структурной сложности языка.
 
Синтаксический моноид <tex>M(L)</tex> определён для любого <tex>L \in \Sigma^*</tex>, однако некоторые свойства языка можно определить по структуре его синтаксического моноида. Размер синтаксического моноида является мерой структурной сложности языка.
Строка 94: Строка 119:
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Пусть язык <tex>L</tex> распознается [[Детерминированные конечные автоматы|ДКА]] <tex>A = \langle \Sigma,Q,s,T,\delta  \rangle</tex>. Тогда размер его синтаксического моноида <tex>M(L)</tex> не превосходит <tex>|Q|^{|Q|}</tex>.
+
Пусть язык <tex>L</tex> распознается [[Детерминированные конечные автоматы|ДКА]] <tex>\mathcal{A} = \langle \Sigma,Q,s,T,\delta  \rangle</tex>. Тогда размер его синтаксического моноида <tex>M(L)</tex> не превосходит <tex>|Q|^{|Q|}</tex>.
 
|proof=
 
|proof=
Введём на <tex>\Sigma^*</tex> следующее отношение эквивалентности:
+
Введём следующее отношение эквивалентности на строках:
 
<br/><tex>x \cong y \Leftrightarrow \forall q \in Q: q \cdot x = q \cdot y</tex>
 
<br/><tex>x \cong y \Leftrightarrow \forall q \in Q: q \cdot x = q \cdot y</tex>
<br/>Оценим количество классов, на которые отношение <tex>\cong</tex> разбивает язык <tex>L</tex>. Сопоставим состояниям автомата <tex>A</tex> числа: <tex>\forall q_i \in Q, q_i \leftrightarrow num(q_i) = i</tex>. Каждый класс эквивалентности можно закодировать вектором <tex>a</tex> из <tex>|Q|</tex> чисел, изменяющихся в диапазоне <tex>1..|Q|</tex>. Положим <tex>a[i] = num(q_i \cdot x)</tex> {{---}} номер состояния, в которое попадём, если начнём с состояния <tex>q_i</tex>, и пойдём по строке <tex>x</tex> посимвольно, где <tex>x</tex> {{---}} слово из кодируемого класса эквивалентности. Количество различных векторов данного вида {{---}} <tex>|Q|^{|Q|}</tex>, а количество классов эквивалентности не превосходит этого значения.
+
<br/>Оценим количество классов, на которые отношение <tex>\cong</tex> разбивает язык <tex>L</tex>. Для этого пронумеруем состояния, и каждому слову <tex> \omega</tex> сопоставим вектор <tex> a_{\omega} \in Q^{|Q|} </tex> такой, что <tex> a_{\omega}[i] = q_j \Leftrightarrow q_i \cdot \omega = q_j </tex>. Количество различных таких векторов {{---}} <tex> {|Q|}^{|Q|} </tex><!--- (поскольку <tex> \forall i = 1 \ldots |Q| :\ a[i] = 1 \ldots |Q| </tex>) --->. В то же время неэквивалентным словам соответствуют разные <tex> a </tex>, тогда количество классов эквивалентности также ограничено <tex> {|Q|}^{|Q|} </tex>.
Если <tex>x \cong y</tex> и <tex>uxv \in L</tex>, то <tex>s \cdot (uyv) = ((s \cdot u) \cdot y) \cdot v = ((s \cdot u) \cdot x) \cdot v = s \cdot (uxv) \in T</tex>, то есть <tex>uyv \in L</tex>. Аналогично из <tex>uyv \in L</tex> следует <tex>uxv \in L</tex>. Значит, <tex>x \cong y \Rightarrow [[x]] = [[y]]</tex>. Следовательно, размер синтаксического моноида не превосходит количества классов эквивалентности, порождаемых отношением <tex>\cong</tex>, которое в свою очередь не превосходит <tex>|Q|^{|Q|}</tex>.
+
 
 +
Остаётся показать, что существует взаимно-однозначное соответствие между нашими классами эквивалентности и синтаксическими моноидами. Смотрим:
 +
<br><tex> x \cong y </tex>
 +
<br><tex> \Leftrightarrow </tex>
 +
<br><tex> s \cdot (uxv) = ((s \cdot u) \cdot x) \cdot v = ((s \cdot u) \cdot y) \cdot v = s \cdot (uyv) \ </tex> (пусть <tex> s \cdot u = q </tex> из определения <tex> \cong </tex>, тогда <tex> (s \cdot u) \cdot x = q \cdot x = q' = q \cdot y = (s \cdot u) \cdot y \ </tex>)
 +
<br><tex> \Leftrightarrow </tex>
 +
<br><tex> s \cdot (uxv) \in T \Leftrightarrow s \cdot (uyv) \in T </tex>
 +
<br><tex> \Leftrightarrow </tex>
 +
<br><tex> uxv \in L \Leftrightarrow uyv \in L </tex>
 +
<br><tex> \Leftrightarrow </tex>
 +
<br><tex> [[x]] = [[y]] </tex>
 +
(<tex> s </tex> {{---}} начальное состояние).
 
}}
 
}}
  
Пусть <tex>A = \langle \Sigma,Q,s,T,\delta \rangle</tex> {{---}} [[Детерминированные конечные автоматы|ДКА]]. Каждое слово <tex>\omega \in \Sigma^*</tex> порождает отображение <tex>f_\omega : Q \rightarrow Q</tex>, определённое следующим образом: <tex>f_\omega(q) = q \cdot \omega</tex>.
+
Пусть <tex>\mathcal{A} = \langle \Sigma,Q,s,T,\delta \rangle</tex> {{---}} [[Детерминированные конечные автоматы|ДКА]]. Каждое слово <tex>\omega \in \Sigma^*</tex> порождает отображение <tex>f_\omega : Q \rightarrow Q</tex>, определённое следующим образом: <tex>f_\omega(q) = q \cdot \omega</tex>.
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Моноидом переходов''' (англ. ''transition monoid'') <tex>M(A)</tex> называется множество отображений <tex>f_\omega</tex> с операцией композиции. <tex>f_x \cdot f_y = f_{xy}</tex>. Нейтральным элементом в данном моноиде является отображение <tex>f_\varepsilon</tex>.
+
'''Моноидом переходов''' (англ. ''transition monoid'') <tex>M(\mathcal{A})</tex> называется множество отображений <tex>f_\omega</tex> с операцией композиции. <tex>f_x \cdot f_y = f_{xy}</tex>. Нейтральным элементом в данном моноиде является отображение <tex>f_\varepsilon</tex>.
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Пусть <tex>A = \langle \Sigma,Q,s,T,\delta \rangle</tex> {{---}} минимальный [[Детерминированные конечные автоматы|ДКА]], задающий язык <tex>L</tex>. Тогда <tex>M(A)</tex> и <tex>M(L)</tex> изоморфны.
+
Пусть <tex>\mathcal{A} = \langle \Sigma,Q,s,T,\delta \rangle</tex> {{---}} минимальный [[Детерминированные конечные автоматы|ДКА]], задающий язык <tex>L</tex>. Тогда <tex>M(\mathcal{A})</tex> и <tex>M(L)</tex> изоморфны.
 
|proof=
 
|proof=
Покажем, что <tex>f_x = f_y \Leftrightarrow [[x]] = [[y]]</tex>.
+
Покажем, что <tex>f_x = f_y \quad \Leftrightarrow \quad [[x]] = [[y]]</tex>.
  
 
<tex>\Rightarrow</tex>
 
<tex>\Rightarrow</tex>
 
<br/>
 
<br/>
Данный факт был показан в доказательстве предыдущей леммы, он не требует минимальности автомата.
+
 
 +
:Данный факт был показан в доказательстве предыдущей леммы, он не требует минимальности автомата.
  
 
<tex>\Leftarrow</tex>
 
<tex>\Leftarrow</tex>
 
<br/>
 
<br/>
Пусть <tex>[[x]] = [[y]]</tex> и <tex>q \in Q</tex>. Тогда <tex>q = s \cdot u</tex> для некоторого слова <tex>u</tex>. Пусть <tex>q_1 = f_x(q) = s \cdot ux</tex> и <tex>q_2 = f_y(q) = s \cdot uy</tex>. Поскольку <tex>[[x]] = [[y]]</tex>, справедливо <tex>uxv \in L \Leftrightarrow uyv \in L</tex>. Следовательно, <tex>q_1 \cdot v \in T \Leftrightarrow q_2 \cdot v \in T</tex>, то есть <tex>q_1</tex> и <tex>q_2</tex> эквивалентны. Значит, <tex>q_1 = q_2</tex>, так как автомат <tex>A</tex> минимален. То есть, <tex>f_x = f_y</tex>.
+
 
 +
:Пусть <tex>[[x]] = [[y]] \ </tex> и <tex>q \in Q</tex>. Тогда <tex>q = s \cdot u</tex> для некоторого слова <tex>u</tex>. Пусть <tex>q_1 = f_x(q) = s \cdot ux</tex> и <tex>q_2 = f_y(q) = s \cdot uy</tex>. Поскольку <tex>[[x]] = [[y]]</tex>, справедливо <tex>uxv \in L \quad \Leftrightarrow \quad uyv \in L</tex>. Следовательно, <tex>q_1 \cdot v \in T \Leftrightarrow q_2 \cdot v \in T</tex>, то есть <tex>q_1</tex> и <tex>q_2</tex> эквивалентны. Значит, <tex>q_1 = q_2</tex>, так как автомат <tex>\mathcal{A}</tex> минимален. То есть, <tex>f_x = f_y</tex>.
 
}}
 
}}
  
 
=== Примеры ===
 
=== Примеры ===
'''1'''. Рассмотрим язык <tex>L = \{\omega \mid |\omega|</tex> <tex>mod</tex> <tex>2 = 0 \}</tex>.
+
====Язык слов четной длины====
 +
Рассмотрим язык <tex>L = \{\omega \mid |\omega| \bmod 2 = 0 \}</tex>.
 +
 
 +
<tex>\{\langle u, v \rangle \mid uxv \in L\}</tex> {{---}} это множество всех пар <tex>\langle u,v \rangle</tex>, таких что <tex>|u| + |v| = |x| \ (\mathrm{mod} \ 2 )</tex>.
 +
 
 +
Значит, <tex>M(L)</tex> состоит из двух элементов: множества слов чётной длины и множества слов нечётной длины. Нейтральным элементом в данном моноиде является множество слов чётной длины.
 +
 
 +
Оба элемента являются обратными самим себе, значит <tex>M(L)</tex> является группой, следовательно <tex>L</tex> {{---}} групповой язык.
 +
 
 +
====Язык над алфавитом из 0 и 1, заданный регулярным выражением 1(0|1)*====
 +
Язык <tex>L</tex> над алфавитом <tex>\Sigma = \{0,1\}</tex> задан регулярным выражением <tex>1(0|1)^*</tex>. Его синтаксический моноид <tex>M(L)</tex> содержит три элемента:
  
<tex>\{\langle u, v \rangle \mid uxv \in L\}</tex> {{---}} это множество всех пар <tex>\langle u,v \rangle</tex>, таких что <tex>|u| + |v| = |x|</tex> <tex>(mod</tex> <tex>2)</tex>. Значит, <tex>M(L)</tex> состоит из двух элементов: множества слов чётной длины и множества слов нечётной длины. Нейтральным элементом в данном моноиде является множество слов чётной длины. Оба элемента являются обратными самим себе, значит <tex>M(L)</tex> является группой, следовательно <tex>L</tex> {{---}} групповой язык.
+
:<tex>a)</tex> <tex>[[\varepsilon]] \ </tex> {{---}} нейтральный элемент. Включает в себя только пустую строку.
  
 +
:<tex>b)</tex> <tex>[[0]] \ </tex> содержит все строки, распознаваемые регулярным выражением <tex>0(0|1)^*</tex>. <tex>\forall x \in [[0]]: C_L(x) = \{\langle u, v \rangle \mid u \in L, v \in \Sigma^* \}</tex>.
  
'''2'''. Язык <tex>L</tex> над алфавитом <tex>\Sigma = \{0,1\}</tex> задан регулярным выражением <tex>1(0|1)^*</tex>. Его синтаксический моноид <tex>M(L)</tex> содержит три элемента:
+
:<tex>c)</tex> <tex>[[1]] \ </tex> содержит все строки, принадлежащие языку, то есть, распознаваемые регулярным выражением <tex>1(0|1)^*</tex>. <tex>\forall x \in [[1]]: C_L(x) = C_L(\varepsilon) \cup \{\langle \varepsilon, v \rangle \mid v \in \Sigma^* \}</tex>.
  
<tex>[[\varepsilon]]</tex> {{---}} нейтральный элемент. Включает в себя только пустую строку.
+
Заметим, что <tex>[[0]] \ </tex> и <tex>[[1]] \ </tex> не имеют обратных элементов в данном моноиде, так как нейтральный элемент содержит только пустую строку, а её невозможно получить из непустой с помощью конкатенации. Следовательно <tex>L</tex> не является групповым языком.
  
<tex>[[0]]</tex> содержит все строки, распознаваемые регулярным выражением <tex>0(0|1)^*</tex>. <tex>\forall x \in [[0]]: C_L(x) = \{\langle u, v \rangle \mid u \in L, v \in \Sigma^* \}</tex>.
+
====Язык из последовательных N нулей и N единиц====
 +
Язык <tex>L = 0^n1^n</tex> задан над алфавитом <tex>\Sigma = \{0,1\}</tex>.  
  
<tex>[[1]]</tex> содержит все строки, принадлежащие языку, то есть, распознаваемые регулярным выражением <tex>1(0|1)^*</tex>. <tex>\forall x \in [[1]]: C_L(x) = C_L(\varepsilon) \cup \{\langle \varepsilon, v \rangle \mid v \in \Sigma^* \}</tex>.
+
Балансом слова <tex>|\omega|_b</tex> назовём число, равное разности между количеством нулей и единиц, встречающихся в данном слове. Если слово <tex>\omega = uxv</tex> принадлежит языку <tex>L</tex>, то <tex>|x|_b = -(|u|_b + |v|_b)</tex>. Но <tex>|x|_b</tex> может принимать любое целое значение, при том, что <tex>x</tex> имеет непустой двухсторонний контекст.  
  
Заметим, что <tex>[[0]]</tex> и <tex>[[1]]</tex> не имеют обратных элементов в данном моноиде, так как нейтральный элемент содержит только пустую строку, а её невозможно получить из непустой с помощью конкатенации. Следовательно <tex>L</tex> не является групповым языком.
+
Значит, синтаксический моноид <tex>M(L)</tex> имеет бесконечное количество элементов, что значит, что данный язык не является регулярным.
  
 +
== См. также ==
  
'''3'''. Язык <tex>L = 0^n1^n</tex> задан над алфавитом <tex>\Sigma = \{0,1\}</tex>. Балансом слова <tex>|\omega|_b</tex> назовём число, равное разности между количеством нулей и единиц, встречающихся в данном слове. Если слово <tex>\omega = uxv</tex> принадлежит языку <tex>L</tex>, то <tex>|x|_b = -(|u|_b + |v|_b)</tex>. Но <tex>|x|_b</tex> может принимать любое целое значение, при том, что <tex>x</tex> имеет непустой двухсторонний контекст. Значит, синтаксический моноид <tex>M(L)</tex> имеет бесконечное количество элементов, что значит, что данный язык не является регулярным.
+
* [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчёт числа слов)|Анализ свойств регулярных языков]]
 +
* [[Доказательство нерегулярности языков: лемма о разрастании]]
  
== Ссылки ==
+
== Источники информации ==
  
 
* ''Howard Straubing'' Finite automata, formal logic, and circuit complexity, 1994. ISBN 3-7643-3719-2. {{---}} C. 53.
 
* ''Howard Straubing'' Finite automata, formal logic, and circuit complexity, 1994. ISBN 3-7643-3719-2. {{---}} C. 53.
 
* ''James A. Anderson'' Automata theory with modern applications, 2006. ISBN 0-521-61324-8. {{---}} С. 72.
 
* ''James A. Anderson'' Automata theory with modern applications, 2006. ISBN 0-521-61324-8. {{---}} С. 72.
* [http://en.wikipedia.org/wiki/Syntactic_monoid Syntactic monoid - Wikipedia]
+
* [http://en.wikipedia.org/wiki/Syntactic_monoid Wikipedia {{---}} Syntactic monoid]
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]

Текущая версия на 19:26, 4 сентября 2022

Контексты

Правый контекст

Определение:
Правым контекстом (англ. right context) [math]C_L^R(y)[/math] слова [math]y[/math] в языке [math]L[/math] называется множество [math]\{z \mid yz \in L\}[/math].


Лемма:
Язык [math]L[/math] — регулярный [math]\Leftrightarrow[/math] множество [math]\{C_L^R(y) \mid y \in \Sigma^*\}[/math] его правых контекстов конечно.
Доказательство:
[math]\triangleright[/math]
Автомат на правых контекстах. Легенда: начальное / промежуточное / дьявольское / терминальное состояния; контекст

[math]\Leftarrow[/math]

Пусть множество правых контекстов языка конечно. Построим распознающий его автомат. Состояния автомата будут соответствовать различным правым контекстам. Таким образом, каждая вершина автомата соответствует множеству допустимых «продолжений» считанного на данный момент слова. Переход по некоторому символу из одного состояния в другое осуществляется, если контекст, соответствующий первому состоянию, содержит все элементы, которые получаются приписыванием этого символа в начало элементам контекста, соответствующего второму. Вершина, соответствующая контексту пустого слова, является стартовой [math]\left( C_L^R(\varepsilon) = L \right)[/math]. Вершины, контексты которых содержат [math]\varepsilon[/math], должны быть допускающими.
Покажем что полученный автомат допускает в точности указанный язык. Выпишем свойства, которые мы стремились удовлетворить при построении:
1. [math] u \quad \leftrightarrow \quad C_L^R(x) ,\ v \quad \leftrightarrow \quad C_L^R(xc) \quad \leftrightarrow \quad \langle u,c \rangle \vdash \langle v, \varepsilon \rangle [/math]
2. [math] s \quad \leftrightarrow \quad C_L^R(\varepsilon), [/math] где [math] s [/math] — стартовое состояние.
3. [math] \varepsilon \in C_L^R(\omega) \quad \Leftrightarrow \quad v \in T \quad ( v \quad \leftrightarrow \quad C_L^R(\omega) ) [/math]
Из 1 следует
1*. [math] u \quad \leftrightarrow \quad C_L^R(x) ,\ v \quad \leftrightarrow \quad C_L^R(x \omega) \quad \Leftrightarrow \quad \langle u,\omega \rangle \vdash^* \langle v, \varepsilon \rangle [/math]
Положив [math] s = u [/math] и учтя 2, получим
[math] v \quad \leftrightarrow \quad C_L^R(\omega) \quad \Leftrightarrow \quad \langle s,\omega \rangle \vdash^* \langle v, \varepsilon \rangle [/math]
Теперь зафиксируем за состоянием [math] v [/math] контекст [math] C_L^R(\omega) [/math]. Тогда левая часть 3 равносильна [math] \omega \in L [/math], а правая, с учётом [math] \langle s,\omega \rangle \vdash^* \langle v, \varepsilon \rangle [/math], означает, что автомат допускает [math] \omega [/math].

[math]\Rightarrow[/math]

Пусть [math]L[/math] — регулярный. В таком случае существует автомат [math]\mathcal{A}[/math], распознающий его.
Рассмотрим произвольное слово [math]y[/math]. Положим [math]u[/math] — такое состояние [math]\mathcal{A}[/math], в которое можно перейти из начального по слову [math]y[/math]. Тогда [math]C_L^R(y)[/math] совпадает с множеством слов, по которым из состояния [math]u[/math] можно попасть в допускающее.
Причем если по какому-то слову [math]z[/math] тоже можно перейти из начального состояния в [math]u[/math], то [math]C_L^R(y) = C_L^R(z)[/math]. Наоборот, если [math]C_L^R(y) = C_L^R(z)[/math], то состояния, в которые можно перейти по словам [math]y[/math] и [math]z[/math], эквивалентны. Таким образом, можно установить взаимное соответствие между правыми контекстами и классами эквивалентности вершин автомата, которых конечное число.
[math]\triangleleft[/math]

Примеры

Здесь будем понимать под [math] C_L^R(X) = Y [/math] не стандартное отображение множества в множество, а [math] \forall x \in X :\ C_L^R(x) = Y [/math]. Рассмотрим правые контексты следующих языков:

Автомат к языку [math] \{ 001, 111, 100 \} [/math]

Пример 1

[math] \{ 001, 111, 100 \} [/math]

Возникающие контексты:
[math]a) C_L^R(\varepsilon) = \{ 001, 111, 100 \} [/math]

[math]b) C_L^R(0) = \{ 01 \} [/math]

[math]c) C_L^R(00) = \{ 1 \} [/math]

[math]d) C_L^R(001) = \{ \varepsilon \} [/math]

[math]e) C_L^R(1) = \{ 11, 00 \} [/math]

[math]f) C_L^R(10) = \{ 0 \} [/math]

[math]g) C_L^R(100) = \{ \varepsilon \} [/math]

[math]h) C_L^R(11) = \{ 1 \} [/math]

[math]j) C_L^R(111) = \{ \varepsilon \} [/math]

[math]k) C_L^R(X) = \varnothing [/math], где [math] X [/math] — множество остальных аргументов.

Начальное состояние — [math]a[/math] . Допускающие состояния: [math]d, g, j[/math] (в них [math] \varepsilon \in C_L^R(\ldots) [/math]). Состояние [math]k[/math]дьявольское. Всего 8 состояний (именно столько имеется различных контекстов).
Автомат к языку [math] 0^*11 [/math]

Пример 2

[math] 0^*11 [/math]

Возможные контексты (аргументы упорядочены в лексикографическом порядке):
[math]a) C_L^R(0^*) = 0^*11 [/math]

[math]b) C_L^R(0^*1) = 1 [/math]

[math]c) C_L^R(0^*10(0|1)^*) = \varnothing [/math]

[math]d) C_L^R(0^*11) = \varepsilon [/math]

[math]e) C_L^R(0^*11(0|1)^+) = \varnothing [/math]

Итого 4 состояния; начальное состояние [math]a[/math], допускающее [math]d[/math], состояние [math]c[/math]&[math]e[/math] — дьявольское.

Левый контекст

Определение:
Левым контекстом (англ. left context) [math]C_L^L(y)[/math] слова [math]y[/math] в языке [math]L[/math] называется множество [math]\{z \mid zy \in L\}[/math].


Лемма:
Язык [math]L[/math] — регулярный [math]\Leftrightarrow[/math] множество [math]\{C_L^L(y) \mid y \in \Sigma^*\}[/math] его левых контекстов конечно.
Доказательство:
[math]\triangleright[/math]
Поскольку множество регулярных языков замкнуто относительно операции разворота, то из того, что [math]C_L^L(y) = \overleftarrow{C_{\overleftarrow{L}}^R(\overleftarrow{y})}[/math] и аналогичного утверждения о правых контекстах получаем требуемое.
[math]\triangleleft[/math]

Двухсторонний контекст

Определение:
Двухсторонним контекстом (англ. two-sided context) [math]C_L(y)[/math] слова [math]y[/math] в языке [math]L[/math] называется множество [math]\{\langle x,z\rangle \mid xyz \in L\}[/math].

Любопытное замечание: [math]C_L(\varepsilon)[/math] состоит из всех пар строк, которые при конкатенации дают слово из языка.


Для доказательства последующих утверждений будем использовать бинарное отображение [math] (\cdot) :\ Q \times \Sigma^* \rightarrow Q [/math] со свойством [math] q \cdot \omega = q' \Leftrightarrow \langle q,\omega \rangle \vdash^* \langle q', \varepsilon \rangle[/math].

Лемма:
Язык [math]L[/math] — регулярный [math]\Leftrightarrow[/math] множество [math]\{C_L(y) \mid y \in \Sigma^*\}[/math] его двухсторонних контекстов конечно.
Доказательство:
[math]\triangleright[/math]

[math]\Leftarrow[/math]

Заметим, что [math] \{ z \mid \langle \varepsilon, z \rangle \in C_L(y) \} = C_L^R(y) [/math]. Следовательно, если множество двухсторонних контекстов языка конечно, то конечно и множество его правых контекстов, а это значит, что язык регулярный.


[math]\Rightarrow[/math]

Пусть [math]L[/math] — регулярный. В таком случае существует детерминированный автомат [math]\mathcal{A}[/math], распознающий его. Понятно, что для любого слова [math] xyz [/math], допускаемого автоматом, существуют [math] u ,\ v [/math] такие, что [math] s \cdot x = u ,\ u \cdot y = v ,\ v \cdot z \in T [/math] (где [math] s [/math] — начальное состояние).
Тогда справедливо равенство [math] C_L(y) = \bigcup\limits_{(u, v) :\ u \cdot y = v} \{ \langle x, z \rangle \mid s \cdot x = u ,\ v \cdot z \in T \} [/math]. Учитывая [math] | \{ (u, v) \mid u,v \in Q \} | = |Q|^2 [/math], получаем [math] | \{ C_L(y) \mid y \in \Sigma^* \} | \leqslant 2^{|Q|^2} [/math], то есть множество контекстов конечно.
[math]\triangleleft[/math]

Синтаксический моноид

Определения

Определение:
Синтаксическим моноидом (англ. syntactic monoid) [math]M(L)[/math] языка [math]L[/math] называется множество, состоящее из его классов эквивалентности [math][[x]] = \{ y \in \Sigma^* \mid C_L(x) = C_L(y) \} \ [/math], с введённым на нём операцией конкатенации [math]\circ[/math], где [math][[x]]\circ[[y]] = [[xy]] \ \ [/math]. Нейтральным элементом в нём является [math][[\varepsilon]][/math].


Определение:
Групповой язык (англ. group language) — это язык, синтаксический моноид которого является группой.


Свойства

Синтаксический моноид [math]M(L)[/math] определён для любого [math]L \in \Sigma^*[/math], однако некоторые свойства языка можно определить по структуре его синтаксического моноида. Размер синтаксического моноида является мерой структурной сложности языка.

Теорема:
Язык [math]L[/math] — регулярный [math]\Leftrightarrow[/math] его синтаксический моноид [math]M(L)[/math] конечен.
Доказательство:
[math]\triangleright[/math]

Размер синтаксического моноида [math]M(L)[/math] языка [math]L[/math] равен количеству его различных двухсторонних контекстов [math]C_L[/math]. Применяя лемму, доказанную ранее, получаем:

Язык [math]L[/math] — регулярный [math]\Leftrightarrow[/math] множество [math]\{C_L(y) \mid y \in \Sigma^*\}[/math] его двухсторонних контекстов конечно [math]\Leftrightarrow[/math] его синтаксический моноид [math]M(L)[/math] конечен.
[math]\triangleleft[/math]
Лемма:
Пусть язык [math]L[/math] распознается ДКА [math]\mathcal{A} = \langle \Sigma,Q,s,T,\delta \rangle[/math]. Тогда размер его синтаксического моноида [math]M(L)[/math] не превосходит [math]|Q|^{|Q|}[/math].
Доказательство:
[math]\triangleright[/math]

Введём следующее отношение эквивалентности на строках:
[math]x \cong y \Leftrightarrow \forall q \in Q: q \cdot x = q \cdot y[/math]
Оценим количество классов, на которые отношение [math]\cong[/math] разбивает язык [math]L[/math]. Для этого пронумеруем состояния, и каждому слову [math] \omega[/math] сопоставим вектор [math] a_{\omega} \in Q^{|Q|} [/math] такой, что [math] a_{\omega}[i] = q_j \Leftrightarrow q_i \cdot \omega = q_j [/math]. Количество различных таких векторов — [math] {|Q|}^{|Q|} [/math]. В то же время неэквивалентным словам соответствуют разные [math] a [/math], тогда количество классов эквивалентности также ограничено [math] {|Q|}^{|Q|} [/math].

Остаётся показать, что существует взаимно-однозначное соответствие между нашими классами эквивалентности и синтаксическими моноидами. Смотрим:
[math] x \cong y [/math]
[math] \Leftrightarrow [/math]
[math] s \cdot (uxv) = ((s \cdot u) \cdot x) \cdot v = ((s \cdot u) \cdot y) \cdot v = s \cdot (uyv) \ [/math] (пусть [math] s \cdot u = q [/math] из определения [math] \cong [/math], тогда [math] (s \cdot u) \cdot x = q \cdot x = q' = q \cdot y = (s \cdot u) \cdot y \ [/math])
[math] \Leftrightarrow [/math]
[math] s \cdot (uxv) \in T \Leftrightarrow s \cdot (uyv) \in T [/math]
[math] \Leftrightarrow [/math]
[math] uxv \in L \Leftrightarrow uyv \in L [/math]
[math] \Leftrightarrow [/math]
[math] [[x]] = [[y]] [/math]

([math] s [/math] — начальное состояние).
[math]\triangleleft[/math]

Пусть [math]\mathcal{A} = \langle \Sigma,Q,s,T,\delta \rangle[/math]ДКА. Каждое слово [math]\omega \in \Sigma^*[/math] порождает отображение [math]f_\omega : Q \rightarrow Q[/math], определённое следующим образом: [math]f_\omega(q) = q \cdot \omega[/math].

Определение:
Моноидом переходов (англ. transition monoid) [math]M(\mathcal{A})[/math] называется множество отображений [math]f_\omega[/math] с операцией композиции. [math]f_x \cdot f_y = f_{xy}[/math]. Нейтральным элементом в данном моноиде является отображение [math]f_\varepsilon[/math].


Теорема:
Пусть [math]\mathcal{A} = \langle \Sigma,Q,s,T,\delta \rangle[/math] — минимальный ДКА, задающий язык [math]L[/math]. Тогда [math]M(\mathcal{A})[/math] и [math]M(L)[/math] изоморфны.
Доказательство:
[math]\triangleright[/math]

Покажем, что [math]f_x = f_y \quad \Leftrightarrow \quad [[x]] = [[y]][/math].

[math]\Rightarrow[/math]

Данный факт был показан в доказательстве предыдущей леммы, он не требует минимальности автомата.

[math]\Leftarrow[/math]

Пусть [math][[x]] = [[y]] \ [/math] и [math]q \in Q[/math]. Тогда [math]q = s \cdot u[/math] для некоторого слова [math]u[/math]. Пусть [math]q_1 = f_x(q) = s \cdot ux[/math] и [math]q_2 = f_y(q) = s \cdot uy[/math]. Поскольку [math][[x]] = [[y]][/math], справедливо [math]uxv \in L \quad \Leftrightarrow \quad uyv \in L[/math]. Следовательно, [math]q_1 \cdot v \in T \Leftrightarrow q_2 \cdot v \in T[/math], то есть [math]q_1[/math] и [math]q_2[/math] эквивалентны. Значит, [math]q_1 = q_2[/math], так как автомат [math]\mathcal{A}[/math] минимален. То есть, [math]f_x = f_y[/math].
[math]\triangleleft[/math]

Примеры

Язык слов четной длины

Рассмотрим язык [math]L = \{\omega \mid |\omega| \bmod 2 = 0 \}[/math].

[math]\{\langle u, v \rangle \mid uxv \in L\}[/math] — это множество всех пар [math]\langle u,v \rangle[/math], таких что [math]|u| + |v| = |x| \ (\mathrm{mod} \ 2 )[/math].

Значит, [math]M(L)[/math] состоит из двух элементов: множества слов чётной длины и множества слов нечётной длины. Нейтральным элементом в данном моноиде является множество слов чётной длины.

Оба элемента являются обратными самим себе, значит [math]M(L)[/math] является группой, следовательно [math]L[/math] — групповой язык.

Язык над алфавитом из 0 и 1, заданный регулярным выражением 1(0|1)*

Язык [math]L[/math] над алфавитом [math]\Sigma = \{0,1\}[/math] задан регулярным выражением [math]1(0|1)^*[/math]. Его синтаксический моноид [math]M(L)[/math] содержит три элемента:

[math]a)[/math] [math][[\varepsilon]] \ [/math] — нейтральный элемент. Включает в себя только пустую строку.
[math]b)[/math] [math][[0]] \ [/math] содержит все строки, распознаваемые регулярным выражением [math]0(0|1)^*[/math]. [math]\forall x \in [[0]]: C_L(x) = \{\langle u, v \rangle \mid u \in L, v \in \Sigma^* \}[/math].
[math]c)[/math] [math][[1]] \ [/math] содержит все строки, принадлежащие языку, то есть, распознаваемые регулярным выражением [math]1(0|1)^*[/math]. [math]\forall x \in [[1]]: C_L(x) = C_L(\varepsilon) \cup \{\langle \varepsilon, v \rangle \mid v \in \Sigma^* \}[/math].

Заметим, что [math][[0]] \ [/math] и [math][[1]] \ [/math] не имеют обратных элементов в данном моноиде, так как нейтральный элемент содержит только пустую строку, а её невозможно получить из непустой с помощью конкатенации. Следовательно [math]L[/math] не является групповым языком.

Язык из последовательных N нулей и N единиц

Язык [math]L = 0^n1^n[/math] задан над алфавитом [math]\Sigma = \{0,1\}[/math].

Балансом слова [math]|\omega|_b[/math] назовём число, равное разности между количеством нулей и единиц, встречающихся в данном слове. Если слово [math]\omega = uxv[/math] принадлежит языку [math]L[/math], то [math]|x|_b = -(|u|_b + |v|_b)[/math]. Но [math]|x|_b[/math] может принимать любое целое значение, при том, что [math]x[/math] имеет непустой двухсторонний контекст.

Значит, синтаксический моноид [math]M(L)[/math] имеет бесконечное количество элементов, что значит, что данный язык не является регулярным.

См. также

Источники информации

  • Howard Straubing Finite automata, formal logic, and circuit complexity, 1994. ISBN 3-7643-3719-2. — C. 53.
  • James A. Anderson Automata theory with modern applications, 2006. ISBN 0-521-61324-8. — С. 72.
  • Wikipedia — Syntactic monoid