http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=Icekeeper&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-29T07:47:32ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%BC%D0%BA%D0%BD%D1%83%D1%82%D0%BE%D1%81%D1%82%D1%8C_%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B8_%D0%BF%D0%B5%D1%80%D0%B5%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2_%D0%BE%D1%82%D0%BD%D0%BE%D1%81%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D1%82%D0%B8%D0%BA%D0%BE-%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D1%85_%D0%B8_%D0%B0%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D0%B0%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D1%85_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B9&diff=5445Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций2010-12-02T05:03:28Z<p>Icekeeper: Вторая теорема</p>
<hr />
<div>{{Теорема<br />
|statement=<br />
<tex> L_1, L_2 </tex> –- разрешимы, тогда<br />
<br />
<br />
<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ \bar{L_1} \\ L_1 \backslash L_2 \\ L_1^* \\ L_1 L_2 \end{array} \right\} </tex> разрешимы<br />
|proof=<br />
Если языки разрешимы, значит для каждого из них есть разрешающая программа. Тогда разрешающая программа для языка <tex>L_1 \cup L_2</tex> будет запускать разрешающую для каждого языка и выводить 1, если оба разрешателя выдали 1, 0 во всех остальных случаях. Для языка <tex> L_1 \cap L_2 </tex> разрешающая программа будет запускать оба разрешателя и выдавать 0, если оба разрешателя выдали 0, 1 во всех остальынх случаях. Для языка <tex> \bar{L_1} </tex> разрешатель будет выдавать результат, обратный результату разрешателя для <tex> L_1 </tex>. Для языка <tex> L_1 \backslash L_2 </tex> разрешающая программа будет запускать оба разрешателя и выдавать 1, если первый разрешатель вернет 1, а второй 0 и 0 во всех остальных случаях. Для языка <tex> L_1^* </tex> разрешатель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все слова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex> иначе не принадлежит. Для языка <tex> L_1 L_2 </tex> разрешающая программа будет перебирать все возможные разбиения на 2 слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе не принадлежит.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
<tex> L_1, L_2 </tex> –- перечислимы, тогда<br />
<br />
<br />
<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ L_1^* \\ L_1 L_2 \end{array} \right\} </tex> перечислимы<br />
<tex>\left. \begin{array}{lll} \bar{L_1} \\ L_1 \backslash L_2 \end{array} \right\} </tex> могут быть не перечислимы<br />
|proof=<br />
Для <tex> L_1 \cup L_2 </tex> перечислитель будет по очереди на один шаг запускать перечислители <tex> L_1 </tex> и <tex> L_2 </tex> и выдавать по очереди слова из <tex> L_1 </tex> и <tex> L_2 </tex>. Дальше воспользуемся возможностью построить полувычислитель для перечислимого языка. Для языка <tex> L_1 \cap L_2 </tex> построим полувычислитель. Запустим по очереди полувычислители для <tex> L_1 </tex> и <tex> L_2 </tex>. Если слово принадлежит <tex> L_1 \cap L_2 </tex>, то оба полувычислителя выдадут 1, иначе один из полувычислителей зависнет, и полувычислитель для <tex> L_1 \cap L_2 </tex> тоже зависнет, что допустимо. Для <tex> L_1^* </tex> перечислитель строится следующим образом: запускаем перечислитель для <tex> L_1 </tex> в цикле и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их. Перечислитель для <tex> L_1 L_2 </tex> строим следующим образом: запускаем одновременно перечислители для <tex> L_1 </tex> и <tex> L_2 </tex>, запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их.<br />
<br />
<br />
Рассмотрим язык <tex> \bar{L_1} </tex>. Предположим, что он перечислим. Тогда имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \bar{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \bar{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что существуют перечислимые, но не разрешимые языки, следовательно, язык <tex> \bar{L_1} </tex> может быть не перечислим. Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \bar{L_2} </tex>. Про язык <tex> \bar{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.<br />
}}</div>Icekeeperhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%BC%D0%BA%D0%BD%D1%83%D1%82%D0%BE%D1%81%D1%82%D1%8C_%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B8_%D0%BF%D0%B5%D1%80%D0%B5%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2_%D0%BE%D1%82%D0%BD%D0%BE%D1%81%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D1%82%D0%B8%D0%BA%D0%BE-%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D1%85_%D0%B8_%D0%B0%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D0%B0%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D1%85_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B9&diff=5440Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций2010-12-02T04:38:02Z<p>Icekeeper: Первая теорема.</p>
<hr />
<div>{{Теорема<br />
|statement=<br />
<tex> L_1, L_2 </tex> –- разрешимы, тогда<br />
<br />
<br />
<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ \bar{L_1} \\ L_1 \backslash L_2 \\ L_1^* \\ L_1 L_2 \end{array} \right\} </tex> разрешимы<br />
|proof=<br />
Если языки разрешимы, значит для каждого из них есть разрешающая программа. Тогда разрешающая программа для языка <tex>L_1 \cup L_2</tex> будет запускать разрешающую для каждого языка и выводить 1, если оба разрешателя выдали 1, 0 во всех остальных случаях. Для языка <tex> L_1 \cap L_2 </tex> разрешающая программа будет запускать оба разрешателя и выдавать 0, если оба разрешателя выдали 0, 1 во всех остальынх случаях. Для языка <tex> \bar{L_1} </tex> разрешатель будет выдавать результат, обратный результату разрешателя для <tex> L_1 </tex>. Для языка <tex> L_1 \backslash L_2 </tex> разрешающая программа будет запускать оба разрешателя и выдавать 1, если первый разрешатель вернет 1, а второй 0 и 0 во всех остальных случаях. Для языка <tex> L_1^* </tex> разрешатель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все слова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex> иначе не принадлежит. Для языка <tex> L_1 L_2 </tex> разрешающая программа будет перебирать все возможные разбиения на 2 слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex> иначе не принадлежит.<br />
}}</div>Icekeeperhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%B2%D0%BE%D0%BA%D0%BE%D0%BD%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8,_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B0%D0%BC&diff=3923Правоконтекстные грамматики, эквивалентность автоматам2010-10-14T01:35:56Z<p>Icekeeper: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
'''Праволинейной грамматикой''' <tex>\Gamma</tex> называется грамматика, в которой все правила имеют вид <tex> A \to a </tex>, <tex> A \to aB </tex>.<br />
}}<br />
<br />
Аналогично можно определить леволинейные грамматики.<br />
<br />
{{Теорема<br />
|statement=<br />
Множество языков, задаваемых праволинейными грамматиками совпадает со множеством языков, задаваемых конечными автоматами.<br />
|proof=<br />
Пусть имеется конечный автомат. Построим для него праволинейную грамматику. Множеством нетерминалов нашей грамматики будет множество состояний автомата. Для каждой пары состояний автомата <tex>A</tex> и <tex>B</tex> таких, что имеется переход из <tex>A</tex> в <tex>B</tex> по символу <tex>c</tex>, добавим в грамматику правило <tex> A \to cB </tex>. Затем для каждой пары состояний автомата <tex>A</tex> и <tex>B</tex> таких, что имеется переход из <tex>A</tex> в <tex>B</tex> по символу <tex>c</tex>, и <tex> B </tex> – является допускающим состоянием в автомате, добавим в грамматику правило <tex> A \to c </tex>. <br />
<br />
Докажем, что если для автомата верно <tex>\langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle </tex>, то для построенной грамматики верно <tex> S \Rightarrow^* \alpha U </tex>. Будем доказывать индукцией по переходам в автомате.<br />
<br />
Базой индукции будут переходы за 0 шагов.<br />
Индукционный переход: пусть данное свойство выполняется для переходов длины <tex>k-1</tex>. Докажем что верно и для переходов за <tex>k</tex> шагов.<br />
<br />
Рассмотрим переход <tex>\langle S, \alpha \rangle \vdash^{k} \langle U, \varepsilon \rangle </tex>, а именно его последний шаг: <tex> \langle S, \alpha \rangle \vdash^{k-1} \langle Q, c \rangle \vdash \langle U, \varepsilon \rangle </tex><br />
Так как для <tex>k-1</tex> шагов верно, то <tex> S \Rightarrow^{k-1} \alpha c^{-1} Q </tex> но по построению грамматики имеется правило <tex> Q \to c U</tex>, значит <tex> S \Rightarrow^{k-1} \alpha c^{-1} Q \Rightarrow \alpha c^{-1} c U = \alpha U</tex>. Таким образом доказали для <tex>k</tex> шагов.<br />
<br />
Докажем в обратную сторону, а именно из <tex> S \Rightarrow^* \alpha U </tex> следует <tex> \langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle </tex>. Доказательство так же проведем по индукции. Индукция будет идти по количеству примененных подряд правил.<br />
<br />
Базой индукции будут строки, выводимые в грамматике из начального нетерминала <tex> S </tex> за 0 применений правил.<br />
<br />
Индукционный переход: пусть верно для <tex>k-1</tex> применения правил. Рассмотрим произвольную строку, полученную за <tex>k</tex> применений правил. Рассмотрим последнее применение правила. Если оно имело вид <tex> A \to aB </tex>, значит в автомате возможен переход <tex> \langle A,a \rangle \vdash \langle B,\varepsilon \rangle </tex>, а если <tex> A \to a </tex>, то <tex> B </tex> является допускающим в автомате. Таким образом свойство выполняется для <tex> k </tex> последовательно примененных правил. Эквивалентность языков автомата и грамматики доказана.<br />
<br />
<br />
Теперь пусть имеется праволинейная грамматика. Построим по ней конечный детерминированный автомат. <br />
Введем специальное допускающее состояние <tex> ok </tex>. Множеством состояний автомата будет множество нетерминалов грамматики вместе с состоянием <tex> ok </tex> (<tex> Q = N \cup ok </tex>). Для правил вида <tex> A \to aB </tex> определим функцию перехода в автомате как <tex> \delta \left( A, a \right) = B </tex>. Для правил вида <tex> A \to a </tex> определим функцию перехода в автомате как <tex> \delta \left( A, a \right) = ok </tex>.<br />
<br />
Докажем, что если слово выводится в грамматике, то оно допускается автоматом. Рассмотрим последовательность применений правил, дающую слово <tex> \alpha </tex> длины <tex> k </tex>. Для каждого правила вида <tex> A \to aB </tex> в автомате существует переход из состояния <tex> A </tex> в состояние <tex> B</tex> по символу <tex> a </tex>. Таким образом, если после <tex> k-1 </tex> применения правил мы можем получить строку вида <tex> \alpha c^{-1}B </tex>, то в автомате имеется соответствующая последовательность переходов <tex> \langle S, \alpha \rangle \vdash^{k-1} \langle B, c \rangle </tex>, а поскольку можно вывести <tex> \alpha </tex>, то хотя бы для одной строки такого вида существует правило <tex> B \to c </tex>, а значит в автомате есть переход <tex> \langle B,c \rangle \vdash \langle ok,\varepsilon \rangle </tex>. Таким образом автомат допускает слово <tex> \alpha </tex>.<br />
<br />
Докажем, что если слово допускается автоматом, то его можно вывести в грамматике. Рассмотрим слово <tex> \alpha </tex> длины <tex> k </tex>. Рассмотрим какую-либо последовательность переходов автомата, допускающую данное слово <tex> \langle S,\alpha \rangle \vdash^k \langle ok,\varepsilon \rangle </tex>. Для каждого одношагового перехода в автомате существует соответствующее правило в грамматике. Значит для подпоследовательности переходов из <tex> k-1 </tex> шага <tex> \langle S, \alpha \rangle \vdash^{k-1} \langle U,c \rangle </tex> существует соответствующая последовательность применений правил <tex> S \Rightarrow^{k-1} \alpha c^{-1} U </tex>. Для последнего перехода в автомате <tex> \langle U,c \rangle \vdash \langle ok, \varepsilon \rangle </tex> существует правило <tex> U \Rightarrow c </tex>. Таким образом, существует последовательность применений правил грамматики, выводящая слово <tex> \alpha </tex>.<br />
<br />
Теорема доказана.<br />
<br />
}}</div>Icekeeperhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%B2%D0%BE%D0%BA%D0%BE%D0%BD%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8,_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B0%D0%BC&diff=3922Правоконтекстные грамматики, эквивалентность автоматам2010-10-14T01:29:11Z<p>Icekeeper: Финальная версия</p>
<hr />
<div>{{Определение<br />
|definition=<br />
'''Праволинейной грамматикой''' <tex>\Gamma</tex> называется грамматика, в которой все правила имеют вид <tex> A \to a </tex>, <tex> A \to aB </tex>.<br />
}}<br />
<br />
Аналогично можно определить леволинейные грамматики.<br />
<br />
{{Теорема<br />
|statement=<br />
Множество языков, задаваемых праволинейными грамматиками совпадает со множеством языков, задаваемых конечными автоматами.<br />
|proof=<br />
Пусть имеется конечный автомат. Построим для него праволинейную грамматику. Множеством нетерминалов нашей грамматики будет множество состояний автомата. Для каждой пары состояний автомата <tex>A</tex> и <tex>B</tex> таких, что имеется переход из <tex>A</tex> в <tex>B</tex> по символу <tex>c</tex>, добавим в грамматику правило <tex> A \to cB </tex>. Затем для каждой пары состояний автомата <tex>A</tex> и <tex>B</tex> таких, что имеется переход из <tex>A</tex> в <tex>B</tex> по символу <tex>c</tex>, и <tex> B </tex> – является допускающим состоянием в автомате, добавим в грамматику правило <tex> A \to c </tex>. <br />
<br />
Докажем, что если для автомата верно <tex>\langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle </tex>, то для построенной грамматики верно <tex> S \Rightarrow^* \alpha U </tex>. Будем доказывать индукцией по переходам в автомате.<br />
<br />
Базой индукции будут переходы за 0 шагов.<br />
Индукционный переход: пусть данное свойство выполняется для переходов длины <tex>k-1</tex>. Докажем что верно и для переходов за <tex>k</tex> шагов.<br />
<br />
Рассмотрим переход <tex>\langle S, \alpha \rangle \vdash^{k} \langle U, \varepsilon \rangle </tex>, а именно его последний шаг: <tex> \langle S, \alpha \rangle \vdash^{k-1} \langle Q, c \rangle \vdash \langle U, \varepsilon \rangle </tex><br />
Так как для <tex>k-1</tex> шагов верно, то <tex> S \Rightarrow^{k-1} \alpha c^{-1} Q </tex> но по построению грамматики имеется правило <tex> Q \to c U</tex>, значит <tex> S \Rightarrow^{k-1} \alpha c^{-1} Q \Rightarrow \alpha c^{-1} c U = \alpha U</tex>. Таким образом доказали для <tex>k</tex> шагов.<br />
<br />
Докажем в обратную сторону, а именно из <tex> S \Rightarrow^* \alpha U </tex> следует <tex> \langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle </tex>. Доказательство так же проведем по индукции. Индукция будет идти по количеству примененных подряд правил.<br />
<br />
Базой индукции будут строки, выводимые в грамматике из начального нетерминала <tex> S </tex> за 0 применений правил.<br />
<br />
Индукционный переход: пусть верно для <tex>k-1</tex> применения правил. Рассмотрим произвольную строку, полученную за <tex>k</tex> применений правил. Рассмотрим последнее применение правила. Если оно имело вид <tex> A \to aB </tex>, значит в автомате возможен переход <tex> \langle A,a \rangle \vdash \langle B,\varepsilon \rangle </tex>, а если <tex> A \to a </tex>, то <tex> B </tex> является допускающим в автомате. Таким образом свойство выполняется для <tex> k </tex> последовательно примененных правил. Эквивалентность языков автомата и грамматики доказана.<br />
<br />
<br />
Теперь пусть имеется праволинейная грамматика. Построим по ней конечный детерминированный автомат. <br />
Введем специальное допускающее состояние <tex> ok </tex>. Множеством состояний автомата будет множество нетерминалов грамматики вместе с состоянием <tex> ok </tex> (<tex> Q = N \cup ok </tex>). Для правил вида <tex> A \to aB </tex> определим функцию перехода в автомате как <tex> \delta \left( A, a \right) = B </tex>. Для правил вида <tex> A \to a </tex> определим функцию перехода в автомате как <tex> \delta \left( A, a \right) = ok </tex>.<br />
<br />
Докажем, что если слово выводится в грамматике, то оно допускается автоматом. Рассмотрим последовательность применений правил, дающую слово <tex> \alpha </tex> длины <tex> k </tex>. Для каждого правила вида <tex> A \to aB </tex> в автомате существует переход из состояния <tex> A </tex> в состояние <tex> B</tex> по символу <tex> a </tex>. Таким образом, если после <tex> k-1 </tex> применения правил мы можем получить строку вида <tex> \alpha c^{-1}B </tex>, то в автомате имеется последовательность переходов <tex> \langle S, \alpha \rangle \vdash^{k-1} \langle B, c \rangle </tex>, а поскольку можно вывести <tex> \alpha </tex>, то хотя бы для одной строки такого вида существует правило <tex> B \to c </tex>, а значит в автомате есть переход <tex> \langle B,c \rangle \vdash \langle ok,\varepsilon \rangle </tex>. Таким образом автомат допускает слово <tex> \alpha </tex>.<br />
<br />
Докажем, что если слово допускается автоматом, то его можно вывести в грамматике. Рассмотрим слово <tex> \alpha </tex> длины <tex> k </tex>. Рассмотрим какую-либо последовательность переходов автомата, допускающую данное слово <tex> \langle S,\alpha \rangle \vdash^k \langle ok,\varepsilon \rangle </tex>. Для каждого одношагового перехода в автомате существует соответствующее правило в грамматике. Значит для подпоследовательности переходов из <tex> k-1 </tex> шага <tex> \langle S, \alpha \rangle \vdash^{k-1} \langle U,c \rangle </tex> существует последовательность применений правил <tex> S \Rightarrow^{k-1} \alpha c^{-1} U </tex>. Для последнего перехода в автомате <tex> \langle U,c \rangle \vdash \langle ok, \varepsilon \rangle </tex> существует правило <tex> U \Rightarrow c </tex>. Таким образом, существует последовательность применений правил грамматики, выводящая слово <tex> \alpha </tex>.<br />
<br />
Теорема доказана.<br />
<br />
}}</div>Icekeeperhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%B2%D0%BE%D0%BA%D0%BE%D0%BD%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8,_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B0%D0%BC&diff=3714Правоконтекстные грамматики, эквивалентность автоматам2010-10-12T03:02:22Z<p>Icekeeper: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
'''Праволинейной грамматикой''' <tex>\Gamma</tex> называется грамматика, в которой все правила имеют вид <tex> A \to a </tex>, <tex> A \to aB </tex>.<br />
}}<br />
<br />
Аналогично можно определить леволинейные грамматики.<br />
<br />
{{Теорема<br />
|statement=<br />
Множество языков, задаваемых праволинейными грамматиками совпадает со множеством языков, задаваемых конечными автоматами.<br />
|proof=<br />
Пусть имеется конечный автомат. Построим для него праволинейную грамматику. Множеством нетерминалов нашей грамматики будет множество состояний автомата. Для каждой пары состояний автомата <tex>A</tex> и <tex>B</tex> таких, что имеется переход из <tex>A</tex> в <tex>B</tex> по символу <tex>c</tex>, и <tex> B </tex> – не является допускающим состоянием в автомате, добавим в грамматику правило <tex> A \to cB </tex>. Затем для каждой пары состояний автомата <tex>A</tex> и <tex>B</tex> таких, что имеется переход из <tex>A</tex> в <tex>B</tex> по символу <tex>c</tex>, и <tex> B </tex> – является допускающим состоянием в автомате, добавим в грамматику правило <tex> A \to c </tex>. <br />
<br />
Докажем, что если для автомата верно <tex>\langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle </tex>, то для построенной грамматики верно <tex> S \Rightarrow^* \alpha U </tex>. Будем доказывать индукцией по переходам в автомате.<br />
<br />
Базой индукции будут переходы за 0 шагов.<br />
Индукционный переход: пусть данное свойство выполняется для переходов длины <tex>k-1</tex>. Докажем что верно и для переходов за <tex>k</tex> шагов.<br />
<br />
Рассмотрим переход <tex>\langle S, \alpha \rangle \vdash^{k} \langle U, \varepsilon \rangle </tex>, а именно его последний шаг: <tex> \langle S, \alpha \rangle \vdash^{k-1} \langle Q, c \rangle \vdash \langle U, \varepsilon \rangle </tex><br />
Так как для <tex>k-1</tex> шагов верно, то <tex> S \Rightarrow^{k-1} \alpha c^{-1} Q </tex> но по построению грамматики имеется правило <tex> Q \to c U</tex>, значит <tex> S \Rightarrow^{k-1} \alpha c^{-1} Q \Rightarrow \alpha c^{-1} c U = \alpha U</tex>. Таким образом доказали для <tex>k</tex> шагов.<br />
<br />
Теперь пусть имеется праволинейная грамматика. Построим по ней конечный детерминированный автомат. <br />
Введем специальное допускающее состояние <tex> ok </tex>. Множеством состояний автомата будет множество нетерминалов грамматики вместе с состоянием <tex> ok </tex> (<tex> Q = N \cup ok </tex>). Для правил вида <tex> A \to aB </tex> определим функцию перехода в автомате как <tex> \delta \left( A, a \right) = B </tex>. Для правил вида <tex> A \to a </tex> определим функцию перехода в автомате как <tex> \delta \left( A, a \right) = ok </tex> <br />
<br />
<br />
}}</div>Icekeeperhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%B2%D0%BE%D0%BA%D0%BE%D0%BD%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8,_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B0%D0%BC&diff=3446Правоконтекстные грамматики, эквивалентность автоматам2010-10-09T17:05:06Z<p>Icekeeper: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
'''Праволинейной грамматикой''' <tex>\Gamma</tex> называется грамматика, в которой все правила имеют вид<br />
}}</div>Icekeeperhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%B2%D0%BE%D0%BA%D0%BE%D0%BD%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8,_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B0%D0%BC&diff=3445Правоконтекстные грамматики, эквивалентность автоматам2010-10-09T16:55:57Z<p>Icekeeper: Новая страница: «{{Определение |definition= '''Правоконтекстной грамматикой''' <tex>\Gamma</tex> называется грамматика, в …»</p>
<hr />
<div>{{Определение<br />
|definition=<br />
'''Правоконтекстной грамматикой''' <tex>\Gamma</tex> называется грамматика, в которой все правила имеют вид<br />
}}</div>Icekeeper