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

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

Версия 03:46, 8 декабря 2011

Контексты

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

Определение:
Правым контекстом [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 \sum^*\}[/math] его правых контекстов конечно.
Доказательство:
[math]\triangleright[/math]

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

Пусть [math]L[/math] — регулярный. Тогда существует автомат [math]A[/math], распознающий его. Рассмотрим произвольное слово [math]y[/math]. Пусть [math]u[/math] — состояние [math]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^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 \sum^*\}[/math] его левых контекстов конечно.
Доказательство:
[math]\triangleright[/math]
Поскольку множество регулярных языков замкнуто относительно операции разворота, то из того, что [math]C_L^L(y) = \overleftarrow{C_{\overleftarrow{L}}^R(\overleftarrow{y})}[/math] и аналогичного утверждения о правых контекстах получаем требуемое.
[math]\triangleleft[/math]

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

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


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

[math]\Leftarrow[/math]
Если множество двухсторонних контекстов языка конечно, то конечно и множество его правых контекстов, а это значит, что язык регулярный.
[math]\Rightarrow[/math]

Пусть [math]L[/math] — регулярный. Тогда существует автомат [math]A[/math], распознающий его. Рассмотрим произвольное слово [math]y[/math]. Пусть [math]\langle i,y \rangle \vdash^* \langle u_i(y), \varepsilon \rangle, i = 1,2,\ldots,n[/math] ([math]n[/math] — число состояний [math]A[/math]). Если для какого-то слова [math]z[/math] выполняется [math]u_i(y) = u_i(z), i = 1,2,\ldots,n[/math], то [math]C_L(y) = C_L(z)[/math]. Наоборот, если [math]C_L(y) = C_L(z)[/math], то [math]u_i(y) \sim u_i(z), i = 1,2,\ldots,n[/math]. Таким образом, можно установить взаимное соответствие между двухсторонними контекстами и классами эквивалентности наборов [math]u_i[/math], которых конечное число, поскольку каждое число [math]u_i[/math] принимает значения от [math]1[/math] до [math]n[/math].
[math]\triangleleft[/math]

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

Определение:
Синтаксическим моноидом языка [math]L[/math] называется множество его двухсторонних контекстов с введенной на нем операцией конкатенации [math]\circ[/math], где [math]C_L(y) \circ C_L(z) = C_L(yz)[/math]. Нейтральным элементом в нём является [math]C_L(\varepsilon)[/math]

Размер синтаксического моноида является мерой структурной сложности языка. Заметим, что если язык распознается автоматом из [math]n[/math] состояний, размер его синтаксического моноида не превосходит [math]n^n[/math].