211
правок
Изменения
м
Нет описания правки
{{Лемма
|statement=
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L^R(y) \mid y \in \sum^*\}</tex> его правых контекстов конечно.
|proof=
<tex>\Leftarrow</tex>:<br />Пусть множество правых контекстов языка конечно. Тогда построим Построим распознающий его автомат. Состояния автомата будут соответствовать различным правым контекстам. Переход по некоторому символу из одного состояния в другое строится, если контекст, соответствующий первому состоянию, содержит элементы, которые получаются приписыванием этого символа в начало элементам контекста, соответствующего второму.<br /><tex>\Rightarrow</tex>:Пусть <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>, эквивалентны. Таким образом, можно установить взаимное соответствие между правыми контекстами и классами эквивалентности вершин автомата, которых конечное число.
}}
{{Лемма
|statement=
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L^L(y) \mid y \in \sum^*\}</tex> его левых контекстов конечно.
|proof=
Поскольку множество регулярных языков замкнуто относительно операции разворота, то из того, что <tex>C_L^L(y) = \overleftarrow{C_{\overleftarrow{L}}^R(\overleftarrow{y})}</tex> и аналогичного утверждения о правых контекстах получаем требуемое.
{{Теорема
|statement=
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L(y) \mid y \in \sum^*\}</tex> его двухсторонних контекстов конечно.
|proof=
<tex>\Leftarrow</tex>:
<br />Если множество двухсторонних контекстов языка конечно, то конечно и множество его правых контекстов, а это значит, что язык регулярный.
<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>.
}}
{{Определение
|definition=
'''Синтаксическим моноидом''' языка <tex>L</tex> называется множество его двухсторонних контекстов с введенной на нем операцией конкатенации <tex>\circ</tex>, где <tex>C_L(y) \circ C_L(z) = C_L(yz)</tex>. Нейтральным элементом в нем нём является <tex>C_L(\varepsilon)</tex>
}}
Размер синтаксического моноида является мерой структурной сложности языка. Заметим, что если язык распознается автоматом из <tex>n</tex> состояний, размер его синтаксического моноида не превосходит <tex>n^n</tex>.
