http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=Zarubkin&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-28T14:36:37ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%BE%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2%D0%BE_%D0%BD%D0%B5%D1%80%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2:_%D0%BB%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D0%BD%D0%B8%D0%B8&diff=3992Доказательство нерегулярности языков: лемма о разрастании2010-10-14T21:00:31Z<p>Zarubkin: </p>
<hr />
<div>[[Категория: Теория формальных языков]]<br />
{{Лемма<br />
|about=О разрастании<br />
|statement=<br />
Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\Sigma</tex>, тогда существует <tex>n</tex>, такой что для любого слова <tex> \omega \in L</tex>, длины не меньше <tex> n </tex> найдутся слова <tex> x,y,z \in \Sigma^*</tex>, для которых верно <tex>xyz=\omega, y\neq \varepsilon, |xy|\leqslant n</tex> и <tex>xy^{k}z\in L</tex> для всех <tex> k \geqslant 0</tex>.<br />
|proof=<br />
Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\Sigma</tex>, тогда найдётся автомат <tex>A</tex>, допускающий язык <tex>L</tex>. Обозначим размер автомата <tex>A</tex>, как <tex>n</tex>. В языке <tex>L</tex> найдётся слово <tex>\omega</tex> длины не меньше <tex>n</tex>. Рассмотрим переходы в автомате <tex>\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\rangle\vdash\dots\vdash\langle u_{l},\epsilon\rangle, \: l\geqslant n</tex>. Так как <tex>l</tex> не меньше количества состояний в автомате <tex>n</tex>, то в переходах будет совпадение. Пусть <tex>u_i</tex> и <tex>u_j</tex> - первое совпадение. Тогда в нашем слове <tex>\omega</tex> можно размножить кусок, который отвечает за переход, от состояния <tex>u_i</tex> к состоянию <tex>u_j</tex>. <br />
<br />
[[Файл:Regularpicture.jpg]]<br />
<br />
<br />
То есть если верно <tex>\langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>, то тогда верно <tex>\langle s, xy^kz\rangle \vdash^*\langle u_i, y^kz\rangle\vdash^*\langle u_j, y^{k-1}z\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>. Тогда автомат <tex>A</tex> допускает слово <tex>xy^kz</tex>, следовательно <tex>xy^kz</tex> принадлежит регулярному языку <tex>L</tex>. <br />
<br />
}}<br />
<br />
<br />
'''Доказательство нерегулярности языка'''<br />
<br />
Чаще используется отрицание леммы для доказательства нерегулярности языка. Пусть <tex>L</tex> - язык над алфавитом <tex>\Sigma</tex>. Если для любого натурального <tex>n</tex> найдётся такое слово <tex>\omega</tex> из данного языка, что его длина будет не меньше <tex> n</tex> и при любом разбиении на три слова <tex>x,y,z</tex> такие, что <tex> : y</tex> не пустое слово, длина <tex>xy</tex> не больше <tex>n</tex>, есть <tex>k</tex> такое, что <tex>xy^kz \overline\in L</tex>, то язык <tex>L</tex> - не регулярный.<br />
<br />
<br />
'''Пример 1''' Язык правильных скобочных последовательностей не регулярен.<br />
<br />
Пусть дан какой-то <tex>n</tex> для него предъявляем слово <tex>\omega=(^n)^n</tex>. После этого слово <tex>\omega</tex> как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то из-за выбранного слова <tex>y=(^b</tex>, где <tex>b</tex> больше нуля. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит язык правильных скобочных последовательностей не регулярный язык.<br />
<br />
'''Пример 2''' Язык <tex>\{0^a1^a\}_{a\geqslant 0}</tex><br />
<br />
Пусть дан какой-то <tex>n</tex> для него предъявляем слово <tex>\omega=0^n1^n</tex>. После этого слово <tex>\omega</tex> как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то из-за выбранного слова <tex>y=0^b</tex>, где <tex>b</tex> больше нуля. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=0^{n+b}1^n</tex>, что не является элементом множества слов языка <tex>\{0^a1^a\}_{a\geqslant 0}</tex>, значит этот язык не регулярен.</div>Zarubkinhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Regularpicture.jpg&diff=3991Файл:Regularpicture.jpg2010-10-14T20:59:58Z<p>Zarubkin: </p>
<hr />
<div></div>Zarubkinhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%BE%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2%D0%BE_%D0%BD%D0%B5%D1%80%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2:_%D0%BB%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D0%BD%D0%B8%D0%B8&diff=3974Доказательство нерегулярности языков: лемма о разрастании2010-10-14T20:02:54Z<p>Zarubkin: </p>
<hr />
<div>[[Категория: Теория формальных языков]]<br />
{{Лемма<br />
|about=О разрастании<br />
|statement=<br />
Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\Sigma</tex>, тогда существует <tex>n</tex>, такой что для любого слова <tex> \omega \in L</tex>, длины не меньше <tex> n </tex> найдутся слова <tex> x,y,z \in \Sigma^*</tex>, для которых верно <tex>xyz=\omega, y\neq \varepsilon, |xy|\leqslant n</tex> и <tex>xy^{k}z\in L</tex> для всех <tex> k \geqslant 0</tex>.<br />
|proof=<br />
Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\Sigma</tex>, тогда найдётся автомат <tex>A</tex>, допускающий язык <tex>L</tex>. Обозначим размер автомата <tex>A</tex>, как <tex>n</tex>. В языке <tex>L</tex> найдётся слово <tex>\omega</tex> длины не меньше <tex>n</tex>. Рассмотрим переходы в автомате <tex>\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\rangle\vdash\dots\vdash\langle u_{l},\epsilon\rangle, \: l\geqslant n</tex>. Так как <tex>l</tex> не меньше количества состояний в автомате <tex>n</tex>, то в переходах будет совпадение. Пусть <tex>u_i</tex> и <tex>u_j</tex> - первое совпадение. Тогда в нашем слове <tex>\omega</tex> можно размножить кусок, который отвечает за переход, от состояния <tex>u_i</tex> к состоянию <tex>u_j</tex>. <br />
<br />
[[Файл:Regularpumpingpicture.jpg]]<br />
<br />
<br />
То есть если верно <tex>\langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>, то тогда верно <tex>\langle s, xy^kz\rangle \vdash^*\langle u_i, y^kz\rangle\vdash^*\langle u_j, y^{k-1}z\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>. Тогда автомат <tex>A</tex> допускает слово <tex>xy^kz</tex>, следовательно <tex>xy^kz</tex> принадлежит регулярному языку <tex>L</tex>. <br />
<br />
}}<br />
<br />
<br />
'''Доказательство нерегулярности языка'''<br />
<br />
Чаще используется отрицание леммы для доказательства нерегулярности языка. Пусть <tex>L</tex> - язык над алфавитом <tex>\Sigma</tex>. Если для любого натурального <tex>n</tex> найдётся такое слово <tex>\omega</tex> из данного языка, что его длина будет не меньше <tex> n</tex> и при любом разбиении на три слова <tex>x,y,z</tex> такие, что <tex> : y</tex> не пустое слово, длина <tex>xy</tex> не больше <tex>n</tex>, есть <tex>k</tex> такое, что <tex>xy^kz \overline\in L</tex>, то язык <tex>L</tex> - не регулярный.<br />
<br />
<br />
'''Пример 1''' Язык правильных скобочных последовательностей не регулярен.<br />
<br />
Пусть дан какой-то <tex>n</tex> для него предъявляем слово <tex>\omega=(^n)^n</tex>. После этого слово <tex>\omega</tex> как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то из-за выбранного слова <tex>y=(^b</tex>, где <tex>b</tex> больше нуля. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит язык правильных скобочных последовательностей не регулярный язык.<br />
<br />
'''Пример 2''' Язык <tex>\{0^a1^a\}_{a\geqslant 0}</tex><br />
<br />
Пусть дан какой-то <tex>n</tex> для него предъявляем слово <tex>\omega=0^n1^n</tex>. После этого слово <tex>\omega</tex> как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то из-за выбранного слова <tex>y=0^b</tex>, где <tex>b</tex> больше нуля. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=0^{n+b}1^n</tex>, что не является элементом множества слов языка <tex>\{0^a1^a\}_{a\geqslant 0}</tex>, значит этот язык не регулярен.</div>Zarubkinhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Regularpumpingpicture.jpg&diff=3973Файл:Regularpumpingpicture.jpg2010-10-14T20:01:31Z<p>Zarubkin: </p>
<hr />
<div></div>Zarubkinhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Regularpumpingpicture.JPG&diff=3972Файл:Regularpumpingpicture.JPG2010-10-14T19:59:53Z<p>Zarubkin: </p>
<hr />
<div></div>Zarubkinhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D1%80%D0%B5%D1%82%D0%B0%D1%86%D0%B8%D1%8F_%D0%B1%D1%83%D0%BB%D0%B5%D0%B2%D1%8B%D1%85_%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB_%D1%81_%D0%BA%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D1%80%D0%B0%D0%BC%D0%B8_%D0%BA%D0%B0%D0%BA_%D0%B8%D0%B3%D1%80_%D0%B4%D0%BB%D1%8F_%D0%B4%D0%B2%D1%83%D1%85_%D0%B8%D0%B3%D1%80%D0%BE%D0%BA%D0%BE%D0%B2&diff=3237Интерпретация булевых формул с кванторами как игр для двух игроков2010-10-08T00:58:32Z<p>Zarubkin: Новая страница: «'''Интерпретация булевых формул с кванторами как игр для двух игроков''' Рассмотрим формул…»</p>
<hr />
<div>'''Интерпретация булевых формул с кванторами как игр для двух игроков'''<br />
<br />
Рассмотрим формулу <tex>\exists x_1 \forall x_2 \exists x_3 \dots Q x_n = \Psi(x_1,\dots ,x_n)</tex>, где <tex>Q</tex> - квантор зависящий от чётности <tex>n</tex>. Теперь возьмём двух игроков и первый будет ставить <tex>x</tex> с нечётными номерами, а второй с чётными. Если в итоге получается истина, то побеждает первый игрок, если получается ложь, то выигрывает второй. Если <tex>\Psi</tex> истинна, то побеждает второй игрок, в противном случае побеждает первый (при правильных ходах). Пусть <tex>\Psi</tex> истинно, тогда отделим первый квантор. <tex>\exists x_1\Phi(x1)</tex>, тогда по предположению есть такой <tex>x_1</tex>, что <tex>\Phi(x_1)</tex> будет истинно. Верно и для любого с предположением для лжи. В итоге получаем, верное утверждение.</div>Zarubkinhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%BE%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2%D0%BE_%D0%BD%D0%B5%D1%80%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2:_%D0%BB%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D0%BD%D0%B8%D0%B8&diff=3236Доказательство нерегулярности языков: лемма о разрастании2010-10-08T00:58:12Z<p>Zarubkin: </p>
<hr />
<div>[[Категория: Теория формальных языков]]<br />
{{Лемма<br />
|about=О разрастании<br />
|statement=<br />
Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\Sigma</tex>, тогда существует <tex>n</tex>, такой что для любого слова <tex> \omega \in L</tex>, длины не меньше <tex> n </tex> найдутся слова <tex> x,y,z \in \Sigma^*</tex>, для которых верно <tex>xyz=\omega, y\neq \varepsilon, |xy|\leqslant n</tex> и <tex>xy^{k}z\in L</tex> для всех <tex> k \geqslant 0</tex>.<br />
|proof=<br />
Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\Sigma</tex>, тогда найдётся автомат <tex>A</tex>, допускающий язык <tex>L</tex>. Обозначим размер автомата <tex>A</tex>, как <tex>n</tex>. В языке <tex>L</tex> найдётся слово <tex>\omega</tex> длины не меньше <tex>n</tex>. Рассмотрим переходы в автомате <tex>\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\rangle\vdash\dots\vdash\langle u_{l},\epsilon\rangle, \: l\geqslant n</tex>. Так как <tex>l</tex> не меньше количества состояний в автомате <tex>n</tex>, то в переходах будет совпадение. Пусть <tex>u_i</tex> и <tex>u_j</tex> - первое совпадение. Тогда в нашем слове <tex>\omega</tex> можно размножить кусок, который отвечает за переход, от состояния <tex>u_i</tex> к состоянию <tex>u_j</tex>. То есть если верно <tex>\langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>, то тогда верно <tex>\langle s, xy^kz\rangle \vdash^*\langle u_i, y^kz\rangle\vdash^*\langle u_j, y^{k-1}z\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>. Тогда автомат <tex>A</tex> допускает слово <tex>xy^kz</tex>, следовательно <tex>xy^kz</tex> принадлежит регулярному языку <tex>L</tex>. <br />
<br />
"Картинка"<br />
}}<br />
<br />
<br />
'''Доказательство нерегулярности языка'''<br />
<br />
Чаще используется отрицание леммы для доказательства нерегулярности языка. Пусть <tex>L</tex> - язык над алфавитом <tex>\Sigma</tex>. Если для любого натурального <tex>n</tex> найдётся такое слово <tex>\omega</tex> из данного языка, что его длина будет не меньше <tex> n</tex> и при любом разбиении на три слова <tex>x,y,z</tex> такие, что <tex> : y</tex> не пустое слово, длина <tex>xy</tex> не больше <tex>n</tex>, есть <tex>k</tex> такое, что <tex>xy^kz \overline\in L</tex>, то язык <tex>L</tex> - не регулярный.<br />
<br />
<br />
'''Пример 1''' Язык правильных скобочных последовательностей не регулярен.<br />
<br />
Пусть дан какой-то <tex>n</tex> для него предъявляем слово <tex>\omega=(^n)^n</tex>. После этого слово <tex>\omega</tex> как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то из-за выбранного слова <tex>y=(^b</tex>, где <tex>b</tex> больше нуля. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит язык правильных скобочных последовательностей не регулярный язык.<br />
<br />
'''Пример 2''' Язык <tex>\{0^a1^a\}_{a\geqslant 0}</tex><br />
<br />
Пусть дан какой-то <tex>n</tex> для него предъявляем слово <tex>\omega=0^n1^n</tex>. После этого слово <tex>\omega</tex> как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то из-за выбранного слова <tex>y=0^b</tex>, где <tex>b</tex> больше нуля. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=0^{n+b}1^n</tex>, что не является элементом множества слов языка <tex>\{0^a1^a\}_{a\geqslant 0}</tex>, значит этот язык не регулярен.</div>Zarubkinhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%BE%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2%D0%BE_%D0%BD%D0%B5%D1%80%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2:_%D0%BB%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D0%BD%D0%B8%D0%B8&diff=3234Доказательство нерегулярности языков: лемма о разрастании2010-10-08T00:57:19Z<p>Zarubkin: </p>
<hr />
<div>[[Категория: Теория формальных языков]]<br />
{{Лемма<br />
|about=О разрастании<br />
|statement=<br />
Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\Sigma</tex>, тогда существует <tex>n</tex>, такой что для любого слова <tex> \omega \in L</tex>, длины не меньше <tex> n </tex> найдутся слова <tex> x,y,z \in \Sigma^*</tex>, для которых верно <tex>xyz=\omega, y\neq \varepsilon, |xy|\leqslant n</tex> и <tex>xy^{k}z\in L</tex> для всех <tex> k \geqslant 0</tex>.<br />
|proof=<br />
Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\Sigma</tex>, тогда найдётся автомат <tex>A</tex>, допускающий язык <tex>L</tex>. Обозначим размер автомата <tex>A</tex>, как <tex>n</tex>. В языке <tex>L</tex> найдётся слово <tex>\omega</tex> длины не меньше <tex>n</tex>. Рассмотрим переходы в автомате <tex>\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\rangle\vdash\dots\vdash\langle u_{l},\epsilon\rangle, \: l\geqslant n</tex>. Так как <tex>l</tex> не меньше количества состояний в автомате <tex>n</tex>, то в переходах будет совпадение. Пусть <tex>u_i</tex> и <tex>u_j</tex> - первое совпадение. Тогда в нашем слове <tex>\omega</tex> можно размножить кусок, который отвечает за переход, от состояния <tex>u_i</tex> к состоянию <tex>u_j</tex>. То есть если верно <tex>\langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>, то тогда верно <tex>\langle s, xy^kz\rangle \vdash^*\langle u_i, y^kz\rangle\vdash^*\langle u_j, y^{k-1}z\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>. Тогда автомат <tex>A</tex> допускает слово <tex>xy^kz</tex>, следовательно <tex>xy^kz</tex> принадлежит регулярному языку <tex>L</tex>. <br />
<br />
"Картинка"<br />
}}<br />
<br />
<br />
'''Доказательство нерегулярности языка'''<br />
<br />
Чаще используется отрицание леммы для доказательства нерегулярности языка. Пусть <tex>L</tex> - язык над алфавитом <tex>\Sigma</tex>. Если для любого натурального <tex>n</tex> найдётся такое слово <tex>\omega</tex> из данного языка, что его длина будет не меньше <tex> n</tex> и при любом разбиении на три слова <tex>x,y,z</tex> такие, что <tex> : y</tex> не пустое слово, длина <tex>xy</tex> не больше <tex>n</tex>, есть <tex>k</tex> такое, что <tex>xy^kz \overline\in L</tex>, то язык <tex>L</tex> - не регулярный.<br />
<br />
<br />
'''Пример 1''' Язык правильных скобочных последовательностей не регулярен.<br />
<br />
Пусть дан какой-то <tex>n</tex> для него предъявляем слово <tex>\omega=(^n)^n</tex>. После этого слово <tex>\omega</tex> как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то из-за выбранного слова <tex>y=(^b</tex>, где <tex>b</tex> больше нуля. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит язык правильных скобочных последовательностей не регулярный язык.<br />
<br />
'''Пример 2''' Язык <tex>\{0^a1^a\}_{a\geqslant 0}</tex><br />
<br />
Пусть дан какой-то <tex>n</tex> для него предъявляем слово <tex>\omega=0^n1^n</tex>. После этого слово <tex>\omega</tex> как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то из-за выбранного слова <tex>y=0^b</tex>, где <tex>b</tex> больше нуля. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=0^{n+b}1^n</tex>, что не является элементом множества слов языка <tex>\{0^a1^a\}_{a\geqslant 0}</tex>, значит этот язык не регулярен.<br />
<br />
<br />
'''Интерпретация булевых формул с кванторами как игр для двух игроков'''<br />
<br />
Рассмотрим формулу <tex>\exists x_1 \forall x_2 \exists x_3 \dots Q x_n = \Psi(x_1,\dots ,x_n)</tex>, где <tex>Q</tex> - квантор зависящий от чётности <tex>n</tex>. Теперь возьмём двух игроков и первый будет ставить <tex>x</tex> с нечётными номерами, а второй с чётными. Если в итоге получается истина, то побеждает первый игрок, если получается ложь, то выигрывает второй. Если <tex>\Psi</tex> истинна, то побеждает второй игрок, в противном случае побеждает первый (при правильных ходах). Пусть <tex>\Psi</tex> истинно, тогда отделим первый квантор. <tex>\exists x_1\Phi(x1)</tex>, тогда по предположению есть такой <tex>x_1</tex>, что <tex>\Phi(x_1)</tex> будет истинно. Верно и для любого с предположением для лжи. В итоге получаем, верное утверждение.</div>Zarubkinhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%BE%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2%D0%BE_%D0%BD%D0%B5%D1%80%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2:_%D0%BB%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D0%BD%D0%B8%D0%B8&diff=3233Доказательство нерегулярности языков: лемма о разрастании2010-10-08T00:53:32Z<p>Zarubkin: </p>
<hr />
<div>[[Категория: Теория формальных языков]]<br />
{{Лемма<br />
|about=О разрастании<br />
|statement=<br />
Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\Sigma</tex>, тогда существует <tex>n</tex>, такой что для любого слова <tex> \omega \in L</tex>, длины не меньше <tex> n </tex> найдутся слова <tex> x,y,z \in \Sigma^*</tex>, для которых верно <tex>xyz=\omega, y\neq \varepsilon, |xy|\leqslant n</tex> и <tex>xy^{k}z\in L</tex> для всех <tex> k \geqslant 0</tex>.<br />
|proof=<br />
Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\Sigma</tex>, тогда найдётся автомат <tex>A</tex>, допускающий язык <tex>L</tex>. Обозначим размер автомата <tex>A</tex>, как <tex>n</tex>. В языке <tex>L</tex> найдётся слово <tex>\omega</tex> длины не меньше <tex>n</tex>. Рассмотрим переходы в автомате <tex>\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\rangle\vdash\dots\vdash\langle u_{l},\epsilon\rangle, \: l\geqslant n</tex>. Так как <tex>l</tex> не меньше количества состояний в автомате <tex>n</tex>, то в переходах будет совпадение. Пусть <tex>u_i</tex> и <tex>u_j</tex> - первое совпадение. Тогда в нашем слове <tex>\omega</tex> можно размножить кусок, который отвечает за переход, от состояния <tex>u_i</tex> к состоянию <tex>u_j</tex>. То есть если верно <tex>\langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>, то тогда верно <tex>\langle s, xy^kz\rangle \vdash^*\langle u_i, y^kz\rangle\vdash^*\langle u_j, y^{k-1}z\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>. Тогда автомат <tex>A</tex> допускает слово <tex>xy^kz</tex>, следовательно <tex>xy^kz</tex> принадлежит регулярному языку <tex>L</tex>. <br />
<br />
"Картинка"<br />
}}<br />
<br />
<br />
'''Доказательство нерегулярности языка'''<br />
<br />
Чаще используется отрицание леммы для доказательства нерегулярности языка. Пусть <tex>L</tex> - язык над алфавитом <tex>\Sigma</tex>. Если для любого натурального <tex>n</tex> найдётся такое слово <tex>\omega</tex> из данного языка, что его длина будет не меньше <tex> n</tex> и при любом разбиении на три слова <tex>x,y,z</tex> такие, что <tex> : y</tex> не пустое слово, длина <tex>xy</tex> не больше <tex>n</tex>, есть <tex>k</tex> такое, что <tex>xy^kz \overline\in L</tex>, то язык <tex>L</tex> - не регулярный.<br />
<br />
<br />
'''Пример 1''' Язык правильных скобочных последовательностей не регулярен.<br />
<br />
Пусть дан какой-то <tex>n</tex> для него предъявляем слово <tex>\omega=(^n)^n</tex>. После этого слово <ttex>\omega</tex> как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то из-за выбранного слова <tex>y=(^b</tex>, где <tex>b</tex> больше нуля. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит язык правильных скобочных последовательностей не регулярный язык.<br />
<br />
'''Пример 2''' Язык <tex>0^a1^a</tex><br />
Для <tex>\forall n</tex> мы берём <tex>\omega=0^n1^n</tex>. Так как <tex>|xy|\leqslant n</tex>, то <tex>y=0^b</tex>. Берём <tex>k=2</tex> и получаем <tex>xy^kz=0^{n+b}1^n</tex>, что не является элементом нашего языка, значит наш язык не регулярен.<br />
<br />
<br />
'''Интерпретация булевых формул с кванторами как игр для двух игроков'''<br />
<br />
Рассмотрим формулу <tex>\exists x_1 \forall x_2 \exists x_3 \dots Q x_n = \Psi(x_1,\dots ,x_n)</tex>, где <tex>Q</tex> - квантор зависящий от чётности <tex>n</tex>. Теперь возьмём двух игроков и первый будет ставить <tex>x</tex> с нечётными номерами, а второй с чётными. Если в итоге получается истина, то побеждает первый игрок, если получается ложь, то выигрывает второй. Если <tex>\Psi</tex> истинна, то побеждает второй игрок, в противном случае побеждает первый (при правильных ходах). Пусть <tex>\Psi</tex> истинно, тогда отделим первый квантор. <tex>\exists x_1\Phi(x1)</tex>, тогда по предположению есть такой <tex>x_1</tex>, что <tex>\Phi(x_1)</tex> будет истинно. Верно и для любого с предположением для лжи. В итоге получаем, верное утверждение.</div>Zarubkinhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%BE%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2%D0%BE_%D0%BD%D0%B5%D1%80%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2:_%D0%BB%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D0%BD%D0%B8%D0%B8&diff=3232Доказательство нерегулярности языков: лемма о разрастании2010-10-08T00:52:32Z<p>Zarubkin: </p>
<hr />
<div>[[Категория: Теория формальных языков]]<br />
{{Лемма<br />
|about=О разрастании<br />
|statement=<br />
Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\Sigma</tex>, тогда существует <tex>n</tex>, такой что для любого слова <tex> \omega \in L</tex>, длины не меньше <tex> n </tex> найдутся слова <tex> x,y,z \in \Sigma^*</tex>, для которых верно <tex>xyz=\omega, y\neq \varepsilon, |xy|\leqslant n</tex> и <tex>xy^{k}z\in L</tex> для всех <tex> k \geqslant 0</tex>.<br />
|proof=<br />
Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\Sigma</tex>, тогда найдётся автомат <tex>A</tex>, допускающий язык <tex>L</tex>. Обозначим размер автомата <tex>A</tex>, как <tex>n</tex>. В языке <tex>L</tex> найдётся слово <tex>\omega</tex> длины не меньше <tex>n</tex>. Рассмотрим переходы в автомате <tex>\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\rangle\vdash\dots\vdash\langle u_{l},\epsilon\rangle, \: l\geqslant n</tex>. Так как <tex>l</tex> не меньше количества состояний в автомате <tex>n</tex>, то в переходах будет совпадение. Пусть <tex>u_i</tex> и <tex>u_j</tex> - первое совпадение. Тогда в нашем слове <tex>\omega</tex> можно размножить кусок, который отвечает за переход, от состояния <tex>u_i</tex> к состоянию <tex>u_j</tex>. То есть если верно <tex>\langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>, то тогда верно <tex>\langle s, xy^kz\rangle \vdash^*\langle u_i, y^kz\rangle\vdash^*\langle u_j, y^{k-1}z\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>. Тогда автомат <tex>A</tex> допускает слово <tex>xy^kz</tex>, следовательно <tex>xy^kz</tex> принадлежит регулярному языку <tex>L</tex>. <br />
<br />
"Картинка"<br />
}}<br />
<br />
<br />
'''Доказательство нерегулярности языка'''<br />
<br />
Чаще используется отрицание леммы для доказательства нерегулярности языка. Пусть <tex>L</tex> - язык над алфавитом <tex>\Sigma</tex>. Если для любого натурального <tex>n</tex> найдётся такое слово <tex>\omega</tex> из данного языка, что его длина будет не меньше <tex> n</tex> и при любом разбиении на три слова <tex>x,y,z</tex> такие, что <tex> : y</tex> не пустое слово, длина <tex>xy</tex> не больше <tex>n</tex>, есть <tex>k</tex> такое, что <tex>xy^kz \overline\in L</tex>, то язык <tex>L</tex> - не регулярный.<br />
<br />
<br />
'''Пример 1''' Язык правильных скобочных последовательностей не регулярен.<br />
<br />
Пусть дан какой-то <tex>n</tex> для него предъявляем слово <tex>\omega=(^n)^n</tex>. После этого наше слово как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то из-за выбранного слова <tex>y=(^b</tex>, где <tex>b</tex> больше нуля. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит язык правильных скобочных последовательностей не регулярный язык.<br />
<br />
'''Пример 2''' Язык <tex>0^a1^a</tex><br />
Для <tex>\forall n</tex> мы берём <tex>\omega=0^n1^n</tex>. Так как <tex>|xy|\leqslant n</tex>, то <tex>y=0^b</tex>. Берём <tex>k=2</tex> и получаем <tex>xy^kz=0^{n+b}1^n</tex>, что не является элементом нашего языка, значит наш язык не регулярен.<br />
<br />
<br />
'''Интерпретация булевых формул с кванторами как игр для двух игроков'''<br />
<br />
Рассмотрим формулу <tex>\exists x_1 \forall x_2 \exists x_3 \dots Q x_n = \Psi(x_1,\dots ,x_n)</tex>, где <tex>Q</tex> - квантор зависящий от чётности <tex>n</tex>. Теперь возьмём двух игроков и первый будет ставить <tex>x</tex> с нечётными номерами, а второй с чётными. Если в итоге получается истина, то побеждает первый игрок, если получается ложь, то выигрывает второй. Если <tex>\Psi</tex> истинна, то побеждает второй игрок, в противном случае побеждает первый (при правильных ходах). Пусть <tex>\Psi</tex> истинно, тогда отделим первый квантор. <tex>\exists x_1\Phi(x1)</tex>, тогда по предположению есть такой <tex>x_1</tex>, что <tex>\Phi(x_1)</tex> будет истинно. Верно и для любого с предположением для лжи. В итоге получаем, верное утверждение.</div>Zarubkinhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%BE%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2%D0%BE_%D0%BD%D0%B5%D1%80%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2:_%D0%BB%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D0%BD%D0%B8%D0%B8&diff=3231Доказательство нерегулярности языков: лемма о разрастании2010-10-08T00:51:05Z<p>Zarubkin: </p>
<hr />
<div>[[Категория: Теория формальных языков]]<br />
{{Лемма<br />
|about=О разрастании<br />
|statement=<br />
Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\Sigma</tex>, тогда существует <tex>n</tex>, такой что для любого слова <tex> \omega \in L</tex>, длины не меньше <tex> n </tex> найдутся слова <tex> x,y,z \in \Sigma^*</tex>, для которых верно <tex>xyz=\omega, y\neq \varepsilon, |xy|\leqslant n</tex> и <tex>xy^{k}z\in L</tex> для всех <tex> k \geqslant 0</tex>.<br />
|proof=<br />
Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\Sigma</tex>, тогда найдётся автомат <tex>A</tex>, допускающий язык <tex>L</tex>. Обозначим размер автомата <tex>A</tex>, как <tex>n</tex>. В языке <tex>L</tex> найдётся слово <tex>\omega</tex> длины не меньше <tex>n</tex>. Рассмотрим переходы в автомате <tex>\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\rangle\vdash\dots\vdash\langle u_{l},\epsilon\rangle, \: l\geqslant n</tex>. Так как <tex>l</tex> не меньше количества состояний в автомате <tex>n</tex>, то в переходах будет совпадение. Пусть <tex>u_i</tex> и <tex>u_j</tex> - первое совпадение. Тогда в нашем слове <tex>\omega</tex> можно размножить кусок, который отвечает за переход, от состояния <tex>u_i</tex> к состоянию <tex>u_j</tex>. То есть если верно <tex>\langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>, то тогда верно <tex>\langle s, xy^kz\rangle \vdash^*\langle u_i, y^kz\rangle\vdash^*\langle u_j, y^{k-1}z\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \varepsilon\rangle</tex>. Тогда автомат <tex>A</tex> допускает слово <tex>xy^kz</tex>, следовательно <tex>xy^kz</tex> принадлежит регулярному языку <tex>L</tex>. <br />
<br />
"Картинка"<br />
}}<br />
<br />
<br />
'''Доказательство нерегулярности языка'''<br />
<br />
Чаще используется отрицание леммы для доказательства нерегулярности языка. Пусть <tex>L</tex> - язык над алфавитом <tex>\Sigma</tex>. Если для любого натурального <tex>n</tex> найдётся такое слово <tex>\omega</tex> из данного языка, что его длина будет не меньше <tex> n</tex> и при любом разбиении на три слова <tex>x,y,z</tex> такие, что <tex> : y\neq \varepsilon</tex>, длина <tex>xy</tex> не больше <tex>n</tex>, есть <tex>k</tex> такое, что <tex>xy^kz \overline\in L</tex>, то язык <tex>L</tex> - не регулярный.<br />
<br />
<br />
'''Пример 1''' Язык правильных скобочных последовательностей не регулярен.<br />
<br />
Пусть дан какой-то <tex>n</tex> для него предъявляем слово <tex>\omega=(^n)^n</tex>. После этого наше слово как-то разбили на <tex>x, y, z</tex>. Так как <tex>|xy|\leqslant n</tex>, то из-за выбранного слова <tex>y=(^b</tex>, где <tex>b</tex> больше нуля. Для любого такого разбиения берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит язык правильных скобочных последовательностей не регулярный язык.<br />
<br />
'''Пример 2''' Язык <tex>0^a1^a</tex><br />
Для <tex>\forall n</tex> мы берём <tex>\omega=0^n1^n</tex>. Так как <tex>|xy|\leqslant n</tex>, то <tex>y=0^b</tex>. Берём <tex>k=2</tex> и получаем <tex>xy^kz=0^{n+b}1^n</tex>, что не является элементом нашего языка, значит наш язык не регулярен.<br />
<br />
<br />
'''Интерпретация булевых формул с кванторами как игр для двух игроков'''<br />
<br />
Рассмотрим формулу <tex>\exists x_1 \forall x_2 \exists x_3 \dots Q x_n = \Psi(x_1,\dots ,x_n)</tex>, где <tex>Q</tex> - квантор зависящий от чётности <tex>n</tex>. Теперь возьмём двух игроков и первый будет ставить <tex>x</tex> с нечётными номерами, а второй с чётными. Если в итоге получается истина, то побеждает первый игрок, если получается ложь, то выигрывает второй. Если <tex>\Psi</tex> истинна, то побеждает второй игрок, в противном случае побеждает первый (при правильных ходах). Пусть <tex>\Psi</tex> истинно, тогда отделим первый квантор. <tex>\exists x_1\Phi(x1)</tex>, тогда по предположению есть такой <tex>x_1</tex>, что <tex>\Phi(x_1)</tex> будет истинно. Верно и для любого с предположением для лжи. В итоге получаем, верное утверждение.</div>Zarubkinhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%BE%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2%D0%BE_%D0%BD%D0%B5%D1%80%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2:_%D0%BB%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D0%BD%D0%B8%D0%B8&diff=3228Доказательство нерегулярности языков: лемма о разрастании2010-10-08T00:18:49Z<p>Zarubkin: </p>
<hr />
<div>[[Категория: Теория формальных языков]]<br />
{{Лемма<br />
|about=О разрастании<br />
|statement=<br />
Пусть <tex>L</tex> - регулярный язык над алфавитом <tex>\Sigma</tex>, тогда существует <tex>n</tex>, такой что для любого слова <tex> \omega \in L</tex>, длины не меньше <tex> n </tex> найдутся слова <tex> x,y,z \in \Sigma^*</tex>, для которых верно <tex>xyz=\omega, y\neq \varepsilon, |xy|\leqslant n</tex> и <tex>xy^{k}z\in L</tex> для всех <tex> k \geqslant 0</tex>.<br />
|proof=<br />
<tex>L</tex> - регулярный <tex>\Rightarrow</tex> <tex>\exists</tex> автомат <tex>A : \: n=|Q|</tex> допускающий этот язык. Возьмём <tex>\omega\in L : |\omega|\geqslant n</tex> тогда рассмотрим переходы в автомате <tex>\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\dots\vdash\langle u_{l},\epsilon\rangle, \: l\geqslant n</tex>. Так как <tex>l\geqslant n</tex>, то возьмём первое совпадение состояний в автомате <tex>u_i, u_j</tex>. В нашем автомате для <tex>\omega : \: \langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \epsilon\rangle</tex>. Тогда <tex>xy^kz</tex> подходит. <br />
}}<br />
<br />
<br />
Чаще используется отрицание леммы для доказательства нерегулярности языка.<br />
<br />
<br />
'''Пример 1''' Правильная скобочная последовательность. <br />
Для <tex>\forall n</tex> мы берём <tex>\omega=(^n)^n</tex>. Так как <tex>|xy|\leqslant n</tex>, то <tex>y=(^b</tex>. Берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит правильная скобочная последовательность не регулярный язык.<br />
<br />
'''Пример 2''' Язык <tex>0^a1^a</tex><br />
Для <tex>\forall n</tex> мы берём <tex>\omega=0^n1^n</tex>. Так как <tex>|xy|\leqslant n</tex>, то <tex>y=0^b</tex>. Берём <tex>k=2</tex> и получаем <tex>xy^kz=0^{n+b}1^n</tex>, что не является элементом нашего языка, значит наш язык не регулярен.<br />
<br />
<br />
'''Интерпретация булевых формул с кванторами как игр для двух игроков'''<br />
<br />
Рассмотрим формулу <tex>\exists x_1 \forall x_2 \exists x_3 \dots Q x_n = \Psi(x_1,\dots ,x_n)</tex>, где <tex>Q</tex> - квантор зависящий от чётности <tex>n</tex>. Теперь возьмём двух игроков и первый будет ставить <tex>x</tex> с нечётными номерами, а второй с чётными. Если в итоге получается истина, то побеждает первый игрок, если получается ложь, то выигрывает второй. Если <tex>\Psi</tex> истинна, то побеждает второй игрок, в противном случае побеждает первый (при правильных ходах). Пусть <tex>\Psi</tex> истинно, тогда отделим первый квантор. <tex>\exists x_1\Phi(x1)</tex>, тогда по предположению есть такой <tex>x_1</tex>, что <tex>\Phi(x_1)</tex> будет истинно. Верно и для любого с предположением для лжи. В итоге получаем, верное утверждение.</div>Zarubkinhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%BE%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2%D0%BE_%D0%BD%D0%B5%D1%80%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2:_%D0%BB%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D0%BD%D0%B8%D0%B8&diff=3097Доказательство нерегулярности языков: лемма о разрастании2010-10-05T01:47:30Z<p>Zarubkin: </p>
<hr />
<div>[[Категория: Теория формальных языков]]<br />
{{Лемма<br />
|about=О разрастании<br />
|statement=<tex>L</tex> - регулярный <tex>\Rightarrow</tex> <tex>\exists n \:\forall \omega : |\omega| \geqslant n, \omega \in L \: \exists x,y,z : \omega=xyz, y\neq \epsilon, |xy|\leqslant n, \forall k \geqslant 0\: xy^{k}z\in L</tex><br />
|proof=L - регулярный <tex>\Rightarrow</tex> <tex>\exists</tex> автомат <tex>A : \: n=|Q|</tex> допускающий этот язык. Возьмём <tex>\omega\in L : |\omega|\geqslant n</tex> тогда рассмотрим переходы в автомате <tex>\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\dots\vdash\langle u_{l},\epsilon\rangle, \: l\geqslant n</tex>. Так как <tex>l\geqslant n</tex>, то возьмём первое совпадение состояний в автомате <tex>u_i, u_j</tex>. В нашем автомате для <tex>\omega : \: \langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \epsilon\rangle</tex>. Тогда <tex>xy^kz</tex> подходит. <br />
}}<br />
<br />
<br />
Чаще используется отрицание леммы для доказательства нерегулярности языка.<br />
<br />
<br />
Пример 1. Правильная скобочная последовательность. <br />
Для <tex>\forall n</tex> мы берём <tex>\omega=(^n)^n</tex>. Так как <tex>|xy|\leqslant n</tex>, то <tex>y=(^b</tex>. Берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит правильная скобочная последовательность не регулярный язык.<br />
<br />
Пример 2. Язык <tex>0^a1^a</tex><br />
Для <tex>\forall n</tex> мы берём <tex>\omega=0^n1^n</tex>. Так как <tex>|xy|\leqslant n</tex>, то <tex>y=0^b</tex>. Берём <tex>k=2</tex> и получаем <tex>xy^kz=0^{n+b}1^n</tex>, что не является элементом нашего языка, значит наш язык не регулярен.</div>Zarubkinhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%BE%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2%D0%BE_%D0%BD%D0%B5%D1%80%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2:_%D0%BB%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D0%BD%D0%B8%D0%B8&diff=3095Доказательство нерегулярности языков: лемма о разрастании2010-10-05T01:23:10Z<p>Zarubkin: </p>
<hr />
<div>{{Лемма<br />
|about=О разрастании<br />
|statement=<tex>L</tex> - регулярный <tex>\Rightarrow</tex> <tex>\exists n \:\forall \omega : |\omega| \geqslant n, \omega \in L \: \exists x,y,z : \omega=xyz, y\neq \epsilon, |xy|\leqslant n, \forall k \geqslant 0\: xy^{k}z\in L</tex><br />
|proof=L - регулярный <tex>\Rightarrow</tex> <tex>\exists</tex> автомат <tex>A : \: n=|Q|</tex> допускающий этот язык. Возьмём <tex>\omega\in L : |\omega|\geqslant n</tex> тогда рассмотрим переходы в автомате <tex>\langle s,\omega\rangle \vdash\langle u_1, \omega[0]^{-1}\omega\dots\vdash\langle u_{l},\epsilon\rangle, \: l\geqslant n</tex>. Так как <tex>l\geqslant n</tex>, то возьмём первое совпадение состояний в автомате <tex>u_i, u_j</tex>. В нашем автомате для <tex>\omega : \: \langle s, xyz\rangle \vdash^*\langle u_i, yz\rangle\vdash^*\langle u_j, z\rangle\vdash^*\langle u_l, \epsilon\rangle</tex>. Тогда <tex>xy^kz</tex> подходит. <br />
}}<br />
<br />
<br />
Чаще используется отрицание леммы для доказательства нерегулярности языка.<br />
<br />
<br />
Пример 1. Правильная скобочная последовательность. <br />
Для <tex>\forall n</tex> мы берём <tex>\omega=(^n)^n</tex>. Так как <tex>|xy|\leqslant n</tex>, то <tex>y=(^b</tex>. Берём <tex>k=2</tex> и получаем <tex>xy^kz=(^{n+b})^n</tex>, что не является правильной скобочной последовательностью. Значит правильная скобочная последовательность не регулярный язык.<br />
<br />
Пример 2. Язык <tex>0^a1^a</tex><br />
Для <tex>\forall n</tex> мы берём <tex>\omega=0^n1^n</tex>. Так как <tex>|xy|\leqslant n</tex>, то <tex>y=0^b</tex>. Берём <tex>k=2</tex> и получаем <tex>xy^kz=0^{n+b}1^n</tex>, что не является элементом нашего языка, значит наш язык не регулярен.</div>Zarubkinhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%BE%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2%D0%BE_%D0%BD%D0%B5%D1%80%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2:_%D0%BB%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D0%BD%D0%B8%D0%B8&diff=3094Доказательство нерегулярности языков: лемма о разрастании2010-10-05T00:39:52Z<p>Zarubkin: </p>
<hr />
<div>{{Лемма<br />
|about=О разрастании<br />
|statement=<tex>L</tex> - регулярный <tex>\Rightarrow</tex> <tex>\exists n \:\forall \omega : |\omega| \geqslant n, \omega \in L \: \exists x,y,z : \omega=xyz, y\neq \epsilon, |xy|\leqslant n, \forall k \geqslant 0\: xy^{k}z\in L</tex><br />
|proof=L - регулярный <tex>\Rightarrow</tex> <tex>\exists</tex> автомат <tex>A : \: n=|Q|</tex><br />
}}</div>Zarubkinhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%BE%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2%D0%BE_%D0%BD%D0%B5%D1%80%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2:_%D0%BB%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D0%BD%D0%B8%D0%B8&diff=3093Доказательство нерегулярности языков: лемма о разрастании2010-10-05T00:28:09Z<p>Zarubkin: Новая страница: «{{Лемма |about=О разрастании |statement=<tex>L</tex> - регулярный <tex>\Rightarrow</tex> <tex>\exists n \:\forall \omega : |\omega| \geqsl…»</p>
<hr />
<div>{{Лемма<br />
|about=О разрастании<br />
|statement=<tex>L</tex> - регулярный <tex>\Rightarrow</tex> <tex>\exists n \:\forall \omega : |\omega| \geqslant n, \omega \in L \: \exists x,y,z : \omega=xyz, y\neq \epsilon, |xy|\leqslant n, \forall k \geqslant 0\: xy^{k}z\in L</tex><br />
|proof=<br />
}}</div>Zarubkin