Викиконспекты - Вклад участника [ru]

Теория формальных языков

2017-01-05T14:43:40Z

Анна: /* Примеры неразрешимых задач */

[[Категория: Теория формальных языков]]
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
== Автоматы и регулярные языки ==
=== Регулярные языки и ДКА ===
*[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]
*[[Регулярные языки: два определения и их эквивалентность | Регулярные языки: два определения и их эквивалентность, регулярные выражения]]
*[[Детерминированные конечные автоматы]]
*[[Прямое произведение ДКА]]
*[[Простой сопоставитель регулярных выражений]] <tex> \star </tex>

=== НКА ===
*[[Недетерминированные конечные автоматы]]
*[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]
*[[Автоматы с eps-переходами. Eps-замыкание]]
*[[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
*[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
=== Минимизация ДКА ===
*[[Эквивалентность состояний ДКА]]
*[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]
*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
*[[Алгоритм Бржозовского]]<tex> ^\star </tex>
=== Свойства конечных автоматов ===
*[[Доказательство нерегулярности языков: лемма о разрастании]]
*[[Интерпретация булевых формул с кванторами как игр для двух игроков]]
*[[Решение уравнений в регулярных выражениях]]
*[[Замкнутость регулярных языков относительно различных операций]]
*[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]
*[[Контексты и синтаксические моноиды]]
=== Другие автоматы ===
*[[Локальные автоматы]]<tex> ^\star </tex>
*[[Двусторонний детерминированный конечный автомат]]<tex> ^\star </tex>
*[[Квантовые конечные автоматы]]<tex> ^\star </tex>
*[[Автоматы Мура и Мили]]<tex> ^\star </tex>

== Контекстно-свободные грамматики ==
=== Базовые понятия о грамматиках ===
*[[Формальные грамматики]]
*[[Иерархия Хомского формальных грамматик]]
*[[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]
*[[Правоконтекстные грамматики, эквивалентность автоматам]]
*[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
*[[Замкнутость КС-языков относительно различных операций]]
*[[Регулярная аппроксимация КС-языков]]<tex> ^\star </tex>

=== Нормальные формы КС-грамматик ===
*[[Удаление бесполезных символов из грамматики]]
*[[Удаление длинных правил из грамматики]]
*[[Удаление eps-правил из грамматики]]
*[[Удаление цепных правил из грамматики]]
*[[Нормальная форма Хомского]]
*[[Устранение левой рекурсии]]
*[[Приведение грамматики к ослабленной нормальной форме Грейбах]]
*[[Нормальная форма Куроды]]<tex> ^\star </tex>

=== Алгоритмы разбора ===
*[[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
*[[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]
*[[Алгоритм Эрли]]
*[[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]

=== Опровержение контекстно-свободности языка ===
*[[Лемма о разрастании для КС-грамматик]]
*[[Лемма Огдена]]
*[[Существенно неоднозначные языки]]
*[[Теорема Парика]]<tex> ^\star </tex>

=== МП-автоматы ===
*[[Автоматы с магазинной памятью]]
*[[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]
*[[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]
*[[Детерминированные автоматы с магазинной памятью]]
*[[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
*[[Нормальная форма ДМП-автомата]]
*[[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
*[[ДМП-автоматы и неоднозначность]]

== Теория вычислимости ==
=== Разрешимые и перечислимые языки ===
*[[Разрешимые (рекурсивные) языки]]
*[[Перечислимые языки]]
*[[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]]
*[[Вычислимые функции]]
*[[Вычислимые числа]]
*[[Универсальная функция|Универсальная функция и главные нумерации]]
*[[Свойства перечислимых языков. Теорема Успенского-Райса]]
*[[Неотделимые множества]]
*[[Иммунные и простые множества]]
*[[Теорема о рекурсии]]
*[[Квайны]]<tex> ^\star </tex>
*[[Busy beaver]]
*[[Колмогоровская сложность]]<tex> ^\star </tex>

=== Вычислительные формализмы ===
*[[Машина Тьюринга]]
*[[Лямбда-исчисление]]<tex> ^\star </tex>
*[[Рекурсивные функции, представимость в формальной арифметике | Примитивно рекурсивные функции]]<tex> ^\star </tex>
*[[Частично рекурсивные функции]]<tex> ^\star </tex>
*[[Стековые машины, эквивалентность двухстековой машины МТ]]
*[[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]
*[[Линейный клеточный автомат, эквивалентность МТ]]
*[[Возможность порождения формальной грамматикой произвольного перечислимого языка]]
*[[Линейный ограниченный автомат]]
*[[Сверхтьюринговые вычисления (гипервычисления)]]<tex> ^\star </tex>

=== Примеры неразрешимых задач ===
*[[m-сводимость]]
*[[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]
*[[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]
*[[Неразрешимость задачи об эквивалентности КС-грамматик|Эквивалентность КС-грамматик]]
*[[Неразрешимость задачи о проверке на пустоту пересечения двух КС-грамматик|Пустота пересечения КС-грамматик]]
*[[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]
*[[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]
*[[Неразрешимость исчисления предикатов первого порядка]]
*[[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]
*[[Игра «Жизнь»]]<tex>^\star</tex>
*[[Неразрешимость игры Braid]]<tex>^\star</tex>
*[[Теорема Райса-Шапиро]]

Неразрешимость задачи о проверке на пустоту пересечения двух КС-грамматик

2017-01-04T22:10:36Z

Анна:

{{Теорема
|statement= Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.
|proof=
Пусть <tex>A = \{ (G_1, G_2) \mid L(G_1) \cap L(G_2) = \varnothing \}</tex>. Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>\overline{A}</tex>, таким образом показав, что дополнение проблемы неразрешимо. Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций|замкнуты относительно дополнения]], то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.

Для любого экземпляра ПСП <tex>(x_1, x_2, ..., x_n)</tex> и <tex>(y_1, y_2, ..., y_n)</tex> над алфавитом <tex>\Sigma</tex> можно подобрать символ <tex>\# \notin \Sigma</tex>. Для каждого экземпляра построим грамматики:
* <tex>G_1 : S \rightarrow aSa \mid a\#a</tex> для всех <tex>a \in \Sigma</tex>. Тогда <tex>L(G_1) = \{ w\#w^R \mid w \in \Sigma^* \}</tex>, где обозначение <tex>w^R</tex> {{---}} разворот <tex>w</tex>.
* <tex>G_2 : S \rightarrow x_iSy^R_i \mid x_i\#y^R_i</tex> для всех <tex>i = 1, 2, \dots n</tex>. Тогда <tex>L(G_2) = \{ x_{i_1} x_{i_2} \dots x_{i_m} \# (y_{i_1} y_{i_2} \dots y_{i_m})^R \mid i_1, i_2, \dots i_m \in \{ 1, 2, \dots n \}, m \geqslant 1 \}</tex>.

Если данный экземпляр ПСП имеет решение, то <tex>L(G_2)</tex> содержит хотя бы одну строку вида <tex>w\#w^R</tex>, поэтому <tex>L(G_1) \cap L(G_2) \ne \varnothing</tex>, и наоборот, если он не имеет решения, то <tex>L(G_2)</tex> не содержит строк такого вида, соответственно <tex>L(G_1) \cap L(G_2) = \varnothing</tex>.

Таким образом мы свели проблему соответствий Поста к <tex>\overline{A}</tex>, следовательно, задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.
}}
Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров.

По двум КС-грамматикам <tex>G_1</tex> и <tex>G_2</tex> можно построить КС-грамматику для [[Замкнутость КС-языков относительно различных операций#.D0.9A.D0.BE.D0.BD.D0.BA.D0.B0.D1.82.D0.B5.D0.BD.D0.B0.D1.86.D0.B8.D1.8F|конкатенации]] задаваемых ими языков <tex>L(G_1)L(G_2)</tex>. По аналогии с этим мы можем рассматривать язык <tex>L(G_1)\#L(G_2)\#</tex>, где <tex>\#</tex> {{---}} новый символ, не встречающийся в алфавите. Заметим, что пересечение языков непусто, то есть <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex>, тогда и только тогда, когда <tex>L(G_1)\#L(G_2)\#</tex> содержит [[Алгоритм Ландау-Шмидта#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|тандемный повтор]].

Аналогично можно заметить, что пересечение <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex> тогда и только тогда, когда <tex>L(G_1)\#L(G_2)^R</tex> содержит палиндром.

Таким образом, мы имеем:
{{Утверждение
|statement= Пусть дана грамматика <tex>G</tex>, <tex>L(G) = L</tex>. Тогда следующие задачи неразрешимы:
# Содержит ли <tex>L</tex> тандемный повтор.
# Содержит ли <tex>L</tex> палиндром.
}}

== См. также ==
* [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора | Контекстно-свободные грамматики]]
* [[Разрешимые (рекурсивные) языки | Разрешимые языки]]
* [[Примеры неразрешимых задач: проблема соответствий Поста | Проблема соответствий Поста]]

== Источники информации ==
* [http://liacs.leidenuniv.nl/~hoogeboomhj/second/codingcomputations.pdf Hendrik Jan Hoogeboom "Undecidable Problems for Context-free Grammars".]

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Примеры неразрешимых задач]]

Неразрешимость задачи о проверке на пустоту пересечения двух КС-грамматик

2017-01-04T18:34:01Z

Анна: Новая страница: «{{Теорема |statement= Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима. ...»

{{Теорема
|statement= Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.
|proof=
Пусть <tex>A = \{ (G_1, G_2) \mid L(G_1) \cap L(G_2) = \varnothing \}</tex>. Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>\overline{A}</tex>, таким образом показав, что дополнение проблемы неразрешимо. Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций|замкнуты относительно дополнения]], то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.

Для любого экземпляра ПСП <tex>(x_1, x_2, ..., x_n)</tex> и <tex>(y_1, y_2, ..., y_n)</tex> над алфавитом <tex>\Sigma</tex> можно подобрать символ <tex>\# \notin \Sigma</tex>. Для каждого экземпляра построим грамматики:
* <tex>G_1 : S \rightarrow aSa \mid a\#a</tex> для всех <tex>a \in \Sigma</tex>. Тогда <tex>L(G_1) = \{ w\#w^R \mid w \in \Sigma^* \}</tex>, где обозначение <tex>w^R</tex> {{---}} разворот <tex>w</tex>.
* <tex>G_2 : S \rightarrow x_iSy^R_i \mid x_i\#y^R_i</tex> для всех <tex>i = 1, 2, \dots n</tex>. Тогда <tex>L(G_2) = \{ x_{i_1} x_{i_2} \dots x_{i_m} \# (y_{i_1} y_{i_2} \dots y_{i_m})^R \mid i_1, i_2, \dots i_m \in \{ 1, 2, \dots n \}, m \geqslant 1 \}</tex>.

Если данный экземпляр ПСП имеет решение, то <tex>L(G_2)</tex> содержит хотя бы одну строку вида <tex>w\#w^R</tex>, поэтому <tex>L(G_1) \cap L(G_2) \ne \varnothing</tex>, и наоборот, если он не имеет решения, то <tex>L(G_2)</tex> не содержит строк такого вида, соответственно <tex>L(G_1) \cap L(G_2) = \varnothing</tex>.

Таким образом мы свели проблему соответствий Поста к <tex>\overline{A}</tex>, следовательно, задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.
}}
Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров.

По двум КС-грамматикам <tex>G_1</tex> и <tex>G_2</tex> можно построить КС-грамматику для [[Замкнутость КС-языков относительно различных операций#.D0.9A.D0.BE.D0.BD.D0.BA.D0.B0.D1.82.D0.B5.D0.BD.D0.B0.D1.86.D0.B8.D1.8F|конкатенации]] задаваемых ими языков <tex>L(G_1)L(G_2)</tex>. По аналогии с этим мы можем рассматривать язык <tex>L(G_1)\#L(G_2)\#</tex>, где <tex>\#</tex> {{---}} новый символ, не встречающийся в алфавите. Заметим, что пересечение языков непусто, то есть <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex>, тогда и только тогда, когда <tex>L(G_1)\#L(G_2)\#</tex> содержит [[Алгоритм Ландау-Шмидта#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|тандемный повтор]].

Аналогично можно заметить, что пересечение <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex> тогда и только тогда, когда <tex>L(G_1)\#L(G_2)^R</tex> содержит палиндром.

Таким образом, мы имеем:
{{Утверждение
|statement= Пусть дана грамматика <tex>G</tex>, <tex>L(G) = L</tex>. Тогда следующие задачи неразрешимы:
# Содержит ли <tex>L</tex> тандемный повтор.
# Содержит ли <tex>L</tex> палиндром.
}}

== См. также ==
* [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора | Контекстно-свободные грамматики]]
* [[Разрешимые (рекурсивные) языки | Разрешимые языки]]
* [[Примеры неразрешимых задач: проблема соответствий Поста | Проблема соответствий Поста]]

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Примеры неразрешимых задач]]

Теория формальных языков

2017-01-04T18:31:58Z

Анна: /* Примеры неразрешимых задач */

[[Категория: Теория формальных языков]]
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
== Автоматы и регулярные языки ==
=== Регулярные языки и ДКА ===
*[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]
*[[Регулярные языки: два определения и их эквивалентность | Регулярные языки: два определения и их эквивалентность, регулярные выражения]]
*[[Детерминированные конечные автоматы]]
*[[Прямое произведение ДКА]]
*[[Простой сопоставитель регулярных выражений]] <tex> \star </tex>

=== НКА ===
*[[Недетерминированные конечные автоматы]]
*[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]
*[[Автоматы с eps-переходами. Eps-замыкание]]
*[[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
*[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
=== Минимизация ДКА ===
*[[Эквивалентность состояний ДКА]]
*[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]
*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
*[[Алгоритм Бржозовского]]<tex> ^\star </tex>
=== Свойства конечных автоматов ===
*[[Доказательство нерегулярности языков: лемма о разрастании]]
*[[Интерпретация булевых формул с кванторами как игр для двух игроков]]
*[[Решение уравнений в регулярных выражениях]]
*[[Замкнутость регулярных языков относительно различных операций]]
*[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]
*[[Контексты и синтаксические моноиды]]
=== Другие автоматы ===
*[[Локальные автоматы]]<tex> ^\star </tex>
*[[Двусторонний детерминированный конечный автомат]]<tex> ^\star </tex>
*[[Квантовые конечные автоматы]]<tex> ^\star </tex>
*[[Автоматы Мура и Мили]]<tex> ^\star </tex>

== Контекстно-свободные грамматики ==
=== Базовые понятия о грамматиках ===
*[[Формальные грамматики]]
*[[Иерархия Хомского формальных грамматик]]
*[[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]
*[[Правоконтекстные грамматики, эквивалентность автоматам]]
*[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
*[[Замкнутость КС-языков относительно различных операций]]
*[[Регулярная аппроксимация КС-языков]]<tex> ^\star </tex>

=== Нормальные формы КС-грамматик ===
*[[Удаление бесполезных символов из грамматики]]
*[[Удаление длинных правил из грамматики]]
*[[Удаление eps-правил из грамматики]]
*[[Удаление цепных правил из грамматики]]
*[[Нормальная форма Хомского]]
*[[Устранение левой рекурсии]]
*[[Приведение грамматики к ослабленной нормальной форме Грейбах]]
*[[Нормальная форма Куроды]]<tex> ^\star </tex>

=== Алгоритмы разбора ===
*[[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
*[[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]
*[[Алгоритм Эрли]]
*[[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]

=== Опровержение контекстно-свободности языка ===
*[[Лемма о разрастании для КС-грамматик]]
*[[Лемма Огдена]]
*[[Существенно неоднозначные языки]]
*[[Теорема Парика]]<tex> ^\star </tex>

=== МП-автоматы ===
*[[Автоматы с магазинной памятью]]
*[[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]
*[[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]
*[[Детерминированные автоматы с магазинной памятью]]
*[[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
*[[Нормальная форма ДМП-автомата]]
*[[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
*[[ДМП-автоматы и неоднозначность]]

== Теория вычислимости ==
=== Разрешимые и перечислимые языки ===
*[[Разрешимые (рекурсивные) языки]]
*[[Перечислимые языки]]
*[[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]]
*[[Вычислимые функции]]
*[[Вычислимые числа]]
*[[Универсальная функция|Универсальная функция и главные нумерации]]
*[[Свойства перечислимых языков. Теорема Успенского-Райса]]
*[[Неотделимые множества]]
*[[Иммунные и простые множества]]
*[[Теорема о рекурсии]]
*[[Квайны]]<tex> ^\star </tex>
*[[Busy beaver]]
*[[Колмогоровская сложность]]<tex> ^\star </tex>

=== Вычислительные формализмы ===
*[[Машина Тьюринга]]
*[[Лямбда-исчисление]]<tex> ^\star </tex>
*[[Рекурсивные функции, представимость в формальной арифметике | Примитивно рекурсивные функции]]<tex> ^\star </tex>
*[[Частично рекурсивные функции]]<tex> ^\star </tex>
*[[Стековые машины, эквивалентность двухстековой машины МТ]]
*[[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]
*[[Линейный клеточный автомат, эквивалентность МТ]]
*[[Возможность порождения формальной грамматикой произвольного перечислимого языка]]
*[[Линейный ограниченный автомат]]
*[[Сверхтьюринговые вычисления (гипервычисления)]]<tex> ^\star </tex>

=== Примеры неразрешимых задач ===
*[[m-сводимость]]
*[[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]
*[[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]
*[[Неразрешимость задачи об эквивалентности КС-грамматик|Эквивалентность КС-грамматик]]
*[[Неразрешимость задачи о проверке на пустоту пересечения двух КС-грамматик|Пересечение КС-грамматик]]
*[[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]
*[[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]
*[[Неразрешимость исчисления предикатов первого порядка]]
*[[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]
*[[Игра «Жизнь»]]<tex>^\star</tex>
*[[Неразрешимость игры Braid]]<tex>^\star</tex>
*[[Теорема Райса-Шапиро]]

Обсуждение участницы:Анна

2017-01-04T13:16:28Z

Анна:

Обсуждение участницы:Анна

2017-01-04T08:25:07Z

Анна:

Обсуждение участницы:Анна

2017-01-03T14:19:32Z

Анна:

{{Теорема
|statement= Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.
|proof=
Тут будет доказательство.
}}
Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров.

По двум КС-грамматикам <tex>G_1</tex> и <tex>G_2</tex> можно построить КС-грамматику для [[Замкнутость КС-языков относительно различных операций#.D0.9A.D0.BE.D0.BD.D0.BA.D0.B0.D1.82.D0.B5.D0.BD.D0.B0.D1.86.D0.B8.D1.8F|конкатенации]] задаваемых ими языков <tex>L(G_1)L(G_2)</tex>. По аналогии с этим мы можем рассматривать язык <tex>L(G_1)\#L(G_2)\#</tex>, где <tex>\#</tex> {{---}} новый символ, не встречающийся в алфавите. Заметим, что пересечение языков непусто, то есть <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex>, тогда и только тогда, когда <tex>L(G_1)\#L(G_2)\#</tex> содержит [[Алгоритм Ландау-Шмидта#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|тандемный повтор]].

Аналогично можно заметить, что пересечение <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex> тогда и только тогда, когда <tex>L(G_1)\#L(G_2)^R</tex> содержит палиндром, где обозначение <tex>L^R</tex> {{---}} разворот <tex>L</tex>.

Таким образом, мы имеем:
{{Утверждение
|statement= Пусть дана грамматика <tex>G</tex>, <tex>L(G) = L</tex>. Тогда следующие задачи неразрешимы:
# Содержит ли <tex>L</tex> тандемный повтор.
# Содержит ли <tex>L</tex> палиндром.
}}

Обсуждение участницы:Анна

2017-01-03T13:39:29Z

Анна:

{{Теорема
|statement= Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.
|proof=
Тут будет доказательство.
}}
Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров.

По двум КС-грамматикам <tex>G_1</tex> и <tex>G_2</tex> можно построить КС-грамматику для [[Замкнутость КС-языков относительно различных операций#.D0.9A.D0.BE.D0.BD.D0.BA.D0.B0.D1.82.D0.B5.D0.BD.D0.B0.D1.86.D0.B8.D1.8F|конкатенации]] задаваемых ими языков <tex>L(G_1)L(G_2)</tex>. По аналогии с этим мы можем рассматривать язык <tex>L(G_1)\#L(G_2)\#</tex>, где <tex>\#</tex> {{---}} новый символ, не встречающийся в алфавите. Заметим, что пересечение языков непусто, то есть <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex>, тогда и только тогда, когда <tex>L(G_1)\#L(G_2)\#</tex> содержит [[Алгоритм Ландау-Шмидта#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|тандемный повтор]].

Аналогично можно заметить, что пересечение <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex> тогда и только тогда, когда <tex>L(G_1)\#L(G_2)^R</tex> содержит палиндром. Таким образом, мы имеем:
{{Утверждение
|statement= Пусть дана грамматика <tex>G</tex>, <tex>L(G) = L</tex>. Тогда следующие задачи неразрешимы:
# Содержит ли <tex>L</tex> тандемный повтор.
# Содержит ли <tex>L</tex> палиндром.
}}

Обсуждение участницы:Анна

2016-12-23T22:00:44Z

Анна: Удалено содержимое страницы

Обсуждение участницы:Анна

2016-12-23T21:46:26Z

Анна:

Доказательство того, что следующие языки неразрешимы:
# <tex>A_{TM} = \{ (M, w) \mid M - </tex> машина Тьюринга, допускающая строку <tex>w \}</tex>
# <tex>L_{TM} = \{ (M, w) \mid M - </tex> машина Тьюринга, допускающая строку <tex>w^R</tex> и не допускающая строку <tex>w \}</tex>
# <tex>A\varepsilon_{TM} = \{ M \mid M - </tex> машина Тьюринга, допускающая <tex>\varepsilon \}</tex>
# <tex>R_{TM} = \{ M \mid M - </tex> машина Тьюринга и <tex>L(M) - </tex> регулярный <tex> \}</tex>
# <tex>E_{TM} = \{ M \mid M - </tex> машина Тьюринга и <tex>L(M) = \varnothing \}</tex>

Обсуждение участницы:Анна

2016-12-22T22:12:05Z

Анна: Удалено содержимое страницы

Замкнутость регулярных языков относительно различных операций

2016-12-22T22:10:06Z

Анна:

== Теорема ==
{{Теорема
|statement=
Пусть <tex>L_1, L_2</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярные языки]] над одним алфавитом <tex>\Sigma</tex>. Тогда следующие языки также являются регулярными:
#Языки, полученные путём применения следующих теоретико-множественных операций:
#*<tex>L_1 \cup L_2</tex>,
#*<tex>\overline{L_1}</tex>,
#*<tex>L_1 \cap L_2</tex>,
#*<tex>L_1 \setminus L_2</tex>;
#<tex>L_1^*</tex>;
#<tex>L_1 L_2</tex>;
#<tex>\overset{\leftarrow}{L_1}</tex>.
|proof=
Как известно, [[Теорема Клини (совпадение классов автоматных и регулярных языков|классы регулярных и автоматных языков совпадают]]. Пусть языки <tex>L_1</tex> и <tex>L_2</tex> распознаются автоматами <tex>A_1 = \langle \Sigma , Q_1 , s_1 , T_1 , \delta_1 : Q_1 \times \Sigma \rightarrow 2^{Q_1} \rangle </tex> и <tex>A_2 = \langle \Sigma , Q_2 , s_2 , T_2 , \delta_2 : Q_2 \times \Sigma \rightarrow 2^{Q_2} \rangle </tex> соответственно.
#
#*<tex>L_1 \cup L_2</tex> является регулярным по определению [[Регулярные языки: два определения и их эквивалентность|регулярных языков]].
#*Рассмотрим автомат <tex>A_1' = \langle \Sigma , Q_1 , s_1 , Q_1 \setminus T_1 , \delta_1 \rangle </tex>, то есть автомат <tex>A</tex>, в котором терминальные и нетерминальные состояния инвертированы (при таком построении следует помнить, что если в исходном автомате было опущено дьявольское состояние, его нужно явно добавить и сделать допускающим.) Очевидно, он допускает те и только те слова, которые не допускает автомат <tex>A_1</tex>, а значит, задаёт язык <tex>\overline{L_1}</tex>. Таким образом, <tex>\overline{L_1}</tex> {{---}} регулярный.
#*<tex>L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}</tex>. Тогда <tex>L_1 \cap L_2</tex> {{---}} регулярный. Также автомат для пересечения языков можно построить явно, используя конструкцию [[Прямое произведение ДКА|произведения автоматов]].
#*<tex>L_1 \setminus L_2 = L_1 \cap \overline{L_2}</tex>. Тогда <tex>L_1 \setminus L_2</tex> {{---}} регулярный.
#<tex>L_1^*</tex> является регулярным по определению [[Регулярные языки: два определения и их эквивалентность|регулярных языков]].
#<tex>L_1 L_2</tex> также является регулярным по определению [[Регулярные языки: два определения и их эквивалентность|регулярных языков]].
#Рассмотрим [[Автоматы_с_eps-переходами._Eps-замыкание|НКА c <tex>\varepsilon</tex>-переходами]] <tex>A_1' = \langle \Sigma, Q_1, s' , \lbrace s_1 \rbrace, \delta_1' \rangle </tex>, где <tex>\delta_1' (v,c) = \lbrace u | \delta_1(u,c) = v \rbrace </tex>; <tex>\delta_1'(s', \varepsilon) = \lbrace T_i \rbrace</tex>. Если в исходном автомате путь по <tex>\alpha</tex> из <tex>s_1</tex> приводил в терминальное состояние, то в новом автомате существует путь по <tex>\alpha</tex> из этого терминального состояния в <tex>s_1</tex> (и наоборот). Следовательно, этот автомат распознает в точности развернутые слова языка <tex>L_1</tex>. Тогда язык <tex>\overset{\leftarrow}{L_1}</tex> {{---}} регулярный.
}}
== Примеры доказательств ==
=== Гомоморфизм цепочек ===
{{Утверждение
|id=st1
|statement=
<tex>L \subset \Sigma_1^*</tex> {{---}} регулярный , <tex>\varphi:\Sigma_1^* \rightarrow \Sigma_2^* </tex> {{---}} [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#Гомоморфизм_языков | гомоморфизм цепочек]]. Тогда <tex>\varphi(L)</tex> {{---}} регулярный.
|proof=
Рассмотрим [[Детерминированные_конечные_автоматы|ДКА]], распознающий <tex>L</tex>. Заменим в нем все переходы по символам на переходы по их образам при гомоморфизме. Полученный автомат (с переходами по строкам) распознает в точности <tex>\varphi(L)</tex> и [[Автоматы_с_eps-переходами._Eps-замыкание|имеет эквивалентный ДКА]].
}}
{{Утверждение
|id=st2
|statement=
<tex>L \subset \Sigma_2^*</tex> {{---}} регулярный , <tex>\varphi:\Sigma_1^* \rightarrow \Sigma_2^* </tex> {{---}} [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#Гомоморфизм_языков | гомоморфизм цепочек]]. Тогда <tex>\varphi^{-1}(L)</tex> {{---}} регулярный.
|proof=
Рассмотрим [[Детерминированные_конечные_автоматы|ДКА]], распознающий <tex>L</tex>. Отследим для каждого состояния <tex>u</tex> и символа <tex>c</tex> строку <tex>\varphi(c)</tex>: <tex> \langle u,\varphi(c) \rangle \vdash^* \langle v,\varepsilon \rangle</tex> и положим <tex>\delta (u,c) = v</tex> в новом автомате (на том же множестве состояний). Автомат с построенной таким образом функцией переходов, очевидно, распознает слова языка <tex>\varphi^{-1}(L)</tex> и только их.
}}
=== Язык half(L) ===
{{Определение
|definition = Определим <tex>\mathrm{half(L)}</tex> как множество первых половин цепочек языка <tex>L</tex>, то есть множество <tex>\{ w \mid \exists x : wx \in L \land |w| = |x| \}</tex>. }}
Например, если <tex>L = \{ \varepsilon, 0010, 011, 010110 \}</tex>, то <tex>\mathrm{half(L)} = \{ \varepsilon, 00, 010 \}</tex>. Заметим, что цепочки нечетной длины не влияют на <tex>\mathrm{half(L)}</tex>.

{{Утверждение
|id = st3
|statement =
Пусть <tex>L</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярный язык]]. Тогда язык <tex>\mathrm{half(L)}</tex> также регулярен.
|proof =
Так как <tex>L</tex> {{---}} регулярный язык, то существует ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>, допускающий его. Рассмотрим строку <tex>x</tex>. Для того, чтобы проверить, что <tex>x \in \mathrm{half(L)}</tex>, нам надо убедиться, что существует строка <tex>y</tex> такой же длины, что и <tex>x</tex>, которая, будучи сконкатенированной с <tex>x</tex>, даст строку из <tex>L</tex>, то есть если на вход автомату подать <tex>xy</tex>, то в конце обработки мы окажемся в терминальном состоянии. Предположим, что автомат, закончив обработку <tex>x</tex>, находится в состоянии <tex>q_i</tex>, то есть <tex>\delta(q_0, x) = q_i</tex>. Мы должны проверить, что существует строка <tex>y, |y| = |x|,</tex> которая ведет из состояния <tex>q_i</tex> до какого-нибудь терминального состояния <tex>M</tex>, то есть <tex>\delta(q_i, y) \in F</tex>.

Предположим, что мы прошли <tex>n</tex> вершин автомата, то есть <tex>|x| = n</tex>. Обозначим за <tex>S_n</tex> множество всех состояний, с которых можно попасть в терминальные за <tex>n</tex> шагов. Тогда <tex>q_i \in S_n \Leftrightarrow x \in \mathrm{half(L)}</tex>. Если мы сможем отслеживать <tex>S_n</tex> и <tex>q_i</tex>, то сможем определять, верно ли, что <tex>x \in \mathrm{half(L)}</tex>. Заметим, что <tex>S_0 \equiv F</tex>. Очевидно мы можем построить <tex>S_{n+1}</tex> зная <tex>S_n</tex> и <tex>\delta</tex>: <tex>S_{n+1} = prev(S_n) = \{ q \in Q \mid \exists a \in \Sigma, q' \in S_n, \delta(q, a) = q' \}</tex> {{---}} множество состояний, из которых есть переход в какое-либо состояние из <tex>S_n</tex> (по единственному символу). Теперь надо найти способ отслеживать и обновлять <tex>S_n</tex>.

Построим ДКА <tex>M'</tex>, который будет хранить эту информацию в своих состояниях. Определим <tex>Q' = Q \times 2^Q</tex>, то есть каждое состояние <tex>M'</tex> {{---}} это пара из одиночного состояния из <tex>M</tex> и множества состояний из <tex>M</tex>. Функцию перехода <tex>\delta'</tex> автомата <tex>M'</tex> определим так, чтобы если по какой-то строке <tex>x</tex> длины <tex>n</tex> в автомате <tex>M</tex> мы перешли в состояние <tex>q_i</tex>, то по этой же строке в автомате <tex>M'</tex> мы перейдем в состояние <tex>(q_i, S_n)</tex>, где <tex>S_n</tex> {{---}} множество состояний из <tex>M</tex>, определенное выше. Вспомним приведенную выше функцию <tex>prev(S_n) = S_{n+1}</tex>. С ее помощью мы можем определить функцию перехода следующим образом: <tex>\delta'((q, S), a) = (\delta(q, a), prev(S))</tex>. Начальное состояние <tex>q_0' = (q_0, S_0) = (q_0, F)</tex>. Множество терминальных состояний {{---}} <tex>F' = \{ (q, S) \mid q \in S, S \in 2^Q \}</tex>.

Теперь по индукции не сложно доказать, что <tex>\delta'(q_0', x) = (\delta(q_0, x), S_n)</tex>, где <tex>|x| = n</tex>. По определению множества терминальных вершин, автомат <tex>M'</tex> допускает строку <tex>x</tex> тогда и только тогда, когда <tex>\delta(q_0, x) \in S_n</tex>. Следовательно, автомат <tex>M'</tex> допускает язык <tex>\mathrm{half(L)}</tex>.Таким образом, мы построили ДКА, который допускает язык <tex>\mathrm{half(L)}</tex>. Следовательно, данный язык является регулярным.
}}
=== Язык cycle(L) ===
{{Определение
|definition = Определим <tex>\mathrm{cycle(L)}</tex> как множество <tex>\{ w \mid </tex> цепочку <tex>w</tex> можно представить в виде <tex>w = xy</tex>, где <tex>yx \in L \}</tex>. }}
Например, если <tex>L = \{ 01, 011 \}</tex>, то <tex>\mathrm{cycle(L)} = \{ 01, 10, 011, 110, 101 \}</tex>.

{{Утверждение
|id = st5
|statement =
Пусть <tex>L</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярный язык]]. Тогда язык <tex>\mathrm{cycle(L)}</tex> также регулярен.
|proof =
[[Файл:Enfa_before.jpg|right|thumb|380px|Рис. 1. Разбиение автомата.]]
[[Файл:Enfa-after.jpg|right|thumb|380px|Рис. 2. Перестроение.]]
Так как <tex>L</tex> {{---}} регулярный язык, то существует допускающий его ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>. Построим из <tex>M</tex> [[Автоматы_с_eps-переходами._Eps-замыкание|недетерминированный автомат с <tex>\varepsilon</tex>-переходами]] следующим образом: рассмотрим состояние <tex>q \in Q</tex>, из которого есть переходы в другие состояния (то есть начиная с <tex>q</tex> можно построить непустое слово, заканчивающееся в терминальной вершине). Тогда если какое-то слово проходит через это состояние, оно может быть зациклено таким образом, что его суффикс, начинающийся с <tex>q</tex>, станет префиксом нового слова, а префикс, заканчивающийся в <tex>q</tex> {{---}} суффиксом. Разделим автомат на две части <tex>A_1</tex> и <tex>A_2</tex> такие, что <tex>A_1</tex> будет содержать все вершины, из которых достижима <tex>q</tex>, а <tex>A_2</tex> {{---}} все вершины, которые достижимы из <tex>q</tex> (см. рис. 1). Заметим, что каждая вершина может содержаться в обеих частях одновременно, такое может случиться, если автомат <tex>M</tex> содержит циклы. Теперь перестроим автомат так, что он будет принимать слова "зацикленные" вокруг <tex>q</tex>, то есть начинающиеся с <tex>q</tex> и после достижения терминальной вершины продолжающиеся с <tex>q_0</tex> (см. рис. 2). Для этого стартовой вершиной сделаем <tex>q</tex> и построим от нее часть <tex>A_2</tex>. Теперь добавим состояние <tex>q_0</tex> и соединим с ним все терминальные состояния из <tex>A_2</tex> с помощью <tex>\varepsilon</tex>-переходов. Далее построим от <tex>q_0</tex> часть <tex>A_1</tex>. Добавим вершину <tex>q'</tex>, эквивалентную <tex>q</tex>, и сделаем ее терминальной. Данный автомат принимает слова, зацикленные вокруг выбранной вершины <tex>q</tex>. Мы хотим, чтобы автомат принимал слова, зацикленные вокруг любой такой <tex>q</tex>. Для этого создадим новую стартовую вершину <tex>q_0'</tex> и свяжем ее <tex>\varepsilon</tex>-переходами со всеми перестроенными автоматами (зацикленными вокруг всех подходящих <tex>q</tex>), в том числе и с изначальным автоматом. Построенный автомат допускает язык <tex>\mathrm{cycle(L)}</tex>, следовательно, данный язык является регулярным.
}}
[[Файл:Ex_1_before.jpg|left|thumb|260px|Рис. 3. Автомат, принимающий язык <tex>L</tex>.]]
[[Файл:Ex_1_after.jpg|right|thumb|380px|Рис. 4. Автомат, принимающий язык <tex>\mathrm{cycle(L)}</tex>.]]
Для лучшего понимания алгоритма перестроения автомата рассмотрим пример.

На рис. 3 представлен автомат, допускающий язык <tex>L = \{ ab, abb, ac \}</tex>. На рис. 4 показано, как этот автомат был перестроен. Были добавлены части, зацикленные относительно вершин <tex>2</tex> и <tex>3</tex>. Появилась новая стартовая вершина <tex>0</tex>, которая связана <tex>\varepsilon</tex>-переходами с изначальным автоматом и его измененными версиями. Данный автомат распознает язык <tex>\mathrm{cycle(L)} = \{ ab, abb, ac, ba, bba, ca, bab \}</tex>: первые три слова распознает первая часть, которая совпадает с изначальным автоматом; следующие три {{---}} вторая, перестроенная относительно вершины <tex>2</tex>; последнее слово распознает третья часть, зацикленная относительно вершины <tex>3</tex>.

 

=== Язык alt(L, M) ===
{{Определение
|definition = Пусть <tex>w = w_1 w_2 \dots w_n</tex> и <tex>x = x_1 x_2 \dots x_n</tex>. Определим <tex>alternation(w, x) = w_1 x_1 w_2 x_2 \dots w_n x_n</tex>.}}
Теперь распространим это определение:
{{Определение
|definition = Пусть <tex>L</tex> и <tex>M</tex> {{---}} два языка над одним алфавитом <tex>\Sigma</tex>. Тогда <tex>\mathrm{alt(L, M)} = \{ alternation(w, x) \mid |w| = |x|, w \in L, x \in M \}</tex>.}}
Например, если <tex>L = \{ 10, 00, 111, 1001 \}</tex> и <tex>M = \{ 11, 0101 \}</tex>, то <tex>\mathrm{alt(L, M)} = \{ 1101, 0101, 10010011 \}</tex>.

{{Утверждение
|id = st4
|statement = Пусть <tex>L</tex> и <tex>M</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярные языки]]. Тогда <tex>\mathrm{alt(L, M)}</tex> также является регулярным.
|proof = Так как <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки, то существуют ДКА <tex>D_L = \langle \Sigma , Q_L , q_{0L} , F_L, \delta_L \rangle</tex>, распознающий язык <tex>L</tex>, и <tex>D_M = \langle \Sigma , Q_M , q_{0M} , F_M, \delta_M \rangle</tex>, распознающий язык <tex>M</tex>. Построим автомат <tex>D_{alt}</tex>, который будет распознавать язык <tex>\mathrm{alt(L, M)}</tex>. Идея следующая: каждое состояние этого автомата будем описывать тремя значениями <tex>(p, q, b)</tex>, где <tex>p \in Q_L</tex>, <tex>q \in Q_M</tex> и <tex>b \in \{ 1, 0 \}</tex>. Нам нужно организовать чередование переходов по состояниям автоматов, то есть если мы на определенном шаге перешли от одного состояния автомата <tex>D_L</tex> до другого, то на следующем мы обязаны совершить переход по состояниям автомата <tex>D_M</tex>. Для этого нам нужно обновлять состояние одного автомата и при этом сохранять состояние другого для следующего перехода. Тут мы будем использовать третье значение: если <tex>b = 0</tex>, то будет двигаться по состояниям первого автомата, то есть значение <tex>p</tex> при переходе в новое состояние автомата <tex>D_{alt}</tex> поменяется, <tex>q</tex> останется неизменной, <tex>b</tex> станет <tex>1</tex>, если <tex>b = 1</tex>, то, соответственно, все наоборот. То есть у нас будут две функции перехода, выбирать нужную будем в зависимости от четности третьего параметра. Важно, что на каждом шаге мы инвертируем значение <tex>b</tex>, что гарантирует чередование. Определим автомат <tex>D_{alt} = \langle \Sigma, Q', q_0', F', \delta' \rangle</tex> следующим образом:
# <tex>Q' = Q_L \times Q_M \times \{ 0, 1 \}</tex>
# <tex>q_0' = (q_{0L}, q_{0M}, 0)</tex>
# <tex>F' = F_L \times F_M \times \{ 0 \}</tex>
# <tex>\delta'((p, q, 0), a) = (\delta_L(p, a), q, 1)</tex> и <tex>\delta'((p, q, 1), a) = (p, \delta_M(q, a), 0)</tex>
Стартовая вершина имеет третий параметр <tex>b = 0</tex>, так как первое значение должно быть получено из автомата <tex>D_L</tex>. Аналогично все терминальные вершины должны иметь то же значение последнего параметра, так как количество переходов должно быть четным и последний переход должен был быть осуществлен по автомату <tex>D_M</tex>. Функция перехода <tex>\delta'</tex> использует <tex>\delta_L</tex> для получения нечетных символов и <tex>\delta_M</tex> для четных. Таким образом, <tex>D_{alt}</tex> состоит из чередующихся символов <tex>D_L</tex> и <tex>D_M</tex>. При этом <tex>D_{alt}</tex> принимает <tex>w</tex> тогда и только тогда, когда <tex>D_L</tex> последовательно принимает все нечетные символы <tex>w</tex> и <tex>D_M</tex> {{---}} все четные, а так же <tex>w</tex> имеет четную длину. Следовательно, <tex>D_{alt}</tex> распознает язык <tex>\mathrm{alt(L, M)}</tex>, что доказывает, что <tex>\mathrm{alt(L, M)}</tex> является регулярным.
}}
[[Файл:Alt ex 1.jpg|left|thumb|265px|Рис. 5. Автоматы для языков <tex>L</tex> и <tex>M</tex>.]]
[[Файл:Alt ex 2.jpg|right|thumb|390px|Рис. 6. Автомат, принимающий язык <tex>\mathrm{alt(L, M)}</tex>.]]
Чтобы более наглядно показать, как строится автомат <tex>D_{alt}</tex>, разберем пример. Пусть <tex>L = \{ 1, 11 \}</tex> и <tex>M = \{ 00 \}</tex> (см. рис. 5). Все состояния нового автомата представлены на рис. 6. Стартовая вершина <tex>q_0' = (1, 1, 0)</tex>, множество терминальных вершин {{---}} <tex>F' = \{ (2, 3, 0), (3, 3, 0) \}</tex>. Мы видим, что построенные по функции <tex>\delta'</tex> переходы на каждом шаге меняют состояние одного из автоматов, а именно того, по которому происходит переход, сохраняя состояние другого для следующего шага. Таким образом, каждый следующий символ получен из автомата, отличного от того, что был использован на предыдущем шаге. Декартово произведение состояний гарантирует, что мы рассмотрим все состояния и переходы изначальных автоматов. Для данного примера мы получаем, что <tex>\mathrm{alt(L, M)} = \{ 1010 \}</tex>.

 

== См. также ==
* [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]
* [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]

== Источники ==
* Хопкрофт Д., Мотвани Р., Ульман Д. "Введение в теорию автоматов, языков и вычислений", 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. {{---}} С. 149 — ISBN 5-8459-0261-4
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
[[Категория: Свойства конечных автоматов]]

Замкнутость регулярных языков относительно различных операций

2016-12-22T22:08:42Z

Анна:

== Теорема ==
{{Теорема
|statement=
Пусть <tex>L_1, L_2</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярные языки]] над одним алфавитом <tex>\Sigma</tex>. Тогда следующие языки также являются регулярными:
#Языки, полученные путём применения следующих теоретико-множественных операций:
#*<tex>L_1 \cup L_2</tex>,
#*<tex>\overline{L_1}</tex>,
#*<tex>L_1 \cap L_2</tex>,
#*<tex>L_1 \setminus L_2</tex>;
#<tex>L_1^*</tex>;
#<tex>L_1 L_2</tex>;
#<tex>\overset{\leftarrow}{L_1}</tex>.
|proof=
Как известно, [[Теорема Клини (совпадение классов автоматных и регулярных языков|классы регулярных и автоматных языков совпадают]]. Пусть языки <tex>L_1</tex> и <tex>L_2</tex> распознаются автоматами <tex>A_1 = \langle \Sigma , Q_1 , s_1 , T_1 , \delta_1 : Q_1 \times \Sigma \rightarrow 2^{Q_1} \rangle </tex> и <tex>A_2 = \langle \Sigma , Q_2 , s_2 , T_2 , \delta_2 : Q_2 \times \Sigma \rightarrow 2^{Q_2} \rangle </tex> соответственно.
#
#*<tex>L_1 \cup L_2</tex> является регулярным по определению [[Регулярные языки: два определения и их эквивалентность|регулярных языков]].
#*Рассмотрим автомат <tex>A_1' = \langle \Sigma , Q_1 , s_1 , Q_1 \setminus T_1 , \delta_1 \rangle </tex>, то есть автомат <tex>A</tex>, в котором терминальные и нетерминальные состояния инвертированы (при таком построении следует помнить, что если в исходном автомате было опущено дьявольское состояние, его нужно явно добавить и сделать допускающим.) Очевидно, он допускает те и только те слова, которые не допускает автомат <tex>A_1</tex>, а значит, задаёт язык <tex>\overline{L_1}</tex>. Таким образом, <tex>\overline{L_1}</tex> {{---}} регулярный.
#*<tex>L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}</tex>. Тогда <tex>L_1 \cap L_2</tex> {{---}} регулярный. Также автомат для пересечения языков можно построить явно, используя конструкцию [[Прямое произведение ДКА|произведения автоматов]].
#*<tex>L_1 \setminus L_2 = L_1 \cap \overline{L_2}</tex>. Тогда <tex>L_1 \setminus L_2</tex> {{---}} регулярный.
#<tex>L_1^*</tex> является регулярным по определению [[Регулярные языки: два определения и их эквивалентность|регулярных языков]].
#<tex>L_1 L_2</tex> также является регулярным по определению [[Регулярные языки: два определения и их эквивалентность|регулярных языков]].
#Рассмотрим [[Автоматы_с_eps-переходами._Eps-замыкание|НКА c <tex>\varepsilon</tex>-переходами]] <tex>A_1' = \langle \Sigma, Q_1, s' , \lbrace s_1 \rbrace, \delta_1' \rangle </tex>, где <tex>\delta_1' (v,c) = \lbrace u | \delta_1(u,c) = v \rbrace </tex>; <tex>\delta_1'(s', \varepsilon) = \lbrace T_i \rbrace</tex>. Если в исходном автомате путь по <tex>\alpha</tex> из <tex>s_1</tex> приводил в терминальное состояние, то в новом автомате существует путь по <tex>\alpha</tex> из этого терминального состояния в <tex>s_1</tex> (и наоборот). Следовательно, этот автомат распознает в точности развернутые слова языка <tex>L_1</tex>. Тогда язык <tex>\overset{\leftarrow}{L_1}</tex> {{---}} регулярный.
}}
== Примеры доказательств ==
=== Гомоморфизм цепочек ===
{{Утверждение
|id=st1
|statement=
<tex>L \subset \Sigma_1^*</tex> {{---}} регулярный , <tex>\varphi:\Sigma_1^* \rightarrow \Sigma_2^* </tex> {{---}} [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#Гомоморфизм_языков | гомоморфизм цепочек]]. Тогда <tex>\varphi(L)</tex> {{---}} регулярный.
|proof=
Рассмотрим [[Детерминированные_конечные_автоматы|ДКА]], распознающий <tex>L</tex>. Заменим в нем все переходы по символам на переходы по их образам при гомоморфизме. Полученный автомат (с переходами по строкам) распознает в точности <tex>\varphi(L)</tex> и [[Автоматы_с_eps-переходами._Eps-замыкание|имеет эквивалентный ДКА]].
}}
{{Утверждение
|id=st2
|statement=
<tex>L \subset \Sigma_2^*</tex> {{---}} регулярный , <tex>\varphi:\Sigma_1^* \rightarrow \Sigma_2^* </tex> {{---}} [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#Гомоморфизм_языков | гомоморфизм цепочек]]. Тогда <tex>\varphi^{-1}(L)</tex> {{---}} регулярный.
|proof=
Рассмотрим [[Детерминированные_конечные_автоматы|ДКА]], распознающий <tex>L</tex>. Отследим для каждого состояния <tex>u</tex> и символа <tex>c</tex> строку <tex>\varphi(c)</tex>: <tex> \langle u,\varphi(c) \rangle \vdash^* \langle v,\varepsilon \rangle</tex> и положим <tex>\delta (u,c) = v</tex> в новом автомате (на том же множестве состояний). Автомат с построенной таким образом функцией переходов, очевидно, распознает слова языка <tex>\varphi^{-1}(L)</tex> и только их.
}}
=== Язык half(L) ===
{{Определение
|definition = Определим <tex>\mathrm{half(L)}</tex> как множество первых половин цепочек языка <tex>L</tex>, то есть множество <tex>\{ w \mid \exists x : wx \in L \land |w| = |x| \}</tex>. }}
Например, если <tex>L = \{ \varepsilon, 0010, 011, 010110 \}</tex>, то <tex>\mathrm{half(L)} = \{ \varepsilon, 00, 010 \}</tex>. Заметим, что цепочки нечетной длины не влияют на <tex>\mathrm{half(L)}</tex>.

{{Утверждение
|id = st3
|statement =
Пусть <tex>L</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярный язык]]. Тогда язык <tex>\mathrm{half(L)}</tex> также регулярен.
|proof =
Так как <tex>L</tex> {{---}} регулярный язык, то существует ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>, допускающий его. Рассмотрим строку <tex>x</tex>. Для того, чтобы проверить, что <tex>x \in \mathrm{half(L)}</tex>, нам надо убедиться, что существует строка <tex>y</tex> такой же длины, что и <tex>x</tex>, которая, будучи сконкатенированной с <tex>x</tex>, даст строку из <tex>L</tex>, то есть если на вход автомату подать <tex>xy</tex>, то в конце обработки мы окажемся в терминальном состоянии. Предположим, что автомат, закончив обработку <tex>x</tex>, находится в состоянии <tex>q_i</tex>, то есть <tex>\delta(q_0, x) = q_i</tex>. Мы должны проверить, что существует строка <tex>y, |y| = |x|,</tex> которая ведет из состояния <tex>q_i</tex> до какого-нибудь терминального состояния <tex>M</tex>, то есть <tex>\delta(q_i, y) \in F</tex>.

Предположим, что мы прошли <tex>n</tex> вершин автомата, то есть <tex>|x| = n</tex>. Обозначим за <tex>S_n</tex> множество всех состояний, с которых можно попасть в терминальные за <tex>n</tex> шагов. Тогда <tex>q_i \in S_n \Leftrightarrow x \in \mathrm{half(L)}</tex>. Если мы сможем отслеживать <tex>S_n</tex> и <tex>q_i</tex>, то сможем определять, верно ли, что <tex>x \in \mathrm{half(L)}</tex>. Заметим, что <tex>S_0 \equiv F</tex>. Очевидно мы можем построить <tex>S_{n+1}</tex> зная <tex>S_n</tex> и <tex>\delta</tex>: <tex>S_{n+1} = prev(S_n) = \{ q \in Q \mid \exists a \in \Sigma, q' \in S_n, \delta(q, a) = q' \}</tex> {{---}} множество состояний, из которых есть переход в какое-либо состояние из <tex>S_n</tex> (по единственному символу). Теперь надо найти способ отслеживать и обновлять <tex>S_n</tex>.

Построим ДКА <tex>M'</tex>, который будет хранить эту информацию в своих состояниях. Определим <tex>Q' = Q \times 2^Q</tex>, то есть каждое состояние <tex>M'</tex> {{---}} это пара из одиночного состояния из <tex>M</tex> и множества состояний из <tex>M</tex>. Функцию перехода <tex>\delta'</tex> автомата <tex>M'</tex> определим так, чтобы если по какой-то строке <tex>x</tex> длины <tex>n</tex> в автомате <tex>M</tex> мы перешли в состояние <tex>q_i</tex>, то по этой же строке в автомате <tex>M'</tex> мы перейдем в состояние <tex>(q_i, S_n)</tex>, где <tex>S_n</tex> {{---}} множество состояний из <tex>M</tex>, определенное выше. Вспомним приведенную выше функцию <tex>prev(S_n) = S_{n+1}</tex>. С ее помощью мы можем определить функцию перехода следующим образом: <tex>\delta'((q, S), a) = (\delta(q, a), prev(S))</tex>. Начальное состояние <tex>q_0' = (q_0, S_0) = (q_0, F)</tex>. Множество терминальных состояний {{---}} <tex>F' = \{ (q, S) \mid q \in S, S \in 2^Q \}</tex>.

Теперь по индукции не сложно доказать, что <tex>\delta'(q_0', x) = (\delta(q_0, x), S_n)</tex>, где <tex>|x| = n</tex>. По определению множества терминальных вершин, автомат <tex>M'</tex> допускает строку <tex>x</tex> тогда и только тогда, когда <tex>\delta(q_0, x) \in S_n</tex>. Следовательно, автомат <tex>M'</tex> допускает язык <tex>\mathrm{half(L)}</tex>.Таким образом, мы построили ДКА, который допускает язык <tex>\mathrm{half(L)}</tex>. Следовательно, данный язык является регулярным.
}}
=== Язык cycle(L) ===
{{Определение
|definition = Определим <tex>\mathrm{cycle(L)}</tex> как множество <tex>\{ w \mid </tex> цепочку <tex>w</tex> можно представить в виде <tex>w = xy</tex>, где <tex>yx \in L \}</tex>. }}
Например, если <tex>L = \{ 01, 011 \}</tex>, то <tex>\mathrm{cycle(L)} = \{ 01, 10, 011, 110, 101 \}</tex>.

{{Утверждение
|id = st5
|statement =
Пусть <tex>L</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярный язык]]. Тогда язык <tex>\mathrm{cycle(L)}</tex> также регулярен.
|proof =
[[Файл:Enfa_before.jpg|right|thumb|380px|Рис. 1. Разбиение автомата.]]
[[Файл:Enfa-after.jpg|right|thumb|380px|Рис. 2. Перестроение.]]
Так как <tex>L</tex> {{---}} регулярный язык, то существует допускающий его ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>. Построим из <tex>M</tex> [[Автоматы_с_eps-переходами._Eps-замыкание|недетерминированный автомат с <tex>\varepsilon</tex>-переходами]] следующим образом: рассмотрим состояние <tex>q \in Q</tex>, из которого есть переходы в другие состояния (то есть начиная с <tex>q</tex> можно построить непустое слово, заканчивающееся в терминальной вершине). Тогда если какое-то слово проходит через это состояние, оно может быть зациклено таким образом, что его суффикс, начинающийся с <tex>q</tex>, станет префиксом нового слова, а префикс, заканчивающийся в <tex>q</tex> {{---}} суффиксом. Разделим автомат на две части <tex>A_1</tex> и <tex>A_2</tex> такие, что <tex>A_1</tex> будет содержать все вершины, из которых достижима <tex>q</tex>, а <tex>A_2</tex> {{---}} все вершины, которые достижимы из <tex>q</tex> (см. рис. 1). Заметим, что каждая вершина может содержаться в обеих частях одновременно, такое может случиться, если автомат <tex>M</tex> содержит циклы. Теперь перестроим автомат так, что он будет принимать слова "зацикленные" вокруг <tex>q</tex>, то есть начинающиеся с <tex>q</tex> и после достижения терминальной вершины продолжающиеся с <tex>q_0</tex> (см. рис. 2). Для этого стартовой вершиной сделаем <tex>q</tex> и построим от нее часть <tex>A_2</tex>. Теперь добавим состояние <tex>q_0</tex> и соединим с ним все терминальные состояния из <tex>A_2</tex> с помощью <tex>\varepsilon</tex>-переходов. Далее построим от <tex>q_0</tex> часть <tex>A_1</tex>. Добавим вершину <tex>q'</tex>, эквивалентную <tex>q</tex>, и сделаем ее терминальной. Данный автомат принимает слова, зацикленные вокруг выбранной вершины <tex>q</tex>. Мы хотим, чтобы автомат принимал слова, зацикленные вокруг любой такой <tex>q</tex>. Для этого создадим новую стартовую вершину <tex>q_0'</tex> и свяжем ее <tex>\varepsilon</tex>-переходами со всеми перестроенными автоматами (зацикленными вокруг всех подходящих <tex>q</tex>), в том числе и с изначальным автоматом. Построенный автомат допускает язык <tex>\mathrm{cycle(L)}</tex>, следовательно, данный язык является регулярным.
}}
[[Файл:Ex_1_before.jpg|left|thumb|260px|Рис. 3. Автомат, принимающий язык <tex>L</tex>.]]
[[Файл:Ex_1_after.jpg|right|thumb|380px|Рис. 4. Автомат, принимающий язык <tex>\mathrm{cycle(L)}</tex>.]]
Для лучшего понимания алгоритма перестроения автомата рассмотрим пример.

На рис. 3 представлен автомат, допускающий язык <tex>L = \{ ab, abb, ac \}</tex>. На рис. 4 показано, как этот автомат был перестроен. Были добавлены части, зацикленные относительно вершин <tex>2</tex> и <tex>3</tex>. Появилась новая стартовая вершина <tex>0</tex>, которая связана <tex>\varepsilon</tex>-переходами с изначальным автоматом и его измененными версиями. Данный автомат распознает язык <tex>\mathrm{cycle(L)} = \{ ab, abb, ac, ba, bba, ca, bab \}</tex>: первые три слова распознает первая часть, которая совпадает с изначальным автоматом; следующие три {{---}} вторая, перестроенная относительно вершины <tex>2</tex>; последнее слово распознает третья часть, зацикленная относительно вершины <tex>3</tex>.

 

=== Язык alt(L, M) ===
{{Определение
|definition = Пусть <tex>w = w_1 w_2 \dots w_n</tex> и <tex>x = x_1 x_2 \dots x_n</tex>. Определим <tex>alternation(w, x) = w_1 x_1 w_2 x_2 \dots w_n x_n</tex>.}}
Теперь распространим это определение:
{{Определение
|definition = Пусть <tex>L</tex> и <tex>M</tex> {{---}} два языка над одним алфавитом <tex>\Sigma</tex>. Тогда <tex>\mathrm{alt(L, M)} = \{ alternation(w, x) \mid |w| = |x|, w \in L, x \in M \}</tex>.}}
Например, если <tex>L = \{ 10, 00, 111, 1001 \}</tex> и <tex>M = \{ 11, 0101 \}</tex>, то <tex>\mathrm{alt(L, M)} = \{ 1101, 0101, 10010011 \}</tex>.

{{Утверждение
|id = st4
|statement = Пусть <tex>L</tex> и <tex>M</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярные языки]]. Тогда <tex>\mathrm{alt(L, M)}</tex> также является регулярным.
|proof = Так как <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки, то существуют ДКА <tex>D_L = \langle \Sigma , Q_L , q_{0L} , F_L, \delta_L \rangle</tex>, распознающий язык <tex>L</tex>, и <tex>D_M = \langle \Sigma , Q_M , q_{0M} , F_M, \delta_M \rangle</tex>, распознающий язык <tex>M</tex>. Построим автомат <tex>D_{alt}</tex>, который будет распознавать язык <tex>\mathrm{alt(L, M)}</tex>. Идея следующая: каждое состояние этого автомата будем описывать тремя значениями <tex>(p, q, b)</tex>, где <tex>p \in Q_L</tex>, <tex>q \in Q_M</tex> и <tex>b \in \{ 1, 0 \}</tex>. Нам нужно организовать чередование переходов по состояниям автоматов, то есть если мы на определенном шаге перешли от одного состояния автомата <tex>D_L</tex> до другого, то на следующем мы обязаны совершить переход по состояниям автомата <tex>D_M</tex>. Для этого нам нужно обновлять состояние одного автомата и при этом сохранять состояние другого для следующего перехода. Тут мы будем использовать третье значение: если <tex>b = 0</tex>, то будет двигаться по состояниям первого автомата, то есть значение <tex>p</tex> при переходе в новое состояние автомата <tex>D_{alt}</tex> поменяется, <tex>q</tex> останется неизменной, <tex>b</tex> станет <tex>1</tex>, если <tex>b = 1</tex>, то, соответственно, все наоборот. То есть у нас будут две функции перехода, выбирать нужную будем в зависимости от четности третьего параметра. Важно, что на каждом шаге мы инвертируем значение <tex>b</tex>, что гарантирует чередование. Определим автомат <tex>D_{alt} = \langle \Sigma, Q', q_0', F', \delta' \rangle</tex> следующим образом:
# <tex>Q' = Q_L \times Q_M \times \{ 0, 1 \}</tex>
# <tex>q_0' = (q_{0L}, q_{0M}, 0)</tex>
# <tex>F' = F_L \times F_M \times \{ 0 \}</tex>
# <tex>\delta'((p, q, 0), a) = (\delta_L(p, a), q, 1)</tex> и <tex>\delta'((p, q, 1), a) = (p, \delta_M(q, a), 0)</tex>
Стартовая вершина имеет третий параметр <tex>b = 0</tex>, так как первое значение должно быть получено из автомата <tex>D_L</tex>. Аналогично все терминальные вершины должны иметь то же значение последнего параметра, так как количество переходов должно быть четным и последний переход должен был быть осуществлен по автомату <tex>D_M</tex>. Функция перехода <tex>\delta'</tex> использует <tex>\delta_L</tex> для получения нечетных символов и <tex>\delta_M</tex> для четных. Таким образом, <tex>D_{alt}</tex> состоит из чередующихся символов <tex>D_L</tex> и <tex>D_M</tex>. При этом <tex>D_{alt}</tex> принимает <tex>w</tex> тогда и только тогда, когда <tex>D_L</tex> последовательно принимает все нечетные символы <tex>w</tex> и <tex>D_M</tex> {{---}} все четные, а так же <tex>w</tex> имеет четную длину. Следовательно, <tex>D_{alt}</tex> распознает язык <tex>\mathrm{alt(L, M)}</tex>, что доказывает, что <tex>\mathrm{alt(L, M)}</tex> является регулярным.
}}
[[Файл:Alt ex 1.jpg|left|thumb|265px|Рис. 5. Автоматы для языков <tex>L</tex> и <tex>M</tex>.]]
[[Файл:Alt ex 2.jpg|right|thumb|390px|Рис. 6. Автомат, принимающий язык <tex>\mathrm{alt(L, M)}</tex>.]]
Чтобы более наглядно показать, как строится автомат <tex>D_{alt}</tex>, разберем пример. Пусть <tex>L = \{ 1, 11 \}</tex> и <tex>M = \{ 00 \}</tex> (см. рис. 5). Все состояния нового автомата представлены на рис. 6. Стартовая вершина <tex>q_0' = (1, 1, 0)</tex>, множество терминальных вершин {{---}} <tex>F' = \{ (2, 3, 0), (3, 3, 0) \}</tex>. Мы видим, что построенные по функции <tex>\delta'</tex> переходы на каждом шаге меняют состояние одного из автоматов, а именно того, по которому происходит переход, сохраняя состояние другого для следующего шага. Таким образом, каждый следующий символ получен из автомата, отличного от того, что был использован на предыдущем шаге. Декартово произведение состояний гарантирует, что мы рассмотрим все состояния и переходы изначальных автоматов. Для данного примера мы получаем, что <tex>\mathrm{alt(L, M)} = \{ 1010 \}</tex>.
== См. также ==
* [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]
* [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]

== Источники ==
* Хопкрофт Д., Мотвани Р., Ульман Д. "Введение в теорию автоматов, языков и вычислений", 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. {{---}} С. 149 — ISBN 5-8459-0261-4
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
[[Категория: Свойства конечных автоматов]]

Замкнутость регулярных языков относительно различных операций

2016-12-22T21:16:54Z

Анна:

== Теорема ==
{{Теорема
|statement=
Пусть <tex>L_1, L_2</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярные языки]] над одним алфавитом <tex>\Sigma</tex>. Тогда следующие языки также являются регулярными:
#Языки, полученные путём применения следующих теоретико-множественных операций:
#*<tex>L_1 \cup L_2</tex>,
#*<tex>\overline{L_1}</tex>,
#*<tex>L_1 \cap L_2</tex>,
#*<tex>L_1 \setminus L_2</tex>;
#<tex>L_1^*</tex>;
#<tex>L_1 L_2</tex>;
#<tex>\overset{\leftarrow}{L_1}</tex>.
|proof=
Как известно, [[Теорема Клини (совпадение классов автоматных и регулярных языков|классы регулярных и автоматных языков совпадают]]. Пусть языки <tex>L_1</tex> и <tex>L_2</tex> распознаются автоматами <tex>A_1 = \langle \Sigma , Q_1 , s_1 , T_1 , \delta_1 : Q_1 \times \Sigma \rightarrow 2^{Q_1} \rangle </tex> и <tex>A_2 = \langle \Sigma , Q_2 , s_2 , T_2 , \delta_2 : Q_2 \times \Sigma \rightarrow 2^{Q_2} \rangle </tex> соответственно.
#
#*<tex>L_1 \cup L_2</tex> является регулярным по определению [[Регулярные языки: два определения и их эквивалентность|регулярных языков]].
#*Рассмотрим автомат <tex>A_1' = \langle \Sigma , Q_1 , s_1 , Q_1 \setminus T_1 , \delta_1 \rangle </tex>, то есть автомат <tex>A</tex>, в котором терминальные и нетерминальные состояния инвертированы (при таком построении следует помнить, что если в исходном автомате было опущено дьявольское состояние, его нужно явно добавить и сделать допускающим.) Очевидно, он допускает те и только те слова, которые не допускает автомат <tex>A_1</tex>, а значит, задаёт язык <tex>\overline{L_1}</tex>. Таким образом, <tex>\overline{L_1}</tex> {{---}} регулярный.
#*<tex>L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}</tex>. Тогда <tex>L_1 \cap L_2</tex> {{---}} регулярный. Также автомат для пересечения языков можно построить явно, используя конструкцию [[Прямое произведение ДКА|произведения автоматов]].
#*<tex>L_1 \setminus L_2 = L_1 \cap \overline{L_2}</tex>. Тогда <tex>L_1 \setminus L_2</tex> {{---}} регулярный.
#<tex>L_1^*</tex> является регулярным по определению [[Регулярные языки: два определения и их эквивалентность|регулярных языков]].
#<tex>L_1 L_2</tex> также является регулярным по определению [[Регулярные языки: два определения и их эквивалентность|регулярных языков]].
#Рассмотрим [[Автоматы_с_eps-переходами._Eps-замыкание|НКА c <tex>\varepsilon</tex>-переходами]] <tex>A_1' = \langle \Sigma, Q_1, s' , \lbrace s_1 \rbrace, \delta_1' \rangle </tex>, где <tex>\delta_1' (v,c) = \lbrace u | \delta_1(u,c) = v \rbrace </tex>; <tex>\delta_1'(s', \varepsilon) = \lbrace T_i \rbrace</tex>. Если в исходном автомате путь по <tex>\alpha</tex> из <tex>s_1</tex> приводил в терминальное состояние, то в новом автомате существует путь по <tex>\alpha</tex> из этого терминального состояния в <tex>s_1</tex> (и наоборот). Следовательно, этот автомат распознает в точности развернутые слова языка <tex>L_1</tex>. Тогда язык <tex>\overset{\leftarrow}{L_1}</tex> {{---}} регулярный.
}}
== Примеры доказательств ==
=== Гомоморфизм цепочек ===
{{Утверждение
|id=st1
|statement=
<tex>L \subset \Sigma_1^*</tex> {{---}} регулярный , <tex>\varphi:\Sigma_1^* \rightarrow \Sigma_2^* </tex> {{---}} [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#Гомоморфизм_языков | гомоморфизм цепочек]]. Тогда <tex>\varphi(L)</tex> {{---}} регулярный.
|proof=
Рассмотрим [[Детерминированные_конечные_автоматы|ДКА]], распознающий <tex>L</tex>. Заменим в нем все переходы по символам на переходы по их образам при гомоморфизме. Полученный автомат (с переходами по строкам) распознает в точности <tex>\varphi(L)</tex> и [[Автоматы_с_eps-переходами._Eps-замыкание|имеет эквивалентный ДКА]].
}}
{{Утверждение
|id=st2
|statement=
<tex>L \subset \Sigma_2^*</tex> {{---}} регулярный , <tex>\varphi:\Sigma_1^* \rightarrow \Sigma_2^* </tex> {{---}} [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#Гомоморфизм_языков | гомоморфизм цепочек]]. Тогда <tex>\varphi^{-1}(L)</tex> {{---}} регулярный.
|proof=
Рассмотрим [[Детерминированные_конечные_автоматы|ДКА]], распознающий <tex>L</tex>. Отследим для каждого состояния <tex>u</tex> и символа <tex>c</tex> строку <tex>\varphi(c)</tex>: <tex> \langle u,\varphi(c) \rangle \vdash^* \langle v,\varepsilon \rangle</tex> и положим <tex>\delta (u,c) = v</tex> в новом автомате (на том же множестве состояний). Автомат с построенной таким образом функцией переходов, очевидно, распознает слова языка <tex>\varphi^{-1}(L)</tex> и только их.
}}
=== Язык half(L) ===
{{Определение
|definition = Определим <tex>\mathrm{half(L)}</tex> как множество первых половин цепочек языка <tex>L</tex>, то есть множество <tex>\{ w \mid </tex> существует <tex>x</tex>, для которой <tex>wx \in L</tex>, причем <tex>|w| = |x| \}</tex>. }}
Например, если <tex>L = \{ \varepsilon, 0010, 011, 010110 \}</tex>, то <tex>\mathrm{half(L)} = \{ \varepsilon, 00, 010 \}</tex>. Заметим, что цепочки нечетной длины не влияют на <tex>\mathrm{half(L)}</tex>.

{{Утверждение
|id = st3
|statement =
Пусть <tex>L</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярный язык]]. Тогда язык <tex>\mathrm{half(L)}</tex> также регулярен.
|proof =
Так как <tex>L</tex> {{---}} регулярный язык, то существует ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>, допускающий его. Рассмотрим строку <tex>x</tex>. Для того, чтобы проверить, что <tex>x \in \mathrm{half(L)}</tex>, нам надо убедиться, что существует строка <tex>y</tex> такой же длины, что и <tex>x</tex>, которая, будучи сконкатенированной с <tex>x</tex>, даст строку из <tex>L</tex>, то есть если на вход автомату подать <tex>xy</tex>, то в конце обработки мы окажемся в терминальном состоянии. Предположим, что автомат, закончив обработку <tex>x</tex>, находится в состоянии <tex>q_i</tex>, то есть <tex>\delta(q_0, x) = q_i</tex>. Мы должны проверить, что существует строка <tex>y, |y| = |x|,</tex> которая ведет из состояния <tex>q_i</tex> до какого-нибудь терминального состояния <tex>M</tex>, то есть <tex>\delta(q_i, y) \in F</tex>.

Предположим, что мы прошли <tex>n</tex> вершин автомата, то есть <tex>|x| = n</tex>. Обозначим за <tex>S_n</tex> множество всех состояний, с которых можно попасть в терминальные за <tex>n</tex> шагов. Тогда <tex>q_i \in S_n \Leftrightarrow x \in \mathrm{half(L)}</tex>. Если мы сможем отслеживать <tex>S_n</tex> и <tex>q_i</tex>, то сможем определять, верно ли, что <tex>x \in \mathrm{half(L)}</tex>. Заметим, что <tex>S_0 \equiv F</tex>. Очевидно мы можем построить <tex>S_{n+1}</tex> зная <tex>S_n</tex> и <tex>\delta</tex>: <tex>S_{n+1} = prev(S_n) = \{ q \in Q \mid \exists a \in \Sigma, q' \in S_n, \delta(q, a) = q' \}</tex> {{---}} множество состояний, из которых есть переход в какое-либо состояние из <tex>S_n</tex> (по единственному символу). Теперь надо найти способ отслеживать и обновлять <tex>S_n</tex>.

Построим ДКА <tex>M'</tex>, который будет хранить эту информацию в своих состояниях. Определим <tex>Q' = Q \times 2^Q</tex>, то есть каждое состояние <tex>M'</tex> {{---}} это пара из одиночного состояния из <tex>M</tex> и множества состояний из <tex>M</tex>. Функцию перехода <tex>\delta'</tex> автомата <tex>M'</tex> определим так, чтобы если по какой-то строке <tex>x</tex> длины <tex>n</tex> в автомате <tex>M</tex> мы перешли в состояние <tex>q_i</tex>, то по этой же строке в автомате <tex>M'</tex> мы перейдем в состояние <tex>(q_i, S_n)</tex>, где <tex>S_n</tex> {{---}} множество состояний из <tex>M</tex>, определенное выше. Вспомним приведенную выше функцию <tex>prev(S_n) = S_{n+1}</tex>. С ее помощью мы можем определить функцию перехода следующим образом: <tex>\delta'((q, S), a) = (\delta(q, a), prev(S))</tex>. Начальное состояние <tex>q_0' = (q_0, S_0) = (q_0, F)</tex>. Множество терминальных состояний {{---}} <tex>F' = \{ (q, S) \mid q \in S, S \in 2^Q \}</tex>.

Теперь по индукции не сложно доказать, что <tex>\delta'(q_0', x) = (\delta(q_0, x), S_n)</tex>, где <tex>|x| = n</tex>. По определению множества терминальных вершин, автомат <tex>M'</tex> допускает строку <tex>x</tex> тогда и только тогда, когда <tex>\delta(q_0, x) \in S_n</tex>. Следовательно, автомат <tex>M'</tex> допускает язык <tex>\mathrm{half(L)}</tex>.Таким образом, мы построили ДКА, который допускает язык <tex>\mathrm{half(L)}</tex>. Следовательно, данный язык является регулярным.
}}
=== Язык cycle(L) ===
{{Определение
|definition = Определим <tex>\mathrm{cycle(L)}</tex> как множество <tex>\{ w \mid </tex> цепочку <tex>w</tex> можно представить в виде <tex>w = xy</tex>, где <tex>yx \in L \}</tex>. }}
Например, если <tex>L = \{ 01, 011 \}</tex>, то <tex>\mathrm{cycle(L)} = \{ 01, 10, 011, 110, 101 \}</tex>.

{{Утверждение
|id = st5
|statement =
Пусть <tex>L</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярный язык]]. Тогда язык <tex>\mathrm{cycle(L)}</tex> также регулярен.
|proof =
[[Файл:Enfa_before.jpg|right|thumb|380px|Рис. 1. Разбиение автомата.]]
[[Файл:Enfa-after.jpg|right|thumb|380px|Рис. 2. Перестроение.]]
Так как <tex>L</tex> {{---}} регулярный язык, то существует допускающий его ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>. Построим из <tex>M</tex> [[Автоматы_с_eps-переходами._Eps-замыкание|недетерминированный автомат с <tex>\varepsilon-</tex>переходами]] следующим образом: рассмотрим состояние <tex>q \in Q</tex>, из которого есть переходы в другие состояния (то есть начиная с <tex>q</tex> можно построить непустое слово, заканчивающееся в терминальной вершине). Тогда если какое-то слово проходит через это состояние, оно может быть зациклено таким образом, что его суффикс, начинающийся с <tex>q</tex>, станет префиксом нового слова, а префикс, заканчивающийся в <tex>q</tex> {{---}} суффиксом. Разделим автомат на две части <tex>A_1</tex> и <tex>A_2</tex> такие, что <tex>A_1</tex> будет содержать все вершины, из которых достижима <tex>q</tex>, а <tex>A_2</tex> {{---}} все вершины, которые достижимы из <tex>q</tex> (см. рис. 1). Заметим, что каждая вершина может содержаться в обеих частях одновременно, такое может случиться, если автомат <tex>M</tex> содержит циклы. Теперь перестроим автомат так, что он будет принимать слова "зацикленные" вокруг <tex>q</tex>, то есть начинающиеся с <tex>q</tex> и после достижения терминальной вершины продолжающиеся с <tex>q_0</tex> (см. рис. 2). Для этого стартовой вершиной сделаем <tex>q</tex> и построим от нее часть <tex>A_2</tex>. Теперь добавим состояние <tex>q_0</tex> и соединим с ним все терминальные состояния из <tex>A_2</tex> с помощью <tex>\varepsilon-</tex>переходов. Далее построим от <tex>q_0</tex> часть <tex>A_1</tex>. Добавим вершину <tex>q'</tex>, эквивалентную <tex>q</tex>, и сделаем ее терминальной. Данный автомат принимает слова, зацикленные вокруг выбранной вершины <tex>q</tex>. Мы хотим, чтобы автомат принимал слова, зацикленные вокруг любой такой <tex>q</tex>. Для этого создадим новую стартовую вершину <tex>q_0'</tex> и свяжем ее <tex>\varepsilon-</tex>переходами со всеми перестроенными автоматами (зацикленными вокруг всех подходящих <tex>q</tex>), в том числе и с изначальным автоматом. Построенный автомат допускает язык <tex>\mathrm{cycle(L)}</tex>, следовательно, данный язык является регулярным.
}}
[[Файл:Ex_1_before.jpg|left|thumb|260px|Рис. 3. Автомат, принимающий язык <tex>L</tex>.]]
[[Файл:Ex_1_after.jpg|right|thumb|380px|Рис. 4. Автомат, принимающий язык <tex>\mathrm{cycle(L)}</tex>.]]
Для лучшего понимания алгоритма перестроения автомата рассмотрим пример.

На рис. 3 представлен автомат, допускающий язык <tex>L = \{ ab, abb, ac \}</tex>. На рис. 4 показано, как этот автомат был перестроен. Были добавлены части, зацикленные относительно вершин <tex>2</tex> и <tex>3</tex>. Появилась новая стартовая вершина <tex>0</tex>, которая связана <tex>\varepsilon-</tex>переходами с изначальным автоматом и его измененными версиями. Данный автомат распознает язык <tex>\mathrm{cycle(L)} = \{ ab, abb, ac, ba, bba, ca, bab \}</tex>: первые три слова распознает первая часть, которая совпадает с изначальным автоматом; следующие три {{---}} вторая, перестроенная относительно вершины <tex>2</tex>; последнее слово распознает третья часть, зацикленная относительно вершины <tex>3</tex>.

 

=== Язык alt(L, M) ===
{{Определение
|definition = Пусть <tex>w = w_1 w_2 \dots w_n</tex> и <tex>x = x_1 x_2 \dots x_n</tex>. Определим <tex>alt(w, x) = w_1 x_1 w_2 x_2 \dots w_n x_n</tex>. Распространим это определение на языки следующим образом: пусть <tex>L</tex> и <tex>M</tex> {{---}} два языка над одним алфавитом <tex>\Sigma</tex>. Тогда <tex>\mathrm{alt(L, M)} = \{ alt(w, x) \mid |w| = |x|, w \in L, x \in M \}</tex>.}}
Например, если <tex>L = \{ 10, 00, 111, 1001 \}</tex> и <tex>M = \{ 11, 0101 \}</tex>, то <tex>\mathrm{alt(L, M)} = \{ 1101, 0101, 10010011 \}</tex>.

{{Утверждение
|id = st4
|statement = Пусть <tex>L</tex> и <tex>M</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярные языки]]. Тогда <tex>\mathrm{alt(L, M)}</tex> также является регулярным.
|proof = Так как <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки, то существуют ДКА <tex>D_L = \langle \Sigma , Q_L , q_{0L} , F_L, \delta_L \rangle</tex>, распознающий язык <tex>L</tex>, и <tex>D_M = \langle \Sigma , Q_M , q_{0M} , F_M, \delta_M \rangle</tex>, распознающий язык <tex>M</tex>. Построим автомат <tex>D_{alt}</tex>, который будет распознавать язык <tex>\mathrm{alt(L, M)}</tex>. Идея следующая: каждое состояние этого автомата будем описывать тремя значениями <tex>(p, q, b)</tex>, где <tex>p \in Q_L</tex>, <tex>q \in Q_M</tex> и <tex>b \in \{ 1, 0 \}</tex>. Нам нужно организовать чередование переходов по состояниям автоматов, то есть если мы на определенном шаге перешли от одного состояния автомата <tex>D_L</tex> до другого, то на следующем мы обязаны совершить переход по состояниям автомата <tex>D_M</tex>. Для этого нам нужно обновлять состояние одного автомата и при этом сохранять состояние другого для следующего перехода. Тут мы будем использовать третье значение: если <tex>b = 0</tex>, то будет двигаться по состояниям первого автомата, то есть значение <tex>p</tex> при переходе в новое состояние автомата <tex>D_{alt}</tex> поменяется, <tex>q</tex> останется неизменной, <tex>b</tex> станет <tex>1</tex>, если <tex>b = 1</tex>, то, соответственно, все наоборот. То есть у нас будут две функции перехода, выбирать нужную будем в зависимости от четности третьего параметра. Важно, что на каждом шаге мы инвертируем значение <tex>b</tex>, что гарантирует чередование. Определим автомат <tex>D_{alt} = \langle \Sigma, Q', q_0', F', \delta' \rangle</tex> следующим образом:
# <tex>Q' = Q_L \times Q_M \times \{ 0, 1 \}</tex>
# <tex>q_0' = (q_{0L}, q_{0M}, 0)</tex>
# <tex>F' = F_L \times F_M \times \{ 0 \}</tex>
# <tex>\delta'((p, q, 0), a) = (\delta_L(p, a), q, 1)</tex> и <tex>\delta'((p, q, 1), a) = (p, \delta_M(q, a), 0)</tex>
Стартовая вершина имеет третий параметр <tex>b = 0</tex>, так как первое значение должно быть получено из автомата <tex>D_L</tex>. Аналогично все терминальные вершины должны иметь то же значение последнего параметра, так как количество переходов должно быть четным и последний переход должен был быть осуществлен по автомату <tex>D_M</tex>. Функция перехода <tex>\delta'</tex> использует <tex>\delta_L</tex> для получения нечетных символов и <tex>\delta_M</tex> для четных. Таким образом, <tex>D_{alt}</tex> состоит из чередующихся символов <tex>D_L</tex> и <tex>D_M</tex>. При этом <tex>D_{alt}</tex> принимает <tex>w</tex> тогда и только тогда, когда <tex>D_L</tex> последовательно принимает все нечетные символы <tex>w</tex> и <tex>D_M</tex> {{---}} все четные, а так же <tex>w</tex> имеет четную длину. Следовательно, <tex>D_{alt}</tex> распознает язык <tex>\mathrm{alt(L, M)}</tex>, что доказывает, что <tex>\mathrm{alt(L, M)}</tex> является регулярным.
}}
[[Файл:Alt ex 1.jpg|left|thumb|265px|Рис. 5. Автоматы для языков <tex>L</tex> и <tex>M</tex>.]]
[[Файл:Alt ex 2.jpg|right|thumb|390px|Рис. 6. Автомат, принимающий язык <tex>\mathrm{alt(L, M)}</tex>.]]
Чтобы более наглядно показать, как строится автомат <tex>D_{alt}</tex>, разберем пример. Пусть <tex>L = \{ 1, 11 \}</tex> и <tex>M = \{ 00 \}</tex> (см. рис. 5). Все состояния нового автомата представлены на рис. 6. Стартовая вершина <tex>q_0' = (1, 1, 0)</tex>, множество терминальных вершин {{---}} <tex>F' = \{ (2, 3, 0), (3, 3, 0) \}</tex>. Мы видим, что построенные по функции <tex>\delta'</tex> переходы на каждом шаге меняют состояние одного из автоматов, а именно того, по которому происходит переход, сохраняя состояние другого для следующего шага. Таким образом, каждый следующий символ получен из автомата, отличного от того, что был использован на предыдущем шаге. Декартово произведение состояний гарантирует, что мы рассмотрим все состояния и переходы изначальных автоматов. Для данного примера мы получаем, что <tex>\mathrm{alt(L, M)} = \{ 1010 \}</tex>.

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Обсуждение участницы:Анна

2016-12-22T21:10:33Z

Анна:

== Примеры доказательств ==
=== Язык <tex>\mathrm{half(L)}</tex> ===
{{Определение
|definition = Определим <tex>\mathrm{half(L)}</tex> как множество первых половин цепочек языка <tex>L</tex>, то есть множество <tex>\{ w \mid </tex> существует <tex>x</tex>, для которой <tex>wx \in L</tex>, причем <tex>|w| = |x| \}</tex>. }}
Например, если <tex>L = \{ \varepsilon, 0010, 011, 010110 \}</tex>, то <tex>\mathrm{half(L)} = \{ \varepsilon, 00, 010 \}</tex>. Заметим, что цепочки нечетной длины не влияют на <tex>\mathrm{half(L)}</tex>.

{{Утверждение
|id = st3
|statement =
Пусть <tex>L</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярный язык]]. Тогда язык <tex>\mathrm{half(L)}</tex> также регулярен.
|proof =
Так как <tex>L</tex> {{---}} регулярный язык, то существует ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>, допускающий его. Рассмотрим строку <tex>x</tex>. Для того, чтобы проверить, что <tex>x \in \mathrm{half(L)}</tex>, нам надо убедиться, что существует строка <tex>y</tex> такой же длины, что и <tex>x</tex>, которая, будучи сконкатенированной с <tex>x</tex>, даст строку из <tex>L</tex>, то есть если на вход автомату подать <tex>xy</tex>, то в конце обработки мы окажемся в терминальном состоянии. Предположим, что автомат, закончив обработку <tex>x</tex>, находится в состоянии <tex>q_i</tex>, то есть <tex>\delta(q_0, x) = q_i</tex>. Мы должны проверить, что существует строка <tex>y, |y| = |x|,</tex> которая ведет из состояния <tex>q_i</tex> до какого-нибудь терминального состояния <tex>M</tex>, то есть <tex>\delta(q_i, y) \in F</tex>.

Предположим, что мы прошли <tex>n</tex> вершин автомата, то есть <tex>|x| = n</tex>. Обозначим за <tex>S_n</tex> множество всех состояний, с которых можно попасть в терминальные за <tex>n</tex> шагов. Тогда <tex>q_i \in S_n \Leftrightarrow x \in \mathrm{half(L)}</tex>. Если мы сможем отслеживать <tex>S_n</tex> и <tex>q_i</tex>, то сможем определять, верно ли, что <tex>x \in \mathrm{half(L)}</tex>. Заметим, что <tex>S_0 \equiv F</tex>. Очевидно мы можем построить <tex>S_{n+1}</tex> зная <tex>S_n</tex> и <tex>\delta</tex>: <tex>S_{n+1} = prev(S_n) = \{ q \in Q \mid \exists a \in \Sigma, q' \in S_n, \delta(q, a) = q' \}</tex> {{---}} множество состояний, из которых есть переход в какое-либо состояние из <tex>S_n</tex> (по единственному символу). Теперь надо найти способ отслеживать и обновлять <tex>S_n</tex>.

Построим ДКА <tex>M'</tex>, который будет хранить эту информацию в своих состояниях. Определим <tex>Q' = Q \times 2^Q</tex>, то есть каждое состояние <tex>M'</tex> {{---}} это пара из одиночного состояния из <tex>M</tex> и множества состояний из <tex>M</tex>. Функцию перехода <tex>\delta'</tex> автомата <tex>M'</tex> определим так, чтобы если по какой-то строке <tex>x</tex> длины <tex>n</tex> в автомате <tex>M</tex> мы перешли в состояние <tex>q_i</tex>, то по этой же строке в автомате <tex>M'</tex> мы перейдем в состояние <tex>(q_i, S_n)</tex>, где <tex>S_n</tex> {{---}} множество состояний из <tex>M</tex>, определенное выше. Вспомним приведенную выше функцию <tex>prev(S_n) = S_{n+1}</tex>. С ее помощью мы можем определить функцию перехода следующим образом: <tex>\delta'((q, S), a) = (\delta(q, a), prev(S))</tex>. Начальное состояние <tex>q_0' = (q_0, S_0) = (q_0, F)</tex>. Множество терминальных состояний {{---}} <tex>F' = \{ (q, S) \mid q \in S, S \in 2^Q \}</tex>.

Теперь по индукции не сложно доказать, что <tex>\delta'(q_0', x) = (\delta(q_0, x), S_n)</tex>, где <tex>|x| = n</tex>. По определению множества терминальных вершин, автомат <tex>M'</tex> допускает строку <tex>x</tex> тогда и только тогда, когда <tex>\delta(q_0, x) \in S_n</tex>. Следовательно, автомат <tex>M'</tex> допускает язык <tex>\mathrm{half(L)}</tex>.Таким образом, мы построили ДКА, который допускает язык <tex>\mathrm{half(L)}</tex>. Следовательно, данный язык является регулярным.
}}
=== Язык <tex>\mathrm{cycle(L)}</tex> ===
{{Определение
|definition = Определим <tex>\mathrm{cycle(L)}</tex> как множество <tex>\{ w \mid </tex> цепочку <tex>w</tex> можно представить в виде <tex>w = xy</tex>, где <tex>yx \in L \}</tex>. }}
Например, если <tex>L = \{ 01, 011 \}</tex>, то <tex>\mathrm{cycle(L)} = \{ 01, 10, 011, 110, 101 \}</tex>.

{{Утверждение
|id = st5
|statement =
Пусть <tex>L</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярный язык]]. Тогда язык <tex>\mathrm{cycle(L)}</tex> также регулярен.
|proof =
[[Файл:Enfa_before.jpg|right|thumb|380px|Рис. 1. Разбиение автомата.]]
[[Файл:Enfa-after.jpg|right|thumb|380px|Рис. 2. Перестроение.]]
Так как <tex>L</tex> {{---}} регулярный язык, то существует допускающий его ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>. Построим из <tex>M</tex> [[Автоматы_с_eps-переходами._Eps-замыкание|недетерминированный автомат с <tex>\varepsilon-</tex>переходами]] следующим образом: рассмотрим состояние <tex>q \in Q</tex>, из которого есть переходы в другие состояния (то есть начиная с <tex>q</tex> можно построить непустое слово, заканчивающееся в терминальной вершине). Тогда если какое-то слово проходит через это состояние, оно может быть зациклено таким образом, что его суффикс, начинающийся с <tex>q</tex>, станет префиксом нового слова, а префикс, заканчивающийся в <tex>q</tex> {{---}} суффиксом. Разделим автомат на две части <tex>A_1</tex> и <tex>A_2</tex> такие, что <tex>A_1</tex> будет содержать все вершины, из которых достижима <tex>q</tex>, а <tex>A_2</tex> {{---}} все вершины, которые достижимы из <tex>q</tex> (см. рис. 1). Заметим, что каждая вершина может содержаться в обеих частях одновременно, такое может случиться, если автомат <tex>M</tex> содержит циклы. Теперь перестроим автомат так, что он будет принимать слова "зацикленные" вокруг <tex>q</tex>, то есть начинающиеся с <tex>q</tex> и после достижения терминальной вершины продолжающиеся с <tex>q_0</tex> (см. рис. 2). Для этого стартовой вершиной сделаем <tex>q</tex> и построим от нее часть <tex>A_2</tex>. Теперь добавим состояние <tex>q_0</tex> и соединим с ним все терминальные состояния из <tex>A_2</tex> с помощью <tex>\varepsilon-</tex>переходов. Далее построим от <tex>q_0</tex> часть <tex>A_1</tex>. Добавим вершину <tex>q'</tex>, эквивалентную <tex>q</tex>, и сделаем ее терминальной. Данный автомат принимает слова, зацикленные вокруг выбранной вершины <tex>q</tex>. Мы хотим, чтобы автомат принимал слова, зацикленные вокруг любой такой <tex>q</tex>. Для этого создадим новую стартовую вершину <tex>q_0'</tex> и свяжем ее <tex>\varepsilon-</tex>переходами со всеми перестроенными автоматами (зацикленными вокруг всех подходящих <tex>q</tex>), в том числе и с изначальным автоматом. Построенный автомат допускает язык <tex>\mathrm{cycle(L)}</tex>, следовательно, данный язык является регулярным.
}}
[[Файл:Ex_1_before.jpg|left|thumb|260px|Рис. 3. Автомат, принимающий язык <tex>L</tex>.]]
[[Файл:Ex_1_after.jpg|right|thumb|380px|Рис. 4. Автомат, принимающий язык <tex>\mathrm{cycle(L)}</tex>.]]
Для лучшего понимания алгоритма перестроения автомата рассмотрим пример.

На рис. 3 представлен автомат, допускающий язык <tex>L = \{ ab, abb, ac \}</tex>. На рис. 4 показано, как этот автомат был перестроен. Были добавлены части, зацикленные относительно вершин <tex>2</tex> и <tex>3</tex>. Появилась новая стартовая вершина <tex>0</tex>, которая связана <tex>\varepsilon-</tex>переходами с изначальным автоматом и его измененными версиями. Данный автомат распознает язык <tex>\mathrm{cycle(L)} = \{ ab, abb, ac, ba, bba, ca, bab \}</tex>: первые три слова распознает первая часть, которая совпадает с изначальным автоматом; следующие три {{---}} вторая, перестроенная относительно вершины <tex>2</tex>; последнее слово распознает третья часть, зацикленная относительно вершины <tex>3</tex>.

 

=== Язык <tex>\mathrm{alt(L, M)}</tex> ===
{{Определение
|definition = Пусть <tex>w = w_1 w_2 \dots w_n</tex> и <tex>x = x_1 x_2 \dots x_n</tex>. Определим <tex>alt(w, x) = w_1 x_1 w_2 x_2 \dots w_n x_n</tex>. Распространим это определение на языки следующим образом: пусть <tex>L</tex> и <tex>M</tex> {{---}} два языка над одним алфавитом <tex>\Sigma</tex>. Тогда <tex>\mathrm{alt(L, M)} = \{ alt(w, x) \mid |w| = |x|, w \in L, x \in M \}</tex>.}}
Например, если <tex>L = \{ 10, 00, 111, 1001 \}</tex> и <tex>M = \{ 11, 0101 \}</tex>, то <tex>\mathrm{alt(L, M)} = \{ 1101, 0101, 10010011 \}</tex>.

{{Утверждение
|id = st4
|statement = Пусть <tex>L</tex> и <tex>M</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярные языки]]. Тогда <tex>\mathrm{alt(L, M)}</tex> также является регулярным.
|proof = Так как <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки, то существуют ДКА <tex>D_L = \langle \Sigma , Q_L , q_{0L} , F_L, \delta_L \rangle</tex>, распознающий язык <tex>L</tex>, и <tex>D_M = \langle \Sigma , Q_M , q_{0M} , F_M, \delta_M \rangle</tex>, распознающий язык <tex>M</tex>. Построим автомат <tex>D_{alt}</tex>, который будет распознавать язык <tex>\mathrm{alt(L, M)}</tex>. Идея следующая: каждое состояние этого автомата будем описывать тремя значениями <tex>(p, q, b)</tex>, где <tex>p \in Q_L</tex>, <tex>q \in Q_M</tex> и <tex>b \in \{ 1, 0 \}</tex>. Нам нужно организовать чередование переходов по состояниям автоматов, то есть если мы на определенном шаге перешли от одного состояния автомата <tex>D_L</tex> до другого, то на следующем мы обязаны совершить переход по состояниям автомата <tex>D_M</tex>. Для этого нам нужно обновлять состояние одного автомата и при этом сохранять состояние другого для следующего перехода. Тут мы будем использовать третье значение: если <tex>b = 0</tex>, то будет двигаться по состояниям первого автомата, то есть значение <tex>p</tex> при переходе в новое состояние автомата <tex>D_{alt}</tex> поменяется, <tex>q</tex> останется неизменной, <tex>b</tex> станет <tex>1</tex>, если <tex>b = 1</tex>, то, соответственно, все наоборот. То есть у нас будут две функции перехода, выбирать нужную будем в зависимости от четности третьего параметра. Важно, что на каждом шаге мы инвертируем значение <tex>b</tex>, что гарантирует чередование. Определим автомат <tex>D_{alt} = \langle \Sigma, Q', q_0', F', \delta' \rangle</tex> следующим образом:
# <tex>Q' = Q_L \times Q_M \times \{ 0, 1 \}</tex>
# <tex>q_0' = (q_{0L}, q_{0M}, 0)</tex>
# <tex>F' = F_L \times F_M \times \{ 0 \}</tex>
# <tex>\delta'((p, q, 0), a) = (\delta_L(p, a), q, 1)</tex> и <tex>\delta'((p, q, 1), a) = (p, \delta_M(q, a), 0)</tex>
Стартовая вершина имеет третий параметр <tex>b = 0</tex>, так как первое значение должно быть получено из автомата <tex>D_L</tex>. Аналогично все терминальные вершины должны иметь то же значение последнего параметра, так как количество переходов должно быть четным и последний переход должен был быть осуществлен по автомату <tex>D_M</tex>. Функция перехода <tex>\delta'</tex> использует <tex>\delta_L</tex> для получения нечетных символов и <tex>\delta_M</tex> для четных. Таким образом, <tex>D_{alt}</tex> состоит из чередующихся символов <tex>D_L</tex> и <tex>D_M</tex>. При этом <tex>D_{alt}</tex> принимает <tex>w</tex> тогда и только тогда, когда <tex>D_L</tex> последовательно принимает все нечетные символы <tex>w</tex> и <tex>D_M</tex> {{---}} все четные, а так же <tex>w</tex> имеет четную длину. Следовательно, <tex>D_{alt}</tex> распознает язык <tex>\mathrm{alt(L, M)}</tex>, что доказывает, что <tex>\mathrm{alt(L, M)}</tex> является регулярным.
}}
[[Файл:Alt ex 1.jpg|left|thumb|265px|Рис. 5. Автоматы для языков <tex>L</tex> и <tex>M</tex>.]]
[[Файл:Alt ex 2.jpg|right|thumb|390px|Рис. 6. Автомат, принимающий язык <tex>\mathrm{alt(L, M)}</tex>.]]
Чтобы более наглядно показать, как строится автомат <tex>D_{alt}</tex>, разберем пример. Пусть <tex>L = \{ 1, 11 \}</tex> и <tex>M = \{ 00 \}</tex> (см. рис. 5). Все состояния нового автомата представлены на рис. 6. Стартовая вершина <tex>q_0' = (1, 1, 0)</tex>, множество терминальных вершин {{---}} <tex>F' = \{ (2, 3, 0), (3, 3, 0) \}</tex>. Мы видим, что построенные по функции <tex>\delta'</tex> переходы на каждом шаге меняют состояние одного из автоматов, а именно того, по которому происходит переход, сохраняя состояние другого для следующего шага. Таким образом, каждый следующий символ получен из автомата, отличного от того, что был использован на предыдущем шаге. Декартово произведение состояний гарантирует, что мы рассмотрим все состояния и переходы изначальных автоматов. Для данного примера мы получаем, что <tex>\mathrm{alt(L, M)} = \{ 1010 \}</tex>.

Обсуждение участницы:Анна

2016-12-22T20:51:09Z

Анна: /* Язык alt(L, M) */

== Примеры доказательств ==
=== Язык <tex>half(L)</tex> ===
{{Определение
|definition = Определим <tex>half(L)</tex> как множество первых половин цепочек языка <tex>L</tex>, то есть множество <tex>\{ w \mid </tex> существует <tex>x</tex>, для которой <tex>wx \in L</tex>, причем <tex>|w| = |x| \}</tex>. }}
Например, если <tex>L = \{ \varepsilon, 0010, 011, 010110 \}</tex>, то <tex>half(L) = \{ \varepsilon, 00, 010 \}</tex>. Заметим, что цепочки нечетной длины не влияют на <tex>half(L)</tex>.

{{Утверждение
|id = st3
|statement =
Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык <tex>half(L)</tex> также регулярен.
|proof =
Так как <tex>L</tex> {{---}} регулярный язык, то существует ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>, допускающий его. Рассмотрим строку <tex>x</tex>. Для того, чтобы проверить, что <tex>x \in half(L)</tex>, нам надо убедиться, что существует строка <tex>y</tex> такой же длины, что и <tex>x</tex>, которая, будучи сконкатенированной с <tex>x</tex>, даст строку из <tex>L</tex>, то есть если на вход автомату подать <tex>xy</tex>, то в конце обработки мы окажемся в терминальном состоянии. Предположим, что автомат, закончив обработку <tex>x</tex>, находится в состоянии <tex>q_i</tex>, то есть <tex>\delta(q_0, x) = q_i</tex>. Мы должны проверить, что существует строка <tex>y, |y| = |x|,</tex> которая ведет из состояния <tex>q_i</tex> до какого-нибудь терминального состояния <tex>M</tex>, то есть <tex>\delta(q_i, y) \in F</tex>. 
Предположим, что мы прошли <tex>n</tex> вершин автомата, то есть <tex>|x| = n</tex>. Обозначим за <tex>S_n</tex> множество всех состояний, с которых можно попасть в терминальные за <tex>n</tex> шагов. Тогда <tex>q_i \in S_n \Leftrightarrow x \in half(L)</tex>. Если мы сможем отслеживать <tex>S_n</tex> и <tex>q_i</tex>, то сможем определять, верно ли, что <tex>x \in half(L)</tex>. Заметим, что <tex>S_0 \equiv F</tex>. Очевидно мы можем построить <tex>S_{n+1}</tex> зная <tex>S_n</tex> и <tex>\delta</tex>: <tex>S_{n+1} = prev(S_n) = \{ q \in Q \mid \exists a \in \Sigma, q' \in S_n, \delta(q, a) = q' \}</tex> {{---}} множество состояний, из которых есть переход в какое-либо состояние из <tex>S_n</tex> (по единственному символу). Теперь надо найти способ отслеживать и обновлять <tex>S_n</tex>. 
Построим ДКА <tex>M'</tex>, который будет хранить эту информацию в своих состояниях. Определим <tex>Q' = Q \times 2^Q</tex>, то есть каждое состояние <tex>M'</tex> {{---}} это пара из одиночного состояния из <tex>M</tex> и множества состояний из <tex>M</tex>. Функцию перехода <tex>\delta'</tex> автомата <tex>M'</tex> определим так, чтобы если по какой-то строке <tex>x</tex> длины <tex>n</tex> в автомате <tex>M</tex> мы перешли в состояние <tex>q_i</tex>, то по этой же строке в автомате <tex>M'</tex> мы перейдем в состояние <tex>(q_i, S_n)</tex>, где <tex>S_n</tex> {{---}} множество состояний из <tex>M</tex>, определенное выше. Вспомним приведенную выше функцию <tex>prev(S_n) = S_{n+1}</tex>. С ее помощью мы можем определить функцию перехода следующим образом: <tex>\delta'((q, S), a) = (\delta(q, a), prev(S))</tex>. Начальное состояние <tex>q_0' = (q_0, S_0) = (q_0, F)</tex>. Множество терминальных состояний {{---}} <tex>F' = \{ (q, S) \mid q \in S, S \in 2^Q \}</tex>. 
Теперь по индукции не сложно доказать, что <tex>\delta'(q_0', x) = (\delta(q_0, x), S_n)</tex>, где <tex>|x| = n</tex>. По определению множества терминальных вершин, автомат <tex>M'</tex> допускает строку <tex>x</tex> тогда и только тогда, когда <tex>\delta(q_0, x) \in S_n</tex>. Следовательно, автомат <tex>M'</tex> допускает язык <tex>half(L)</tex>.Таким образом, мы построили ДКА, который допускает язык <tex>half(L)</tex>. Следовательно, данный язык является регулярным.
}}
=== Язык <tex>cycle(L)</tex> ===
{{Определение
|definition = Определим <tex>cycle(L)</tex> как множество <tex>\{ w \mid </tex> цепочку <tex>w</tex> можно представить в виде <tex>w = xy</tex>, где <tex>yx \in L \}</tex>. }}
Например, если <tex>L = \{ 01, 011 \}</tex>, то <tex>cycle(L) = \{ 01, 10, 011, 110, 101 \}</tex>.

{{Утверждение
|id = st5
|statement =
Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык <tex>cycle(L)</tex> также регулярен.
|proof =
[[Файл:Enfa_before.jpg|right|thumb|380px|Рис. 1. Разбиение автомата.]]
[[Файл:Enfa-after.jpg|right|thumb|380px|Рис. 2. Перестроение.]]
Так как <tex>L</tex> {{---}} регулярный язык, то существует допускающий его ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>. Построим из <tex>M</tex> недетерминированный автомат с <tex>\varepsilon-</tex>переходами следующим образом: рассмотрим состояние <tex>q \in Q</tex>, из которого есть переходы в другие состояния (то есть начиная с <tex>q</tex> можно построить непустое слово, заканчивающееся в терминальной вершине). Тогда если какое-то слово проходит через это состояние, оно может быть зациклено таким образом, что его суффикс, начинающийся с <tex>q</tex>, станет префиксом нового слова, а префикс, заканчивающийся в <tex>q</tex> {{---}} суффиксом. Разделим автомат на две части <tex>A_1</tex> и <tex>A_2</tex> такие, что <tex>A_1</tex> будет содержать все вершины, из которых достижима <tex>q</tex>, а <tex>A_2</tex> {{---}} все вершины, которые достижимы из <tex>q</tex> (см. рис. 1). Заметим, что каждая вершина может содержаться в обеих частях одновременно, такое может случиться, если автомат <tex>M</tex> содержит циклы. Теперь перестроим автомат так, что он будет принимать слова "зацикленные" вокруг <tex>q</tex>, то есть начинающиеся с <tex>q</tex> и после достижения терминальной вершины продолжающиеся с <tex>q_0</tex> (см. рис. 2). Для этого стартовой вершиной сделаем <tex>q</tex> и построим от нее часть <tex>A_2</tex>. Теперь добавим состояние <tex>q_0</tex> и соединим с ним все терминальные состояния из <tex>A_2</tex> с помощью <tex>\varepsilon-</tex>переходов. Далее построим от <tex>q_0</tex> часть <tex>A_1</tex>. Добавим вершину <tex>q'</tex>, эквивалентную <tex>q</tex>, и сделаем ее терминальной. Данный автомат принимает слова, зацикленные вокруг выбранной вершины <tex>q</tex>. Мы хотим, чтобы автомат принимал слова, зацикленные вокруг любой такой <tex>q</tex>. Для этого создадим новую стартовую вершину <tex>q_0'</tex> и свяжем ее <tex>\varepsilon-</tex>переходами со всеми перестроенными автоматами (зацикленными вокруг всех подходящих <tex>q</tex>), в том числе и с изначальным автоматом. Построенный автомат допускает язык <tex>cycle(L)</tex>, следовательно, данный язык является регулярным.
}}
[[Файл:Ex_1_before.jpg|left|thumb|260px|Рис. 3. Автомат, принимающий язык <tex>L</tex>.]]
[[Файл:Ex_1_after.jpg|right|thumb|380px|Рис. 4. Автомат, принимающий язык <tex>cycle(L)</tex>.]]
Для лучшего понимания алгоритма перестроения автомата рассмотрим пример. 
На рис. 3 представлен автомат, допускающий язык <tex>L = \{ ab, abb, ac \}</tex>. На рис. 4 показано, как этот автомат был перестроен. Были добавлены части, зацикленные относительно вершин <tex>2</tex> и <tex>3</tex>. Появилась новая стартовая вершина <tex>0</tex>, которая связана <tex>\varepsilon-</tex>переходами с изначальным автоматом и его измененными версиями. Данный автомат распознает язык <tex>cycle(L) = \{ ab, abb, ac, ba, bba, ca, bab \}</tex>: первые три слова распознает первая часть, которая совпадает с изначальным автоматом; следующие три {{---}} вторая, перестроенная относительно вершины <tex>2</tex>; последнее слово распознает третья часть, зацикленная относительно вершины <tex>3</tex>.

 

=== Язык <tex>alt(L, M)</tex> ===
{{Определение
|definition = Пусть <tex>w = w_1 w_2 \dots w_n</tex> и <tex>x = x_1 x_2 \dots x_n</tex>. Определим <tex>alt(w, x) = w_1 x_1 w_2 x_2 \dots w_n x_n</tex>. Распространим это определение на языки следующим образом: пусть <tex>L</tex> и <tex>M</tex> {{---}} два языка над одним алфавитом <tex>\Sigma</tex>. Тогда <tex>alt(L, M) = \{ alt(w, x) \mid |w| = |x|, w \in L, x \in M \}</tex>.}}
Например, если <tex>L = \{ 10, 00, 111, 1001 \}</tex> и <tex>M = \{ 11, 0101 \}</tex>, то <tex>alt(L, M) = \{ 1101, 0101, 10010011 \}</tex>.

{{Утверждение
|id = st4
|statement = Пусть <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки. Тогда <tex>alt(L, M)</tex> также является регулярным.
|proof = Так как <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки, то существуют ДКА <tex>D_L = \langle \Sigma , Q_L , q_{0L} , F_L, \delta_L \rangle</tex>, распознающий язык <tex>L</tex>, и <tex>D_M = \langle \Sigma , Q_M , q_{0M} , F_M, \delta_M \rangle</tex>, распознающий язык <tex>M</tex>. Построим автомат <tex>D_{alt}</tex>, который будет распознавать язык <tex>alt(L, M)</tex>. Идея следующая: каждое состояние этого автомата будем описывать тремя значениями <tex>(p, q, b)</tex>, где <tex>p \in Q_L</tex>, <tex>q \in Q_M</tex> и <tex>b \in \{ 1, 0 \}</tex>. Нам нужно организовать чередование переходов по состояниям автоматов, то есть если мы на определенном шаге перешли от одного состояния автомата <tex>D_L</tex> до другого, то на следующем мы обязаны совершить переход по состояниям автомата <tex>D_M</tex>. Для этого нам нужно обновлять состояние одного автомата и при этом сохранять состояние другого для следующего перехода. Тут мы будем использовать третье значение: если <tex>b = 0</tex>, то будет двигаться по состояниям первого автомата, то есть значение <tex>p</tex> при переходе в новое состояние автомата <tex>D_{alt}</tex> поменяется, <tex>q</tex> останется неизменной, <tex>b</tex> станет <tex>1</tex>, если <tex>b = 1</tex>, то, соответственно, все наоборот. То есть у нас будут две функции перехода, выбирать нужную будем в зависимости от четности третьего параметра. Важно, что на каждом шаге мы инвертируем значение <tex>b</tex>, что гарантирует чередование. Определим автомат <tex>D_{alt} = \langle \Sigma, Q', q_0', F', \delta' \rangle</tex> следующим образом:
# <tex>Q' = Q_L \times Q_M \times \{ 0, 1 \}</tex>
# <tex>q_0' = (q_{0L}, q_{0M}, 0)</tex>
# <tex>F' = F_L \times F_M \times \{ 0 \}</tex>
# <tex>\delta'((p, q, 0), a) = (\delta_L(p, a), q, 1)</tex> и <tex>\delta'((p, q, 1), a) = (p, \delta_M(q, a), 0)</tex>
Стартовая вершина имеет третий параметр <tex>b = 0</tex>, так как первое значение должно быть получено из автомата <tex>D_L</tex>. Аналогично все терминальные вершины должны иметь то же значение последнего параметра, так как количество переходов должно быть четным и последний переход должен был быть осуществлен по автомату <tex>D_M</tex>. Функция перехода <tex>\delta'</tex> использует <tex>\delta_L</tex> для получения нечетных символов и <tex>\delta_M</tex> для четных. Таким образом, <tex>D_{alt}</tex> состоит из чередующихся символов <tex>D_L</tex> и <tex>D_M</tex>. При этом <tex>D_{alt}</tex> принимает <tex>w</tex> тогда и только тогда, когда <tex>D_L</tex> последовательно принимает все нечетные символы <tex>w</tex> и <tex>D_M</tex> {{---}} все четные, а так же <tex>w</tex> имеет четную длину. Следовательно, <tex>D_{alt}</tex> распознает язык <tex>alt(L, M)</tex>, что доказывает, что <tex>alt(L, M)</tex> является регулярным.
}}
[[Файл:Alt ex 1.jpg|left|thumb|265px|Рис. 5. Автоматы для языков <tex>L</tex> и <tex>M</tex>.]]
[[Файл:Alt ex 2.jpg|right|thumb|390px|Рис. 6. Автомат, принимающий язык <tex>alt(L, M)</tex>.]]
Чтобы более наглядно показать, как строится автомат <tex>D_{alt}</tex>, разберем пример. Пусть <tex>L = \{ 1, 11 \}</tex> и <tex>M = \{ 00 \}</tex> (см. рис. 5). Все состояния нового автомата представлены на рис. 6. Стартовая вершина <tex>q_0' = (1, 1, 0)</tex>, множество терминальных вершин {{---}} <tex>F' = \{ (2, 3, 0), (3, 3, 0) \}</tex>. Мы видим, что построенные по функции <tex>\delta'</tex> переходы на каждом шаге меняют состояние одного из автоматов, а именно того, по которому происходит переход, сохраняя состояние другого для следующего шага. Таким образом, каждый следующий символ получен из автомата, отличного от того, что был использован на предыдущем шаге. Декартово произведение состояний гарантирует, что мы рассмотрим все состояния и переходы изначальных автоматов.

Обсуждение участницы:Анна

2016-12-22T20:34:45Z

Анна:

Файл:Alt ex 2.jpg

2016-12-22T20:09:10Z

Анна:

Файл:Alt ex 1.jpg

2016-12-22T20:03:07Z

Анна:

Обсуждение участницы:Анна

2016-12-17T21:26:27Z

Анна: /* Язык alt(L, M) */

== Примеры доказательств ==
=== Язык <tex>half(L)</tex> ===
{{Определение
|definition = Определим <tex>half(L)</tex> как множество первых половин цепочек языка <tex>L</tex>, то есть множество <tex>\{ w \mid </tex> существует <tex>x</tex>, для которой <tex>wx \in L</tex>, причем <tex>|w| = |x| \}</tex>. }}
Например, если <tex>L = \{ \varepsilon, 0010, 011, 010110 \}</tex>, то <tex>half(L) = \{ \varepsilon, 00, 010 \}</tex>. Заметим, что цепочки нечетной длины не влияют на <tex>half(L)</tex>.

{{Утверждение
|id = st3
|statement =
Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык <tex>half(L)</tex> также регулярен.
|proof =
Так как <tex>L</tex> {{---}} регулярный язык, то существует ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>, допускающий его. Рассмотрим строку <tex>x</tex>. Для того, чтобы проверить, что <tex>x \in half(L)</tex>, нам надо убедиться, что существует строка <tex>y</tex> такой же длины, что и <tex>x</tex>, которая, будучи сконкатенированной с <tex>x</tex>, даст строку из <tex>L</tex>, то есть если на вход автомату подать <tex>xy</tex>, то в конце обработки мы окажемся в терминальном состоянии. Предположим, что автомат, закончив обработку <tex>x</tex>, находится в состоянии <tex>q_i</tex>, то есть <tex>\delta(q_0, x) = q_i</tex>. Мы должны проверить, что существует строка <tex>y, |y| = |x|,</tex> которая ведет из состояния <tex>q_i</tex> до какого-нибудь терминального состояния <tex>M</tex>, то есть <tex>\delta(q_i, y) \in F</tex>. 
Предположим, что мы прошли <tex>n</tex> вершин автомата, то есть <tex>|x| = n</tex>. Обозначим за <tex>S_n</tex> множество всех состояний, с которых можно попасть в терминальные за <tex>n</tex> шагов. Тогда <tex>q_i \in S_n \Leftrightarrow x \in half(L)</tex>. Если мы сможем отслеживать <tex>S_n</tex> и <tex>q_i</tex>, то сможем определять, верно ли, что <tex>x \in half(L)</tex>. Заметим, что <tex>S_0 \equiv F</tex>. Очевидно мы можем построить <tex>S_{n+1}</tex> зная <tex>S_n</tex> и <tex>\delta</tex>: <tex>S_{n+1} = prev(S_n) = \{ q \in Q \mid \exists a \in \Sigma, q' \in S_n, \delta(q, a) = q' \}</tex> {{---}} множество состояний, из которых есть переход в какое-либо состояние из <tex>S_n</tex> (по единственному символу). Теперь надо найти способ отслеживать и обновлять <tex>S_n</tex>. 
Построим ДКА <tex>M'</tex>, который будет хранить эту информацию в своих состояниях. Определим <tex>Q' = Q \times 2^Q</tex>, то есть каждое состояние <tex>M'</tex> {{---}} это пара из одиночного состояния из <tex>M</tex> и множества состояний из <tex>M</tex>. Функцию перехода <tex>\delta'</tex> автомата <tex>M'</tex> определим так, чтобы если по какой-то строке <tex>x</tex> длины <tex>n</tex> в автомате <tex>M</tex> мы перешли в состояние <tex>q_i</tex>, то по этой же строке в автомате <tex>M'</tex> мы перейдем в состояние <tex>(q_i, S_n)</tex>, где <tex>S_n</tex> {{---}} множество состояний из <tex>M</tex>, определенное выше. Вспомним приведенную выше функцию <tex>prev(S_n) = S_{n+1}</tex>. С ее помощью мы можем определить функцию перехода следующим образом: <tex>\delta'((q, S), a) = (\delta(q, a), prev(S))</tex>. Начальное состояние <tex>q_0' = (q_0, S_0) = (q_0, F)</tex>. Множество терминальных состояний {{---}} <tex>F' = \{ (q, S) \mid q \in S, S \in 2^Q \}</tex>. 
Теперь по индукции не сложно доказать, что <tex>\delta'(q_0', x) = (\delta(q_0, x), S_n)</tex>, где <tex>|x| = n</tex>. По определению множества терминальных вершин, автомат <tex>M'</tex> допускает строку <tex>x</tex> тогда и только тогда, когда <tex>\delta(q_0, x) \in S_n</tex>. Следовательно, автомат <tex>M'</tex> допускает язык <tex>half(L)</tex>.Таким образом, мы построили ДКА, который допускает язык <tex>half(L)</tex>. Следовательно, данный язык является регулярным.
}}
=== Язык <tex>alt(L, M)</tex> ===
{{Определение
|definition = Пусть <tex>w = w_1 w_2 \dots w_n</tex> и <tex>x = x_1 x_2 \dots x_n</tex>. Определим <tex>alt(w, x) = w_1 x_1 w_2 x_2 \dots w_n x_n</tex>. Распространим это определение на языки следующим образом: пусть <tex>L</tex> и <tex>M</tex> {{---}} два языка над одним алфавитом <tex>\Sigma</tex>. Тогда <tex>alt(L, M) = \{ alt(w, x) \mid |w| = |x|, w \in L, x \in M \}</tex>.}}
Например, если <tex>L = \{ 10, 00, 111, 1001 \}</tex> и <tex>M = \{ 11, 0101 \}</tex>, то <tex>alt(L, M) = \{ 1101, 0101, 10010011 \}</tex>.

{{Утверждение
|id = st4
|statement = Пусть <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки. Тогда <tex>alt(L, M)</tex> также является регулярным.
|proof = Так как <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки, то существуют ДКА <tex>D_L = \langle \Sigma , Q_L , q_{0L} , F_L, \delta_L \rangle</tex>, распознающий язык <tex>L</tex>, и <tex>D_M = \langle \Sigma , Q_M , q_{0M} , F_M, \delta_M \rangle</tex>, распознающий язык <tex>M</tex>. Построим автомат <tex>D_{alt}</tex>, который будет распознавать язык <tex>alt(L, M)</tex>. Идея следующая: каждое состояние этого автомата будем описывать тремя значениями <tex>(p, q, b)</tex>, где <tex>p \in Q_L</tex>, <tex>q \in Q_M</tex> и <tex>b \in \{ 1, 0 \}</tex>. Нам нужно организовать чередование переходов по состояниям автоматов, то есть если мы на определенном шаге перешли от одного состояния автомата <tex>D_L</tex> до другого, то на следующем мы обязаны совершить переход по состояниям автомата <tex>D_M</tex>. Для этого нам нужно обновлять состояние одного автомата и при этом сохранять состояние другого для следующего перехода. Тут мы будем использовать третье значение: если <tex>b = 0</tex>, то будет двигаться по состояниям первого автомата, то есть значение <tex>p</tex> при переходе в новое состояние автомата <tex>D_{alt}</tex> поменяется, <tex>q</tex> останется неизменной, <tex>b</tex> станет <tex>1</tex>, если <tex>b = 1</tex>, то, соответственно, все наоборот. То есть у нас будут две функции перехода, выбирать нужную будем в зависимости от четности третьего параметра. Важно, что на каждом шаге мы инвертируем значение <tex>b</tex>, что гарантирует чередование. Определим автомат <tex>D_{alt} = \langle \Sigma, Q', q_0', F', \delta' \rangle</tex> следующим образом:
# <tex>Q' = Q_L \times Q_M \times \{ 0, 1 \}</tex>
# <tex>q_0' = (q_{0L}, q_{0M}, 0)</tex>
# <tex>F' = F_L \times F_M \times \{ 0 \}</tex>
# <tex>\delta'((p, q, 0), a) = (\delta_L(p, a), q, 1)</tex> и <tex>\delta'((p, q, 1), a) = (p, \delta_M(q, a), 0)</tex>
Стартовая вершина имеет третий параметр <tex>b = 0</tex>, так как первое значение должно быть получено из автомата <tex>D_L</tex>. Аналогично все терминальные вершины должны иметь то же значение последнего параметра, так как количество переходов должно быть четным и последний переход должен был быть осуществлен по автомату <tex>D_M</tex>. Функция перехода <tex>\delta'</tex> использует <tex>\delta_L</tex> для получения нечетных символов и <tex>\delta_M</tex> для четных. Таким образом, <tex>D_{alt}</tex> состоит из чередующихся символов <tex>D_L</tex> и <tex>D_M</tex>. При этом <tex>D_{alt}</tex> принимает <tex>w</tex> тогда и только тогда, когда <tex>D_L</tex> последовательно принимает все нечетные символы <tex>w</tex> и <tex>D_M</tex> {{---}} все четные, а так же <tex>w</tex> имеет четную длину. Следовательно, <tex>D_{alt}</tex> распознает язык <tex>alt(L, M)</tex>, что доказывает, что <tex>alt(L, M)</tex> является регулярным.
}}
Чтобы более наглядно показать, как строится автомат <tex>D_{alt}</tex>, разберем пример. Пусть <tex>L = \{ 1, 11 \}</tex> и <tex>M = \{ 00 \}</tex>.

=== Язык <tex>cycle(L)</tex> ===
{{Определение
|definition = Определим <tex>cycle(L)</tex> как множество <tex>\{ w \mid </tex> цепочку <tex>w</tex> можно представить в виде <tex>w = xy</tex>, где <tex>yx \in L \}</tex>. }}
Например, если <tex>L = \{ 01, 011 \}</tex>, то <tex>cycle(L) = \{ 01, 10, 011, 110, 101 \}</tex>.

{{Утверждение
|id = st5
|statement =
Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык <tex>cycle(L)</tex> также регулярен.
|proof =
[[Файл:Enfa_before.jpg|right|thumb|380px|Рис. 1. Разбиение автомата.]]
[[Файл:Enfa-after.jpg|right|thumb|380px|Рис. 2. Перестроение.]]
Так как <tex>L</tex> {{---}} регулярный язык, то существует допускающий его ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>. Построим из <tex>M</tex> недетерминированный автомат с <tex>\varepsilon-</tex>переходами следующим образом: рассмотрим состояние <tex>q \in Q</tex>, из которого есть переходы в другие состояния (то есть начиная с <tex>q</tex> можно построить непустое слово, заканчивающееся в терминальной вершине). Тогда если какое-то слово проходит через это состояние, оно может быть зациклено таким образом, что его суффикс, начинающийся с <tex>q</tex>, станет префиксом нового слова, а префикс, заканчивающийся в <tex>q</tex> {{---}} суффиксом. Разделим автомат на две части <tex>A_1</tex> и <tex>A_2</tex> такие, что <tex>A_1</tex> будет содержать все вершины, из которых достижима <tex>q</tex>, а <tex>A_2</tex> {{---}} все вершины, которые достижимы из <tex>q</tex> (см. рис. 1). Заметим, что каждая вершина может содержаться в обеих частях одновременно, такое может случиться, если автомат <tex>M</tex> содержит циклы. Теперь перестроим автомат так, что он будет принимать слова "зацикленные" вокруг <tex>q</tex>, то есть начинающиеся с <tex>q</tex> и после достижения терминальной вершины продолжающиеся с <tex>q_0</tex> (см. рис. 2). Для этого стартовой вершиной сделаем <tex>q</tex> и построим от нее часть <tex>A_2</tex>. Теперь добавим состояние <tex>q_0</tex> и соединим с ним все терминальные состояния из <tex>A_2</tex> с помощью <tex>\varepsilon-</tex>переходов. Далее построим от <tex>q_0</tex> часть <tex>A_1</tex>. Добавим вершину <tex>q'</tex>, эквивалентную <tex>q</tex>, и сделаем ее терминальной. Данный автомат принимает слова, зацикленные вокруг выбранной вершины <tex>q</tex>. Мы хотим, чтобы автомат принимал слова, зацикленные вокруг любой такой <tex>q</tex>. Для этого создадим новую стартовую вершину <tex>q_0'</tex> и свяжем ее <tex>\varepsilon-</tex>переходами со всеми перестроенными автоматами (зацикленными вокруг всех подходящих <tex>q</tex>), в том числе и с изначальным автоматом. Построенный автомат допускает язык <tex>cycle(L)</tex>, следовательно, данный язык является регулярным.
}}
[[Файл:Ex_1_before.jpg|left|thumb|260px|Рис. 3. Автомат, принимающий язык <tex>L</tex>.]]
[[Файл:Ex_1_after.jpg|right|thumb|380px|Рис. 4. Автомат, принимающий язык <tex>cycle(L)</tex>.]]
Для лучшего понимания алгоритма перестроения автомата рассмотрим пример. 
На рис. 3 представлен автомат, допускающий язык <tex>L = \{ ab, abb, ac \}</tex>. На рис. 4 показано, как этот автомат был перестроен. Были добавлены части, зацикленные относительно вершин <tex>2</tex> и <tex>3</tex>. Появилась новая стартовая вершина <tex>0</tex>, которая связана <tex>\varepsilon-</tex>переходами с изначальным автоматом и его измененными версиями. Данный автомат распознает язык <tex>cycle(L) = \{ ab, abb, ac, ba, bba, ca, bab \}</tex>: первые три слова распознает первая часть, которая совпадает с изначальным автоматом; следующие три {{---}} вторая, перестроенная относительно вершины <tex>2</tex>; последнее слово распознает третья часть, зацикленная относительно вершины <tex>3</tex>.

Обсуждение участницы:Анна

2016-12-17T16:36:09Z

Анна: /* Язык alt(L, M) */

== Примеры доказательств ==
=== Язык <tex>half(L)</tex> ===
{{Определение
|definition = Определим <tex>half(L)</tex> как множество первых половин цепочек языка <tex>L</tex>, то есть множество <tex>\{ w \mid </tex> существует <tex>x</tex>, для которой <tex>wx \in L</tex>, причем <tex>|w| = |x| \}</tex>. }}
Например, если <tex>L = \{ \varepsilon, 0010, 011, 010110 \}</tex>, то <tex>half(L) = \{ \varepsilon, 00, 010 \}</tex>. Заметим, что цепочки нечетной длины не влияют на <tex>half(L)</tex>.

{{Утверждение
|id = st3
|statement =
Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык <tex>half(L)</tex> также регулярен.
|proof =
Так как <tex>L</tex> {{---}} регулярный язык, то существует ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>, допускающий его. Рассмотрим строку <tex>x</tex>. Для того, чтобы проверить, что <tex>x \in half(L)</tex>, нам надо убедиться, что существует строка <tex>y</tex> такой же длины, что и <tex>x</tex>, которая, будучи сконкатенированной с <tex>x</tex>, даст строку из <tex>L</tex>, то есть если на вход автомату подать <tex>xy</tex>, то в конце обработки мы окажемся в терминальном состоянии. Предположим, что автомат, закончив обработку <tex>x</tex>, находится в состоянии <tex>q_i</tex>, то есть <tex>\delta(q_0, x) = q_i</tex>. Мы должны проверить, что существует строка <tex>y, |y| = |x|,</tex> которая ведет из состояния <tex>q_i</tex> до какого-нибудь терминального состояния <tex>M</tex>, то есть <tex>\delta(q_i, y) \in F</tex>. 
Предположим, что мы прошли <tex>n</tex> вершин автомата, то есть <tex>|x| = n</tex>. Обозначим за <tex>S_n</tex> множество всех состояний, с которых можно попасть в терминальные за <tex>n</tex> шагов. Тогда <tex>q_i \in S_n \Leftrightarrow x \in half(L)</tex>. Если мы сможем отслеживать <tex>S_n</tex> и <tex>q_i</tex>, то сможем определять, верно ли, что <tex>x \in half(L)</tex>. Заметим, что <tex>S_0 \equiv F</tex>. Очевидно мы можем построить <tex>S_{n+1}</tex> зная <tex>S_n</tex> и <tex>\delta</tex>: <tex>S_{n+1} = prev(S_n) = \{ q \in Q \mid \exists a \in \Sigma, q' \in S_n, \delta(q, a) = q' \}</tex> {{---}} множество состояний, из которых есть переход в какое-либо состояние из <tex>S_n</tex> (по единственному символу). Теперь надо найти способ отслеживать и обновлять <tex>S_n</tex>. 
Построим ДКА <tex>M'</tex>, который будет хранить эту информацию в своих состояниях. Определим <tex>Q' = Q \times 2^Q</tex>, то есть каждое состояние <tex>M'</tex> {{---}} это пара из одиночного состояния из <tex>M</tex> и множества состояний из <tex>M</tex>. Функцию перехода <tex>\delta'</tex> автомата <tex>M'</tex> определим так, чтобы если по какой-то строке <tex>x</tex> длины <tex>n</tex> в автомате <tex>M</tex> мы перешли в состояние <tex>q_i</tex>, то по этой же строке в автомате <tex>M'</tex> мы перейдем в состояние <tex>(q_i, S_n)</tex>, где <tex>S_n</tex> {{---}} множество состояний из <tex>M</tex>, определенное выше. Вспомним приведенную выше функцию <tex>prev(S_n) = S_{n+1}</tex>. С ее помощью мы можем определить функцию перехода следующим образом: <tex>\delta'((q, S), a) = (\delta(q, a), prev(S))</tex>. Начальное состояние <tex>q_0' = (q_0, S_0) = (q_0, F)</tex>. Множество терминальных состояний {{---}} <tex>F' = \{ (q, S) \mid q \in S, S \in 2^Q \}</tex>. 
Теперь по индукции не сложно доказать, что <tex>\delta'(q_0', x) = (\delta(q_0, x), S_n)</tex>, где <tex>|x| = n</tex>. По определению множества терминальных вершин, автомат <tex>M'</tex> допускает строку <tex>x</tex> тогда и только тогда, когда <tex>\delta(q_0, x) \in S_n</tex>. Следовательно, автомат <tex>M'</tex> допускает язык <tex>half(L)</tex>.Таким образом, мы построили ДКА, который допускает язык <tex>half(L)</tex>. Следовательно, данный язык является регулярным.
}}
=== Язык <tex>alt(L, M)</tex> ===
{{Определение
|definition = Пусть <tex>w = w_1 w_2 \dots w_n</tex> и <tex>x = x_1 x_2 \dots x_n</tex>. Определим <tex>alt(w, x) = w_1 x_1 w_2 x_2 \dots w_n x_n</tex>. Распространим это определение на языки следующим образом: пусть <tex>L</tex> и <tex>M</tex> {{---}} два языка над одним алфавитом <tex>\Sigma</tex>. Тогда <tex>alt(L, M) = \{ alt(w, x) \mid |w| = |x|, w \in L, x \in M \}</tex>.}}
Например, если <tex>L = \{ 10, 00, 111, 1001 \}</tex> и <tex>M = \{ 11, 0101 \}</tex>, то <tex>alt(L, M) = \{ 1101, 0101, 10010011 \}</tex>.

{{Утверждение
|id = st4
|statement = Пусть <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки. Тогда <tex>alt(L, M)</tex> также является регулярным.
|proof = Так как <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки, то существуют ДКА <tex>D_L = \langle \Sigma , Q_L , q_{0L} , F_L, \delta_L \rangle</tex>, распознающий язык <tex>L</tex>, и <tex>D_M = \langle \Sigma , Q_M , q_{0M} , F_M, \delta_M \rangle</tex>, распознающий язык <tex>M</tex>. Построим автомат <tex>D_{alt}</tex>, который будет распознавать язык <tex>alt(L, M)</tex>. Идея следующая: каждое состояние этого автомата будем описывать тремя значениями <tex>(p, q, b)</tex>, где <tex>p \in Q_L</tex>, <tex>q \in Q_M</tex> и <tex>b \in \{ 1, 0 \}</tex>. Нам нужно организовать чередование переходов по состояниям автоматов, то есть если мы на определенном шаге перешли от одного состояния автомата <tex>D_L</tex> до другого, то на следующем мы обязаны совершить переход по состояниям автомата <tex>D_M</tex>. Для этого будем использовать третье значение {{---}} если <tex>b = 0</tex>, то будет двигаться по состояниям первого автомата, то есть <tex>p</tex> поменяется, <tex>q</tex> останется неизменной, <tex>b</tex> станет <tex>1</tex>, если <tex>b = 1</tex>, то, соответственно, все наоборот. То есть в зависимости от четности третьего параметра будем использовать две функции перехода. Важно, что на каждом шаге мы инвертируем значение <tex>b</tex>, что гарантирует чередование. Определим автомат <tex>D_{alt} = \langle \Sigma, Q', q_0', F', \delta' \rangle</tex> следующим образом:
# <tex>Q' = Q_L \times Q_M \times \{ 0, 1 \}</tex>
# <tex>q_0' = (q_{0L}, q_{0M}, 0)</tex>
# <tex>F' = F_L \times F_M \times \{ 0 \}</tex>
# <tex>\delta'((p, q, 0), a) = (\delta_L(p, a), q, 1)</tex> и <tex>\delta'((p, q, 1), a) = (p, \delta_M(q, a), 0)</tex>
Стартовая вершина имеет третий параметр <tex>b = 0</tex>, так как первое значение должно быть получено из автомата <tex>D_L</tex>. Аналогично все терминальные вершины должны иметь то же значение последнего параметра, так как количество переходов должно быть четным и последний переход должен был быть осуществлен по автомату <tex>D_M</tex>.
}}

=== Язык <tex>cycle(L)</tex> ===
{{Определение
|definition = Определим <tex>cycle(L)</tex> как множество <tex>\{ w \mid </tex> цепочку <tex>w</tex> можно представить в виде <tex>w = xy</tex>, где <tex>yx \in L \}</tex>. }}
Например, если <tex>L = \{ 01, 011 \}</tex>, то <tex>cycle(L) = \{ 01, 10, 011, 110, 101 \}</tex>.

{{Утверждение
|id = st5
|statement =
Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык <tex>cycle(L)</tex> также регулярен.
|proof =
[[Файл:Enfa_before.jpg|right|thumb|380px|Рис. 1. Разбиение автомата.]]
[[Файл:Enfa-after.jpg|right|thumb|380px|Рис. 2. Перестроение.]]
Так как <tex>L</tex> {{---}} регулярный язык, то существует допускающий его ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>. Построим из <tex>M</tex> недетерминированный автомат с <tex>\varepsilon-</tex>переходами следующим образом: рассмотрим состояние <tex>q \in Q</tex>, из которого есть переходы в другие состояния (то есть начиная с <tex>q</tex> можно построить непустое слово, заканчивающееся в терминальной вершине). Тогда если какое-то слово проходит через это состояние, оно может быть зациклено таким образом, что его суффикс, начинающийся с <tex>q</tex>, станет префиксом нового слова, а префикс, заканчивающийся в <tex>q</tex> {{---}} суффиксом. Разделим автомат на две части <tex>A_1</tex> и <tex>A_2</tex> такие, что <tex>A_1</tex> будет содержать все вершины, из которых достижима <tex>q</tex>, а <tex>A_2</tex> {{---}} все вершины, которые достижимы из <tex>q</tex> (см. рис. 1). Заметим, что каждая вершина может содержаться в обеих частях одновременно, такое может случиться, если автомат <tex>M</tex> содержит циклы. Теперь перестроим автомат так, что он будет принимать слова "зацикленные" вокруг <tex>q</tex>, то есть начинающиеся с <tex>q</tex> и после достижения терминальной вершины продолжающиеся с <tex>q_0</tex> (см. рис. 2). Для этого стартовой вершиной сделаем <tex>q</tex> и построим от нее часть <tex>A_2</tex>. Теперь добавим состояние <tex>q_0</tex> и соединим с ним все терминальные состояния из <tex>A_2</tex> с помощью <tex>\varepsilon-</tex>переходов. Далее построим от <tex>q_0</tex> часть <tex>A_1</tex>. Добавим вершину <tex>q'</tex>, эквивалентную <tex>q</tex>, и сделаем ее терминальной. Данный автомат принимает слова, зацикленные вокруг выбранной вершины <tex>q</tex>. Мы хотим, чтобы автомат принимал слова, зацикленные вокруг любой такой <tex>q</tex>. Для этого создадим новую стартовую вершину <tex>q_0'</tex> и свяжем ее <tex>\varepsilon-</tex>переходами со всеми перестроенными автоматами (зацикленными вокруг всех подходящих <tex>q</tex>), в том числе и с изначальным автоматом. Построенный автомат допускает язык <tex>cycle(L)</tex>, следовательно, данный язык является регулярным.
}}
[[Файл:Ex_1_before.jpg|left|thumb|260px|Рис. 3. Автомат, принимающий язык <tex>L</tex>.]]
[[Файл:Ex_1_after.jpg|right|thumb|380px|Рис. 4. Автомат, принимающий язык <tex>cycle(L)</tex>.]]
Для лучшего понимания алгоритма перестроения автомата рассмотрим пример. 
На рис. 3 представлен автомат, допускающий язык <tex>L = \{ ab, abb, ac \}</tex>. На рис. 4 показано, как этот автомат был перестроен. Были добавлены части, зацикленные относительно вершин <tex>2</tex> и <tex>3</tex>. Появилась новая стартовая вершина <tex>0</tex>, которая связана <tex>\varepsilon-</tex>переходами с изначальным автоматом и его измененными версиями. Данный автомат распознает язык <tex>cycle(L) = \{ ab, abb, ac, ba, bba, ca, bab \}</tex>: первые три слова распознает первая часть, которая совпадает с изначальным автоматом; следующие три {{---}} вторая, перестроенная относительно вершины <tex>2</tex>; последнее слово распознает третья часть, зацикленная относительно вершины <tex>3</tex>.

Обсуждение участницы:Анна

2016-12-15T08:32:10Z

Анна:

Файл:Enfa-after.jpg

2016-12-15T08:22:31Z

Анна: загружена новая версия «Файл:Enfa-after.jpg»

Файл:Enfa before.jpg

2016-12-15T08:19:03Z

Анна: загружена новая версия «Файл:Enfa before.jpg»

Файл:Ex 1 after.jpg

2016-12-15T08:15:24Z

Анна: загружена новая версия «Файл:Ex 1 after.jpg»

Файл:Ex 1 before.jpg

2016-12-15T08:12:09Z

Анна: загружена новая версия «Файл:Ex 1 before.jpg»

Обсуждение участницы:Анна

2016-12-14T21:04:29Z

Анна:

{{Определение
|definition = Определим <tex>half(L)</tex> как множество первых половин цепочек языка <tex>L</tex>, то есть множество <tex>\{ w \mid </tex> существует <tex>x</tex>, для которой <tex>wx \in L</tex>, причем <tex>|w| = |x| \}</tex>. }}
Например, если <tex>L = \{ \varepsilon, 0010, 011, 010110 \}</tex>, то <tex>half(L) = \{ \varepsilon, 00, 010 \}</tex>. Заметим, что цепочки нечетной длины не влияют на <tex>half(L)</tex>.
{{Определение
|definition = Определим <tex>cycle(L)</tex> как множество <tex>\{ w \mid </tex> цепочку <tex>w</tex> можно представить в виде <tex>w = xy</tex>, где <tex>yx \in L \}</tex>. }}
Например, если <tex>L = \{ 01, 011 \}</tex>, то <tex>cycle(L) = \{ 01, 10, 011, 110, 101 \}</tex>.

{{Утверждение
|id = st3
|statement =
Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык <tex>half(L)</tex> также регулярен.
|proof =
Так как <tex>L</tex> {{---}} регулярный язык, то существует ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>, допускающий его. Рассмотрим строку <tex>x</tex>. Для того, чтобы проверить, что <tex>x \in half(L)</tex>, нам надо убедиться, что существует строка <tex>y</tex> такой же длины, что и <tex>x</tex>, которая, будучи сконкатенированной с <tex>x</tex>, даст строку из <tex>L</tex>, то есть если на вход автомату подать <tex>xy</tex>, то в конце обработки мы окажемся в терминальном состоянии. Предположим, что автомат, закончив обработку <tex>x</tex>, находится в состоянии <tex>q_i</tex>, то есть <tex>\delta(q_0, x) = q_i</tex>. Мы должны проверить, что существует строка <tex>y, |y| = |x|,</tex> которая ведет из состояния <tex>q_i</tex> до какого-нибудь терминального состояния <tex>M</tex>, то есть <tex>\delta(q_i, y) \in F</tex>. 
Предположим, что мы прошли <tex>n</tex> вершин автомата, то есть <tex>|x| = n</tex>. Обозначим за <tex>S_n</tex> множество всех состояний, с которых можно попасть в терминальные за <tex>n</tex> шагов. Тогда <tex>q_i \in S_n \Leftrightarrow x \in half(L)</tex>. Если мы сможем отслеживать <tex>S_n</tex> и <tex>q_i</tex>, то сможем определять, верно ли, что <tex>x \in half(L)</tex>. Заметим, что <tex>S_0 \equiv F</tex>. Очевидно мы можем построить <tex>S_{n+1}</tex> зная <tex>S_n</tex> и <tex>\delta</tex>: <tex>S_{n+1} = prev(S_n) = \{ q \in Q \mid \exists a \in \Sigma, q' \in S_n, \delta(q, a) = q' \}</tex> {{---}} множество состояний, из которых есть переход в какое-либо состояние из <tex>S_n</tex> (по единственному символу). Теперь надо найти способ отслеживать и обновлять <tex>S_n</tex>. 
Построим ДКА <tex>M'</tex>, который будет хранить эту информацию в своих состояниях. Определим <tex>Q' = Q \times 2^Q</tex>, то есть каждое состояние <tex>M'</tex> {{---}} это пара из одиночного состояния из <tex>M</tex> и множества состояний из <tex>M</tex>. Функцию перехода <tex>\delta'</tex> автомата <tex>M'</tex> определим так, чтобы если по какой-то строке <tex>x</tex> длины <tex>n</tex> в автомате <tex>M</tex> мы перешли в состояние <tex>q_i</tex>, то по этой же строке в автомате <tex>M'</tex> мы перейдем в состояние <tex>(q_i, S_n)</tex>, где <tex>S_n</tex> {{---}} множество состояний из <tex>M</tex>, определенное выше. Вспомним приведенную выше функцию <tex>prev(S_n) = S_{n+1}</tex>. С ее помощью мы можем определить функцию перехода следующим образом: <tex>\delta'((q, S), a) = (\delta(q, a), prev(S))</tex>. Начальное состояние <tex>q_0' = (q_0, S_0) = (q_0, F)</tex>. Множество терминальных состояний {{---}} <tex>F' = \{ (q, S) \mid q \in S, S \in 2^Q \}</tex>. 
Теперь по индукции не сложно доказать, что <tex>\delta'(q_0', x) = (\delta(q_0, x), S_n)</tex>, где <tex>|x| = n</tex>. По определению множества терминальных вершин, автомат <tex>M'</tex> допускает строку <tex>x</tex> тогда и только тогда, когда <tex>\delta(q_0, x) \in S_n</tex>. Следовательно, автомат <tex>M'</tex> допускает язык <tex>half(L)</tex>.Таким образом, мы построили ДКА, который допускает язык <tex>half(L)</tex>. Следовательно, данный язык является регулярным.
}}

{{Утверждение
|id = st4
|statement =
Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык <tex>cycle(L)</tex> также регулярен.
|proof =
[[Файл:Enfa_before.jpg|left|thumb|240px|Рис. 1. Разбиение автомата.]]
[[Файл:Enfa-after.jpg|right|thumb|240px|Рис. 2. Перестроение.]]
Так как <tex>L</tex> {{---}} регулярный язык, то существует допускающий его ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>. Построим из <tex>M</tex> недетерминированный автомат с <tex>\varepsilon-</tex>переходами следующим образом: рассмотрим состояние <tex>q \in Q</tex>, из которого есть переходы в другие состояния (то есть начиная с <tex>q</tex> можно построить непустое слово, заканчивающееся в терминальной вершине). Тогда если какое-то слово проходит через это состояние, оно может быть зациклено таким образом, что его суффикс, начинающийся с <tex>q</tex>, станет префиксом нового слова, а префикс, заканчивающийся в <tex>q</tex> {{---}} суффиксом. Разделим автомат на две части <tex>A_1</tex> и <tex>A_2</tex> такие, что <tex>A_1</tex> будет содержать все вершины, из которых достижима <tex>q</tex>, а <tex>A_2</tex> {{---}} все вершины, которые достижимы из <tex>q</tex> (см. рис. 1). Заметим, что каждая вершина может содержаться в обеих частях одновременно, такое может случиться, если автомат <tex>M</tex> содержит циклы. Теперь перестроим автомат так, что он будет принимать слова "зацикленные" вокруг <tex>q</tex>, то есть начинающиеся с <tex>q</tex> и после достижения терминальной вершины продолжающиеся с <tex>q_0</tex> (см. рис. 2). Для этого стартовой вершиной сделаем <tex>q</tex> и построим от нее часть <tex>A_2</tex>. Теперь добавим состояние <tex>q_0</tex> и соединим с ним все терминальные состояния из <tex>A_2</tex> с помощью <tex>\varepsilon-</tex>переходов. Далее построим от <tex>q_0</tex> часть <tex>A_1</tex>. Добавим вершину <tex>q'</tex>, эквивалентную <tex>q</tex>, и сделаем ее терминальной. Данный автомат принимает слова, зацикленные вокруг выбранной вершины <tex>q</tex>. Мы хотим, чтобы автомат принимал слова, зацикленные вокруг любой такой <tex>q</tex>. Для этого создадим новую стартовую вершину <tex>q_0'</tex> и свяжем ее <tex>\varepsilon-</tex>переходами со всеми перестроенными автоматами (зацикленными вокруг всех подходящих <tex>q</tex>), в том числе и с изначальным автоматом. Построенный автомат допускает язык <tex>cycle(L)</tex>, следовательно, данный язык является регулярным.
}}
[[Файл:Ex_1_before.jpg|left|thumb|240px|Рис. 3. Автомат, принимающий язык <tex>L</tex>.]]
[[Файл:Ex_1_after.jpg|right|thumb|300px|Рис. 4. Автомат, принимающий язык <tex>cycle(L)</tex>.]]
Для лучшего понимания алгоритма перестроения автомата рассмотрим пример. 
На рис. 3 представлен автомат, допускающий язык <tex>L = \{ ab, abb, ac \}</tex>. На рис. 4 показано, как этот автомат был перестроен. Были добавлены части, зацикленные относительно вершин <tex>2</tex> и <tex>3</tex>. Появилась новая стартовая вершина <tex>0</tex>, которая связана <tex>\varepsilon-</tex>переходами с изначальным автоматом и его измененными версиями. Данный автомат распознает язык <tex>cycle(L) = \{ ab, abb, ac, ba, bba, ca, bab \}</tex>: первые три слова распознает первая часть, которая совпадает с изначальным автоматом; следующие три {{---}} вторая, перестроенная относительно вершины <tex>2</tex>; последнее слово распознает третья часть, зацикленная относительно вершины <tex>3</tex>.

Обсуждение участницы:Анна

2016-12-14T21:01:42Z

Анна:

{{Определение
|definition = Определим <tex>half(L)</tex> как множество первых половин цепочек языка <tex>L</tex>, то есть множество <tex>\{ w \mid </tex> существует <tex>x</tex>, для которой <tex>wx \in L</tex>, причем <tex>|w| = |x| \}</tex>. }}
Например, если <tex>L = \{ \varepsilon, 0010, 011, 010110 \}</tex>, то <tex>half(L) = \{ \varepsilon, 00, 010 \}</tex>. Заметим, что цепочки нечетной длины не влияют на <tex>half(L)</tex>.
{{Определение
|definition = Определим <tex>cycle(L)</tex> как множество <tex>\{ w \mid </tex> цепочку <tex>w</tex> можно представить в виде <tex>w = xy</tex>, где <tex>yx \in L \}</tex>. }}
Например, если <tex>L = \{ 01, 011 \}</tex>, то <tex>cycle(L) = \{ 01, 10, 011, 110, 101 \}</tex>.

{{Утверждение
|id = st3
|statement =
Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык <tex>half(L)</tex> также регулярен.
|proof =
Так как <tex>L</tex> {{---}} регулярный язык, то существует ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>, допускающий его. Рассмотрим строку <tex>x</tex>. Для того, чтобы проверить, что <tex>x \in half(L)</tex>, нам надо убедиться, что существует строка <tex>y</tex> такой же длины, что и <tex>x</tex>, которая, будучи сконкатенированной с <tex>x</tex>, даст строку из <tex>L</tex>, то есть если на вход автомату подать <tex>xy</tex>, то в конце обработки мы окажемся в терминальном состоянии. Предположим, что автомат, закончив обработку <tex>x</tex>, находится в состоянии <tex>q_i</tex>, то есть <tex>\delta(q_0, x) = q_i</tex>. Мы должны проверить, что существует строка <tex>y, |y| = |x|,</tex> которая ведет из состояния <tex>q_i</tex> до какого-нибудь терминального состояния <tex>M</tex>, то есть <tex>\delta(q_i, y) \in F</tex>. 
Предположим, что мы прошли <tex>n</tex> вершин автомата, то есть <tex>|x| = n</tex>. Обозначим за <tex>S_n</tex> множество всех состояний, с которых можно попасть в терминальные за <tex>n</tex> шагов. Тогда <tex>q_i \in S_n \Leftrightarrow x \in half(L)</tex>. Если мы сможем отслеживать <tex>S_n</tex> и <tex>q_i</tex>, то сможем определять, верно ли, что <tex>x \in half(L)</tex>. Заметим, что <tex>S_0 \equiv F</tex>. Очевидно мы можем построить <tex>S_{n+1}</tex> зная <tex>S_n</tex> и <tex>\delta</tex>: <tex>S_{n+1} = prev(S_n) = \{ q \in Q \mid \exists a \in \Sigma, q' \in S_n, \delta(q, a) = q' \}</tex> {{---}} множество состояний, из которых есть переход в какое-либо состояние из <tex>S_n</tex> (по единственному символу). Теперь надо найти способ отслеживать и обновлять <tex>S_n</tex>. 
Построим ДКА <tex>M'</tex>, который будет хранить эту информацию в своих состояниях. Определим <tex>Q' = Q \times 2^Q</tex>, то есть каждое состояние <tex>M'</tex> {{---}} это пара из одиночного состояния из <tex>M</tex> и множества состояний из <tex>M</tex>. Функцию перехода <tex>\delta'</tex> автомата <tex>M'</tex> определим так, чтобы если по какой-то строке <tex>x</tex> длины <tex>n</tex> в автомате <tex>M</tex> мы перешли в состояние <tex>q_i</tex>, то по этой же строке в автомате <tex>M'</tex> мы перейдем в состояние <tex>(q_i, S_n)</tex>, где <tex>S_n</tex> {{---}} множество состояний из <tex>M</tex>, определенное выше. Вспомним приведенную выше функцию <tex>prev(S_n) = S_{n+1}</tex>. С ее помощью мы можем определить функцию перехода следующим образом: <tex>\delta'((q, S), a) = (\delta(q, a), prev(S))</tex>. Начальное состояние <tex>q_0' = (q_0, S_0) = (q_0, F)</tex>. Множество терминальных состояний {{---}} <tex>F' = \{ (q, S) \mid q \in S, S \in 2^Q \}</tex>. 
Теперь по индукции не сложно доказать, что <tex>\delta'(q_0', x) = (\delta(q_0, x), S_n)</tex>, где <tex>|x| = n</tex>. По определению множества терминальных вершин, автомат <tex>M'</tex> допускает строку <tex>x</tex> тогда и только тогда, когда <tex>\delta(q_0, x) \in S_n</tex>. Следовательно, автомат <tex>M'</tex> допускает язык <tex>half(L)</tex>.Таким образом, мы построили ДКА, который допускает язык <tex>half(L)</tex>. Следовательно, данный язык является регулярным.
}}

{{Утверждение
|id = st4
|statement =
Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык <tex>cycle(L)</tex> также регулярен.
|proof =
[[Файл:Enfa_before.jpg|left|thumb|240px|Рис. 1. Разбиение автомата.]]
[[Файл:Enfa-after.jpg|right|thumb|240px|Рис. 2. Перестроение.]]
Так как <tex>L</tex> {{---}} регулярный язык, то существует допускающий его ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>. Построим из <tex>M</tex> недетерминированный автомат с <tex>\varepsilon-</tex>переходами следующим образом: рассмотрим состояние <tex>q \in Q</tex>, из которого есть переходы в другие состояния (то есть начиная с <tex>q</tex> можно построить непустое слово, заканчивающееся в терминальной вершине). Тогда если какое-то слово проходит через это состояние, оно может быть зациклено таким образом, что его суффикс, начинающийся с <tex>q</tex>, станет префиксом нового слова, а префикс, заканчивающийся в <tex>q</tex> {{---}} суффиксом. Разделим автомат на две части <tex>A_1</tex> и <tex>A_2</tex> такие, что <tex>A_1</tex> будет содержать все вершины, из которых достижима <tex>q</tex>, а <tex>A_2</tex> {{---}} все вершины, которые достижимы из <tex>q</tex> (см. рис. 1). Заметим, что каждая вершина может содержаться в обеих частях одновременно, такое может случиться, если автомат <tex>M</tex> содержит циклы. Теперь перестроим автомат так, что он будет принимать слова, "зацикленные" вокруг <tex>q</tex>, то есть начинающиеся с <tex>q</tex> и после достижения терминальной вершины продолжающиеся с <tex>q_0</tex> (см. рис. 2). Для этого стартовой вершиной сделаем <tex>q</tex> и построим от нее часть <tex>A_2</tex>. Теперь добавим состояние <tex>q_0</tex> и соединим с ним все терминальные состояния из <tex>A_2</tex> с помощью <tex>\varepsilon-</tex>переходов. Далее построим от <tex>q_0</tex> часть <tex>A_1</tex>. Добавим вершину <tex>q'</tex>, эквивалентную <tex>q</tex>, и сделаем ее терминальной. Данный автомат принимает слова, зацикленные вокруг выбранной вершины <tex>q</tex>. Мы хотим, чтобы автомат принимал слова, зацикленные вокруг любой такой <tex>q</tex>. Для этого создадим новую стартовую вершину <tex>q_0'</tex> и свяжем ее <tex>\varepsilon-</tex>переходами со всеми перестроенными автоматами (зацикленными вокруг всех подходящих <tex>q</tex>), в том числе и с изначальным автоматом. Построенный автомат допускает язык <tex>cycle(L)</tex>, следовательно, данный язык является регулярным.
}}
[[Файл:Ex_1_before.jpg|left|thumb|240px|Рис. 3. Автомат, принимающий язык <tex>L</tex>.]]
[[Файл:Ex_1_after.jpg|right|thumb|300px|Рис. 4. Автомат, принимающий язык <tex>cycle(L)</tex>.]]
Для лучшего понимания алгоритма перестроения автомата рассмотрим пример. 
На рис. 3 представлен автомат, допускающий язык <tex>L = \{ ab, abb, ac \}</tex>. На рис. 4 показано, как этот автомат был перестроен. Были добавлены части, зацикленные относительно вершин <tex>2</tex> и <tex>3</tex>. Появилась новая стартовая вершина <tex>0</tex>, которая связана <tex>\varepsilon-</tex>переходами с изначальным автоматом и его измененными версиями. Данный автомат распознает язык <tex>cycle(L) = \{ ab, abb, ac, ba, bba, ca, bab \}</tex>: первые три слова распознает первая часть, которая совпадает с изначальным автоматом; следующие три {{---}} вторая, перестроенная относительно вершины <tex>2</tex>; последнее слово распознает третья часть, зацикленная относительно вершины <tex>3</tex>.

Файл:Ex 2 before.jpg

2016-12-14T20:51:04Z

Анна:

Файл:Ex 1 after.jpg

2016-12-14T20:25:27Z

Анна:

Файл:Ex 1 before.jpg

2016-12-14T20:21:30Z

Анна:

Обсуждение участницы:Анна

2016-12-14T18:45:59Z

Анна:

{{Определение
|definition = Определим <tex>half(L)</tex> как множество первых половин цепочек языка <tex>L</tex>, то есть множество <tex>\{ w \mid </tex> существует <tex>x</tex>, для которой <tex>wx \in L</tex>, причем <tex>|w| = |x| \}</tex>. }}
Например, если <tex>L = \{ \varepsilon, 0010, 011, 010110 \}</tex>, то <tex>half(L) = \{ \varepsilon, 00, 010 \}</tex>. Заметим, что цепочки нечетной длины не влияют на <tex>half(L)</tex>.
{{Определение
|definition = Определим <tex>cycle(L)</tex> как множество <tex>\{ w \mid </tex> цепочку <tex>w</tex> можно представить в виде <tex>w = xy</tex>, где <tex>yx \in L \}</tex>. }}
Например, если <tex>L = \{ 01, 011 \}</tex>, то <tex>cycle(L) = \{ 01, 10, 011, 110, 101 \}</tex>.

{{Утверждение
|id = st3
|statement =
Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык <tex>half(L)</tex> также регулярен.
|proof =
Так как <tex>L</tex> {{---}} регулярный язык, то существует ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>, допускающий его. Рассмотрим строку <tex>x</tex>. Для того, чтобы проверить, что <tex>x \in half(L)</tex>, нам надо убедиться, что существует строка <tex>y</tex> такой же длины, что и <tex>x</tex>, которая, будучи сконкатенированной с <tex>x</tex>, даст строку из <tex>L</tex>, то есть если на вход автомату подать <tex>xy</tex>, то в конце обработки мы окажемся в терминальном состоянии. Предположим, что автомат, закончив обработку <tex>x</tex>, находится в состоянии <tex>q_i</tex>, то есть <tex>\delta(q_0, x) = q_i</tex>. Мы должны проверить, что существует строка <tex>y, |y| = |x|,</tex> которая ведет из состояния <tex>q_i</tex> до какого-нибудь терминального состояния <tex>M</tex>, то есть <tex>\delta(q_i, y) \in F</tex>. 
Предположим, что мы прошли <tex>n</tex> вершин автомата, то есть <tex>|x| = n</tex>. Обозначим за <tex>S_n</tex> множество всех состояний, с которых можно попасть в терминальные за <tex>n</tex> шагов. Тогда <tex>q_i \in S_n \Leftrightarrow x \in half(L)</tex>. Если мы сможем отслеживать <tex>S_n</tex> и <tex>q_i</tex>, то сможем определять, верно ли, что <tex>x \in half(L)</tex>. Заметим, что <tex>S_0 \equiv F</tex>. Очевидно мы можем построить <tex>S_{n+1}</tex> зная <tex>S_n</tex> и <tex>\delta</tex>: <tex>S_{n+1} = prev(S_n) = \{ q \in Q \mid \exists a \in \Sigma, q' \in S_n, \delta(q, a) = q' \}</tex> {{---}} множество состояний, из которых есть переход в какое-либо состояние из <tex>S_n</tex> (по единственному символу). Теперь надо найти способ отслеживать и обновлять <tex>S_n</tex>. 
Построим ДКА <tex>M'</tex>, который будет хранить эту информацию в своих состояниях. Определим <tex>Q' = Q \times 2^Q</tex>, то есть каждое состояние <tex>M'</tex> {{---}} это пара из одиночного состояния из <tex>M</tex> и множества состояний из <tex>M</tex>. Функцию перехода <tex>\delta'</tex> автомата <tex>M'</tex> определим так, чтобы если по какой-то строке <tex>x</tex> длины <tex>n</tex> в автомате <tex>M</tex> мы перешли в состояние <tex>q_i</tex>, то по этой же строке в автомате <tex>M'</tex> мы перейдем в состояние <tex>(q_i, S_n)</tex>, где <tex>S_n</tex> {{---}} множество состояний из <tex>M</tex>, определенное выше. Вспомним приведенную выше функцию <tex>prev(S_n) = S_{n+1}</tex>. С ее помощью мы можем определить функцию перехода следующим образом: <tex>\delta'((q, S), a) = (\delta(q, a), prev(S))</tex>. Начальное состояние <tex>q_0' = (q_0, S_0) = (q_0, F)</tex>. Множество терминальных состояний {{---}} <tex>F' = \{ (q, S) \mid q \in S, S \in 2^Q \}</tex>. 
Теперь по индукции не сложно доказать, что <tex>\delta'(q_0', x) = (\delta(q_0, x), S_n)</tex>, где <tex>|x| = n</tex>. По определению множества терминальных вершин, автомат <tex>M'</tex> допускает строку <tex>x</tex> тогда и только тогда, когда <tex>\delta(q_0, x) \in S_n</tex>. Следовательно, автомат <tex>M'</tex> допускает язык <tex>half(L)</tex>.Таким образом, мы построили ДКА, который допускает язык <tex>half(L)</tex>. Следовательно, данный язык является регулярным.
}}

{{Утверждение
|id = st4
|statement =
Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык <tex>cycle(L)</tex> также регулярен.
|proof =
[[Файл:Enfa_before.jpg|left|thumb|240px|Рис. 1. Разбиение автомата.]]
[[Файл:Enfa-after.jpg|right|thumb|240px|Рис. 2. Перестроение.]]
Так как <tex>L</tex> {{---}} регулярный язык, то существует допускающий его ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>. Построим из <tex>M</tex> недетерминированный автомат с <tex>\varepsilon-</tex>переходами следующим образом: рассмотрим состояние <tex>q \in Q</tex>, из которого есть переходы в другие состояния (то есть начиная с <tex>q</tex> можно построить непустое слово, заканчивающееся в терминальной вершине). Тогда если какое-то слово проходит через это состояние, оно может быть зациклено таким образом, что его суффикс, начинающийся с <tex>q</tex>, станет префиксом нового слова, а префикс, заканчивающийся в <tex>q</tex> {{---}} суффиксом. Разделим автомат на две части <tex>A_1</tex> и <tex>A_2</tex> такие, что <tex>A_1</tex> будет содержать все вершины, из которых достижима <tex>q</tex>, а <tex>A_2</tex> {{---}} все вершины, которые достижимы из <tex>q</tex> (см. рис. 1). Заметим, что каждая вершина может содержаться в обеих частях одновременно, такое может случиться, если автомат <tex>M</tex> содержит циклы. Теперь перестроим автомат так, что он будет принимать слова, "зацикленные" вокруг <tex>q</tex>, то есть начинающиеся с <tex>q</tex> и после достижения терминальной вершины продолжающиеся с <tex>q_0</tex>(см. рис. 2). Для этого стартовой вершиной сделаем <tex>q</tex> и построим от нее часть <tex>A_2</tex>. Теперь добавим состояние <tex>q_0</tex> и соединим с ним все терминальные состояния из <tex>A_2</tex> с помощью <tex>\varepsilon-</tex>переходов. Далее построим от <tex>q_0</tex> часть <tex>A_1</tex>. Добавим вершину <tex>q'</tex>, эквивалентную <tex>q</tex>, и сделаем ее терминальной. Данный автомат принимает слова, зацикленные вокруг выбранной вершины <tex>q</tex>. Мы хотим, чтобы автомат принимал слова, зацикленные вокруг любой такой <tex>q</tex>. Для этого создадим новую стартовую вершину <tex>q_0'</tex> и свяжем ее со всеми перестроенными автоматами (зацикленными вокруг всех подходящих <tex>q</tex>), в том числе и с изначальным автоматом. Построенный автомат допускает язык <tex>cycle(L)</tex>, следовательно, данный язык является регулярным.
}}

Файл:Enfa-after.jpg

2016-12-14T18:33:21Z

Анна:

Файл:Enfa before.jpg

2016-12-14T18:08:43Z

Анна:

Обсуждение участницы:Анна

2016-12-12T19:32:15Z

Анна:

Обсуждение участницы:Анна

2016-12-12T17:45:44Z

Анна:

Обсуждение участницы:Анна

2016-12-12T11:25:10Z

Анна:

Opij1SumTi

2016-06-08T20:04:02Z

Анна: /* Асимптотика */

<tex dpi = "200"> O \mid p_{i,j} = 1 \mid \sum T_{i} </tex>
{{Задача
|definition=
Дано <tex>m</tex> одинаковых станков, которые работают параллельно, и <tex>n</tex> работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания <tex>d_i</tex> {{---}} время, до которого она должна быть выполнена. Необходимо минимизировать суммарную [[Классификация_задач#Критерий оптимизации|медлительность]].
}}
== Описание алгоритма ==
=== Идея ===
Будем полагать, что работы заданы в порядке неубывания их дедлайнов, то есть <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>.
{{Лемма
|statement=
Пусть есть работы <tex>1 \ldots n</tex> с дедлайнами <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Тогда существует оптимальное расписание, в котором времена завершения работ идут в том же порядке, то есть <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex>.
|proof=
Рассмотрим две работы <tex>i</tex> и <tex>j</tex> из какого-либо оптимального расписания такие, что <tex>C_i > C_j</tex> и <tex>d_i < d_j</tex>. Поменяем эти работы в расписании местами, то есть <tex>C'_i = C_j</tex> и <tex>C'_j = C_i</tex>. Если они обе успевали выполниться вовремя, то это свойство сохранится, так как <tex>d_i < d_j</tex>, значит по-прежнему <tex>T_i = 0</tex> и <tex>T_j = 0</tex>, то есть значение целевой функции мы не ухудшили и расписание осталось оптимальным. Если обе работы не успевали выполниться вовремя, то когда мы поменяем их местами ничего не изменится, то есть значение целевой функции останется прежним, так как мы не меняли значения времен окончаний, а только поменяли их местами. Если работа <tex>j</tex> успевала выполниться, а <tex>i</tex> {{---}} нет, то мы снова не ухудшим значение целевой функции. Покажем это. До того, как мы поменяли работы местами, было <tex>T_i + T_j = C_i - d_i</tex>, так как <tex>T_j = 0</tex>. После того, как мы поменяли работы местами, <tex>T_i + T_j = C'_i - d_i + C'_j - d_j = C_j - d_i + C_i - d_j = C_i - d_i + (C_j - d_j)</tex>. Но так как работа <tex>j</tex> успевает выполниться до дедлайна, то <tex>C_j - d_j \leqslant 0</tex>.
}}
Далее будем рассматривать только оптимальное расписание со свойством <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex>.
{{Теорема
|statement=
Всегда существует оптимально расписание такое, что в нем <tex>C_i \leqslant m + i - 1</tex> для любого <tex>i = 1 \ldots n</tex>, где <tex>m</tex> {{---}} количество станков.
|proof=
Рассмотрим оптимальное расписание <tex>S^*</tex>, в котором для любого <tex>i = 1 \ldots k - 1</tex> выполняется <tex>C_i \leqslant m + i - 1</tex>, но <tex>C_k > m + k - 1</tex>, где <tex>k</tex> максимально среди всех возможных. Для начала покажем, что <tex>k</tex> не меньше <tex>2</tex>. Пусть есть оптимальное расписание, у которого <tex>C_1 > m</tex>. Это значит, что есть период времени <tex>t</tex> такой, что первая работа выполняется в момент <tex>t</tex> и не выполняется в <tex>t - 1</tex>. Поменяем эти периоды времени местами. То есть все работы, которые выполнялись в момент <tex>t - 1</tex>, будут выполняться на тех же станках, но в момент <tex>t</tex>, и наоборот. Значение <tex>C_i</tex> для каждой работы <tex>i</tex> не увеличится, так как <tex>C_1</tex> было минимальным из них, а значит ни одна работа не могла быть закончена раньше периода времени <tex>t</tex>. Будем продолжать этот процесс, пока не будет выполнено равенство <tex>C_1 = m</tex>. 
Теперь пусть <tex>C_k = m + k + t</tex>, где <tex>t \geqslant 0</tex>. Будем называть ''итерацией обработки'' работы обработку на одной машине. Разобьем все работы на три множества:
* множество <tex>A</tex> будет содержать все итерации обработки работ <tex>i = 1 \ldots k - 1</tex>
* множество <tex>B</tex> {{---}} все итерации, запланированные в расписании <tex>S^*</tex> строго после момента времени <tex>k + m + t</tex>
* множество <tex>C</tex> {{---}} итерации обработки работ <tex>i = k + 1 \ldots n</tex>, которые в <tex>S^*</tex> запланированы на время <tex>k + m + t</tex> и раньше
Таким образом, мы имеем три непересекающихся множества, которые вместе с работой <tex>k</tex> покрывают все итерации всех работ. 
Построим новое расписание <tex>S^*</tex>. Для начала расставим все работы из множества <tex>A \cup B</tex> так же, как они были запланированы в расписании <tex>S^*</tex>. Так как <tex>C_i \leqslant m + i - 1</tex> для <tex>i = 1 \ldots k - 1</tex>, ни одна итерация обработки в множестве <tex>B</tex> не поставлена раньше момента времени <tex>k + m + t</tex> и к моменту времени <tex>C_k = m + k + t</tex> выполнено <tex>k</tex> работ, то это значит, что между моментами времени <tex>1</tex> и <tex>k + m - 1</tex> на каждой машине есть <tex>m</tex> различных простоев, то есть моментов, когда на ней ничего не обрабатывается. Значит, мы всегда сможем поставить на эти простои итерации обработки работы <tex>k</tex>, даже если эти простои пересекаются. Таким образом, <tex>C_k \leqslant m + k - 1</tex>. 
Теперь назначим машины для операций из множества <tex>C</tex>. До момента времени <tex>k + m + t</tex> сейчас распланировано ровно <tex>k</tex> работ, так как по определению работы из множества <tex>B</tex> запланированы на время строго большее <tex>k + m + t</tex>. Значит, между моментами времени <tex>1</tex> и <tex>k + m + t</tex> есть <tex>k + m + t - k = m + t</tex> различных простоев на каждой машине. Исходя из определения множества <tex>C</tex> и того, что к моменту <tex>k + m + t</tex> распланировано <tex>km</tex> итераций обработок, приходим к неравенству <tex>|C| \leqslant (k + m + t)m - km = (m + t)m</tex>. Значит, мы можем распланировать итерации из множества <tex>C</tex> не позднее момента <tex>k + m + t</tex>. Таим образом, мы снова построили расписание для задачи open shop, которое так же является оптимальным, так как для множеств <tex>A</tex> и <tex>B</tex> все осталось как в оптимальном расписании <tex>S^*</tex>, работу <tex>k</tex> мы научились выполнять быстрее, а для множества <tex>C</tex> ответ был не ухудшен. Любая работа <tex>j</tex>, итерации обработки которой принадлежат множеству <tex>C</tex>, имела время окончания <tex>C_j \geqslant m + k + t</tex>. Однако это противоречит тому, что мы выбрали максимальное <tex>k</tex>.
}}
Отсортируем работы в порядке неуменьшения дедлайнов. Для текущей работы <tex>i</tex> вычислим ''лимит'' <tex>T_i</tex> {{---}} время, до которого закончится обработка данной работы, то есть <tex>1 \leqslant t_1 < t_2 < \ldots < t_m \leqslant T_i </tex>, где <tex>t_j</tex>, <tex>j = 1 \ldots m</tex> {{---}} периоды обработки работы <tex>i</tex>.
Будем выбирать эти периоды среди моментов времени, в которые выполняется наименьшее число работ.

=== Псевдокод ===
Определим ''вектор частот'' <tex>h[t]</tex> {{---}} количество работ во временном интервале <tex>t</tex>. Работы отсортированы в порядке <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>.

'''function''' scheduler():
'''int''' <tex>h[m + n - 1]</tex>
'''vector<int>''' <tex>s[n]</tex>
'''fill'''(<tex>h,\ 0</tex>)
'''fill'''(<tex>s,\ \varnothing</tex>)
'''for''' <tex>i = 1</tex> '''to''' <tex>n</tex>
'''if''' <tex>d_i < m + i - 1</tex>
вычислим <tex>z</tex> {{---}} количество временных интервалов <tex>t = 1 \ldots d_i</tex>, таких, что <tex>h[t] < m</tex>
'''if''' <tex>z \geqslant m</tex>
<tex>T_i = d_i</tex>
'''else'''
<tex>T_i = d_i + m - z</tex>
'''else'''
<tex>T_i = m + i - 1</tex>
вычислим <tex>m</tex> периодов <tex>1 \leqslant t_1 < t_2 < \ldots < t_m \leqslant T_i </tex> с минимальными значениями <tex>h[t_j]</tex>
'''for''' <tex>j = 1</tex> '''to''' <tex>m</tex>
<tex>s[i] = s[i] \cup \{t_j - 1\}</tex> // ставим работу <tex>i</tex> на время <tex>[t_j - 1, t_j]</tex>
<tex>h[t_j] = h[t_j] + 1</tex>
'''return''' <tex>s</tex>

=== Асимптотика ===
Алгоритм может работать за <tex>O(nm)</tex>. Чтобы получить алгоритм с такой сложностью, мы распределяем работы так, чтобы после каждого шага <tex>i</tex> сохранялся инвариант <tex>l_1 \geqslant l_2 \geqslant \ldots \geqslant l_m </tex> при <tex>l_1 \geqslant T_i</tex>, где <tex>l_j</tex> такое, что на станке <tex>M_j</tex> все временные промежутки <tex>1 \ldots l_j</tex> заняты.
На первом шаге алгоритма <tex> l_1 = l_2 = \ldots = l_m = 0 </tex>. Предположим, что инвариант сохранился после шага <tex> i - 1 </tex>. Тогда <tex> T_{i-1} \leqslant T_i </tex> и, для сохранения инварианта, распределим работу в следующем порядке: 
<center><tex>l_1 + 1 \ldots T_i</tex> на станке <tex> M_1 </tex>, 
<tex>l_2 + 1 \ldots l_1</tex> на станке <tex> M_2 </tex>, 
<tex> \vdots </tex> 
<tex>l_m + 1 \ldots l_{m-1}</tex> на станке <tex> M_1 </tex>.
</center>
Таким образом, мы получаем распределение одной работы по <tex>m</tex> станкам для <tex>n</tex> работ. Итоговая асимптотика {{---}} <tex>O(nm)</tex>.

== Доказательство корректности ==
{{Теорема
|statement=Алгоритм строит оптимальное расписание для задачи <tex> O \mid p_{i,j} = 1 \mid \sum T_{i} </tex>
|proof= Воспользуемся для доказательства леммой и теоремой из предыдущего пункта. Из них мы знаем, что существует оптимальное расписание, для которого выполняются свойства <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex> и <tex>C_i \leqslant m + i - 1</tex> для любого <tex>i = 1 \ldots n</tex>, где <tex>m</tex> {{---}} число станков. Пусть <tex>B</tex> {{---}} оптимальное расписание, которое удовлетворяет свойству, по которому работы <tex>1 \ldots k - 1 </tex> поставлены в те же временные промежутки, в которых они оказались следуя нашему расписанию <tex>A</tex>. Более того, предположим, что <tex>B</tex> было выбрано так, что <tex>k</tex> максимально.
Пусть <tex>C_k > T_k</tex>. С того момента, как работа <tex>k</tex> поставлена в расписании <tex>A</tex> перед <tex>T_k</tex>, определим временной промежуток <tex>t \leqslant T_k </tex> в месте, где работа <tex>k</tex> не выполняется в <tex>B</tex>. Тогда в самом расписании <tex>B</tex> этот промежуток либо так же пустой, либо он занят работой <tex>r > k</tex>.
* Если он пустой, мы перемещаем операцию <tex>k</tex>, которая была распределена в промежуток <tex>C_k</tex>, в этот промежуток.
* Если работа <tex>r</tex> стоит во время <tex>t</tex>, но не во время <tex>C_k</tex>, то мы меняем между собой операции работ <tex>k</tex> и <tex>r</tex>.
* Если работа <tex>r</tex> поставлена во время <tex>t</tex> и <tex>C_k</tex>, то либо тут есть пустое место в <tex>C_r + 1</tex>, либо там должна быть работа, назовем ее <tex>v</tex>, которая поставлена на время <tex>C_r + 1</tex>, но не поставлена в <tex>C_k</tex>.
Работа <tex>v</tex> точно там есть, потому что <tex>r</tex> и <tex>k</tex> поставлены на время <tex>C_k</tex>, но не поставлены на время <tex>C_r + 1</tex>. Если свободный промежуток есть, тогда переставим работу <tex>r</tex> со времени <tex>t</tex> на время <tex>C_r + 1</tex> и работу <tex>k</tex> со времени <tex>C_k</tex> на <tex>t</tex>. Иначе мы можем переместить работу <tex>r</tex> с времени <tex>t</tex> на время <tex>C_r + 1</tex>, <tex>k</tex> c <tex>C_k</tex> на <tex>t</tex>, и <tex>v</tex> с <tex>C_r + 1</tex> на <tex>C_k</tex>. Тогда <tex>C_k</tex> должно уменьшиться как минимум на один, а <tex>C_r</tex> увеличится не больше, чем на один.
Если мы продолжим так действовать, мы получим оптимальное расписание <tex>B'</tex> с <tex>C_k \leqslant T_k</tex>, в котором работы <tex>1 \ldots k-1</tex> расположены так же, как в расписании <tex>A</tex>.
Пусть <tex>h</tex> {{---}} вектор частот для части расписания из работ от <tex>1</tex> до <tex>k - 1</tex>. Предположим, что <tex>h(t') < h(t)</tex> и работа <tex>k</tex> выполняется во временной промежуток <tex>t</tex>, но не выполняется в <tex>t'</tex> в расписании <tex>B'</tex>. Если в <tex>B'</tex> станок простаивает во время <tex>t'</tex>, мы можем переместить работу <tex>k</tex> из <tex>t</tex> в <tex>t'</tex>. Иначе работа <tex>r > k</tex> находится в расписании в промежутке <tex>t'</tex>, но ее нет в <tex>t</tex>. Мы можем передвинуть <tex>r</tex> в <tex>t</tex> и <tex>k</tex> в <tex>t'</tex> без увеличения целевой функции, потому что <tex>C_k \leqslant C_r</tex>. Продолжая действовать таким образом, мы достигнем оптимального расписания, в котором работы <tex>1 \ldots k</tex> расположены таким же образом, как и в <tex>A</tex>. Мы получили противоречие, так как выбранный <tex>k</tex> оказался не максимальным.
}}

== См. также ==
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
* [[Opij1di|<tex> O \mid p_{i, j} = 1, d_i \mid - </tex>]]
* [[Opij1sumwu|<tex> O \mid p_{i, j} = 1 \mid - \sum w_{i} U_{i}</tex>]]
== Источники информации ==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 171-174 ISBN 978-3-540-69515-8

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

Opij1SumTi

2016-06-08T20:00:32Z

Анна: /* Доказательство корректности */

<tex dpi = "200"> O \mid p_{i,j} = 1 \mid \sum T_{i} </tex>
{{Задача
|definition=
Дано <tex>m</tex> одинаковых станков, которые работают параллельно, и <tex>n</tex> работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания <tex>d_i</tex> {{---}} время, до которого она должна быть выполнена. Необходимо минимизировать суммарную [[Классификация_задач#Критерий оптимизации|медлительность]].
}}
== Описание алгоритма ==
=== Идея ===
Будем полагать, что работы заданы в порядке неубывания их дедлайнов, то есть <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>.
{{Лемма
|statement=
Пусть есть работы <tex>1 \ldots n</tex> с дедлайнами <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Тогда существует оптимальное расписание, в котором времена завершения работ идут в том же порядке, то есть <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex>.
|proof=
Рассмотрим две работы <tex>i</tex> и <tex>j</tex> из какого-либо оптимального расписания такие, что <tex>C_i > C_j</tex> и <tex>d_i < d_j</tex>. Поменяем эти работы в расписании местами, то есть <tex>C'_i = C_j</tex> и <tex>C'_j = C_i</tex>. Если они обе успевали выполниться вовремя, то это свойство сохранится, так как <tex>d_i < d_j</tex>, значит по-прежнему <tex>T_i = 0</tex> и <tex>T_j = 0</tex>, то есть значение целевой функции мы не ухудшили и расписание осталось оптимальным. Если обе работы не успевали выполниться вовремя, то когда мы поменяем их местами ничего не изменится, то есть значение целевой функции останется прежним, так как мы не меняли значения времен окончаний, а только поменяли их местами. Если работа <tex>j</tex> успевала выполниться, а <tex>i</tex> {{---}} нет, то мы снова не ухудшим значение целевой функции. Покажем это. До того, как мы поменяли работы местами, было <tex>T_i + T_j = C_i - d_i</tex>, так как <tex>T_j = 0</tex>. После того, как мы поменяли работы местами, <tex>T_i + T_j = C'_i - d_i + C'_j - d_j = C_j - d_i + C_i - d_j = C_i - d_i + (C_j - d_j)</tex>. Но так как работа <tex>j</tex> успевает выполниться до дедлайна, то <tex>C_j - d_j \leqslant 0</tex>.
}}
Далее будем рассматривать только оптимальное расписание со свойством <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex>.
{{Теорема
|statement=
Всегда существует оптимально расписание такое, что в нем <tex>C_i \leqslant m + i - 1</tex> для любого <tex>i = 1 \ldots n</tex>, где <tex>m</tex> {{---}} количество станков.
|proof=
Рассмотрим оптимальное расписание <tex>S^*</tex>, в котором для любого <tex>i = 1 \ldots k - 1</tex> выполняется <tex>C_i \leqslant m + i - 1</tex>, но <tex>C_k > m + k - 1</tex>, где <tex>k</tex> максимально среди всех возможных. Для начала покажем, что <tex>k</tex> не меньше <tex>2</tex>. Пусть есть оптимальное расписание, у которого <tex>C_1 > m</tex>. Это значит, что есть период времени <tex>t</tex> такой, что первая работа выполняется в момент <tex>t</tex> и не выполняется в <tex>t - 1</tex>. Поменяем эти периоды времени местами. То есть все работы, которые выполнялись в момент <tex>t - 1</tex>, будут выполняться на тех же станках, но в момент <tex>t</tex>, и наоборот. Значение <tex>C_i</tex> для каждой работы <tex>i</tex> не увеличится, так как <tex>C_1</tex> было минимальным из них, а значит ни одна работа не могла быть закончена раньше периода времени <tex>t</tex>. Будем продолжать этот процесс, пока не будет выполнено равенство <tex>C_1 = m</tex>. 
Теперь пусть <tex>C_k = m + k + t</tex>, где <tex>t \geqslant 0</tex>. Будем называть ''итерацией обработки'' работы обработку на одной машине. Разобьем все работы на три множества:
* множество <tex>A</tex> будет содержать все итерации обработки работ <tex>i = 1 \ldots k - 1</tex>
* множество <tex>B</tex> {{---}} все итерации, запланированные в расписании <tex>S^*</tex> строго после момента времени <tex>k + m + t</tex>
* множество <tex>C</tex> {{---}} итерации обработки работ <tex>i = k + 1 \ldots n</tex>, которые в <tex>S^*</tex> запланированы на время <tex>k + m + t</tex> и раньше
Таким образом, мы имеем три непересекающихся множества, которые вместе с работой <tex>k</tex> покрывают все итерации всех работ. 
Построим новое расписание <tex>S^*</tex>. Для начала расставим все работы из множества <tex>A \cup B</tex> так же, как они были запланированы в расписании <tex>S^*</tex>. Так как <tex>C_i \leqslant m + i - 1</tex> для <tex>i = 1 \ldots k - 1</tex>, ни одна итерация обработки в множестве <tex>B</tex> не поставлена раньше момента времени <tex>k + m + t</tex> и к моменту времени <tex>C_k = m + k + t</tex> выполнено <tex>k</tex> работ, то это значит, что между моментами времени <tex>1</tex> и <tex>k + m - 1</tex> на каждой машине есть <tex>m</tex> различных простоев, то есть моментов, когда на ней ничего не обрабатывается. Значит, мы всегда сможем поставить на эти простои итерации обработки работы <tex>k</tex>, даже если эти простои пересекаются. Таким образом, <tex>C_k \leqslant m + k - 1</tex>. 
Теперь назначим машины для операций из множества <tex>C</tex>. До момента времени <tex>k + m + t</tex> сейчас распланировано ровно <tex>k</tex> работ, так как по определению работы из множества <tex>B</tex> запланированы на время строго большее <tex>k + m + t</tex>. Значит, между моментами времени <tex>1</tex> и <tex>k + m + t</tex> есть <tex>k + m + t - k = m + t</tex> различных простоев на каждой машине. Исходя из определения множества <tex>C</tex> и того, что к моменту <tex>k + m + t</tex> распланировано <tex>km</tex> итераций обработок, приходим к неравенству <tex>|C| \leqslant (k + m + t)m - km = (m + t)m</tex>. Значит, мы можем распланировать итерации из множества <tex>C</tex> не позднее момента <tex>k + m + t</tex>. Таим образом, мы снова построили расписание для задачи open shop, которое так же является оптимальным, так как для множеств <tex>A</tex> и <tex>B</tex> все осталось как в оптимальном расписании <tex>S^*</tex>, работу <tex>k</tex> мы научились выполнять быстрее, а для множества <tex>C</tex> ответ был не ухудшен. Любая работа <tex>j</tex>, итерации обработки которой принадлежат множеству <tex>C</tex>, имела время окончания <tex>C_j \geqslant m + k + t</tex>. Однако это противоречит тому, что мы выбрали максимальное <tex>k</tex>.
}}
Отсортируем работы в порядке неуменьшения дедлайнов. Для текущей работы <tex>i</tex> вычислим ''лимит'' <tex>T_i</tex> {{---}} время, до которого закончится обработка данной работы, то есть <tex>1 \leqslant t_1 < t_2 < \ldots < t_m \leqslant T_i </tex>, где <tex>t_j</tex>, <tex>j = 1 \ldots m</tex> {{---}} периоды обработки работы <tex>i</tex>.
Будем выбирать эти периоды среди моментов времени, в которые выполняется наименьшее число работ.

=== Псевдокод ===
Определим ''вектор частот'' <tex>h[t]</tex> {{---}} количество работ во временном интервале <tex>t</tex>. Работы отсортированы в порядке <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>.

'''function''' scheduler():
'''int''' <tex>h[m + n - 1]</tex>
'''vector<int>''' <tex>s[n]</tex>
'''fill'''(<tex>h,\ 0</tex>)
'''fill'''(<tex>s,\ \varnothing</tex>)
'''for''' <tex>i = 1</tex> '''to''' <tex>n</tex>
'''if''' <tex>d_i < m + i - 1</tex>
вычислим <tex>z</tex> {{---}} количество временных интервалов <tex>t = 1 \ldots d_i</tex>, таких, что <tex>h[t] < m</tex>
'''if''' <tex>z \geqslant m</tex>
<tex>T_i = d_i</tex>
'''else'''
<tex>T_i = d_i + m - z</tex>
'''else'''
<tex>T_i = m + i - 1</tex>
вычислим <tex>m</tex> периодов <tex>1 \leqslant t_1 < t_2 < \ldots < t_m \leqslant T_i </tex> с минимальными значениями <tex>h[t_j]</tex>
'''for''' <tex>j = 1</tex> '''to''' <tex>m</tex>
<tex>s[i] = s[i] \cup \{t_j - 1\}</tex> // ставим работу <tex>i</tex> на время <tex>[t_j - 1, t_j]</tex>
<tex>h[t_j] = h[t_j] + 1</tex>
'''return''' <tex>s</tex>

=== Асимптотика ===
Алгоритм может работать за <tex>O(nm)</tex>. Чтобы получить алгоритм с такой сложностью, мы распределяем работы так, чтобы после каждого шага <tex>i</tex> сохранялся инвариант <tex>l_1 \geqslant l_2 \geqslant \ldots \geqslant l_m </tex> при <tex>l_1 \geqslant T_i</tex>, где <tex>l_j</tex> это такое число, что на станке <tex>M_j</tex> все временные промежутки <tex>1 \ldots l_j</tex> заняты.
На первом шаге алгоритма <tex> l_1 = l_2 = \ldots = l_m = 0 </tex>. Предположим, что инвариант сохранился после шага <tex> i - 1 </tex>. Тогда <tex> T_{i-1} \leqslant T_i </tex> и, для сохранения инварианта, распределим работу в следующем порядке: 
<center><tex>l_1 + 1 \ldots T_i</tex> на станке <tex> M_1 </tex>, 
<tex>l_2 + 1 \ldots l_1</tex> на станке <tex> M_2 </tex>, 
<tex> \vdots </tex> 
<tex>l_m + 1 \ldots l_{m-1}</tex> на станке <tex> M_1 </tex>.
</center>
Таким образом, мы получаем распределение одной работы по <tex>m</tex> станкам для <tex>n</tex> работ. Итоговая асимптотика {{---}} <tex>O(nm)</tex>.

== Доказательство корректности ==
{{Теорема
|statement=Алгоритм строит оптимальное расписание для задачи <tex> O \mid p_{i,j} = 1 \mid \sum T_{i} </tex>
|proof= Воспользуемся для доказательства леммой и теоремой из предыдущего пункта. Из них мы знаем, что существует оптимальное расписание, для которого выполняются свойства <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex> и <tex>C_i \leqslant m + i - 1</tex> для любого <tex>i = 1 \ldots n</tex>, где <tex>m</tex> {{---}} число станков. Пусть <tex>B</tex> {{---}} оптимальное расписание, которое удовлетворяет свойству, по которому работы <tex>1 \ldots k - 1 </tex> поставлены в те же временные промежутки, в которых они оказались следуя нашему расписанию <tex>A</tex>. Более того, предположим, что <tex>B</tex> было выбрано так, что <tex>k</tex> максимально.
Пусть <tex>C_k > T_k</tex>. С того момента, как работа <tex>k</tex> поставлена в расписании <tex>A</tex> перед <tex>T_k</tex>, определим временной промежуток <tex>t \leqslant T_k </tex> в месте, где работа <tex>k</tex> не выполняется в <tex>B</tex>. Тогда в самом расписании <tex>B</tex> этот промежуток либо так же пустой, либо он занят работой <tex>r > k</tex>.
* Если он пустой, мы перемещаем операцию <tex>k</tex>, которая была распределена в промежуток <tex>C_k</tex>, в этот промежуток.
* Если работа <tex>r</tex> стоит во время <tex>t</tex>, но не во время <tex>C_k</tex>, то мы меняем между собой операции работ <tex>k</tex> и <tex>r</tex>.
* Если работа <tex>r</tex> поставлена во время <tex>t</tex> и <tex>C_k</tex>, то либо тут есть пустое место в <tex>C_r + 1</tex>, либо там должна быть работа, назовем ее <tex>v</tex>, которая поставлена на время <tex>C_r + 1</tex>, но не поставлена в <tex>C_k</tex>.
Работа <tex>v</tex> точно там есть, потому что <tex>r</tex> и <tex>k</tex> поставлены на время <tex>C_k</tex>, но не поставлены на время <tex>C_r + 1</tex>. Если свободный промежуток есть, тогда переставим работу <tex>r</tex> со времени <tex>t</tex> на время <tex>C_r + 1</tex> и работу <tex>k</tex> со времени <tex>C_k</tex> на <tex>t</tex>. Иначе мы можем переместить работу <tex>r</tex> с времени <tex>t</tex> на время <tex>C_r + 1</tex>, <tex>k</tex> c <tex>C_k</tex> на <tex>t</tex>, и <tex>v</tex> с <tex>C_r + 1</tex> на <tex>C_k</tex>. Тогда <tex>C_k</tex> должно уменьшиться как минимум на один, а <tex>C_r</tex> увеличится не больше, чем на один.
Если мы продолжим так действовать, мы получим оптимальное расписание <tex>B'</tex> с <tex>C_k \leqslant T_k</tex>, в котором работы <tex>1 \ldots k-1</tex> расположены так же, как в расписании <tex>A</tex>.
Пусть <tex>h</tex> {{---}} вектор частот для части расписания из работ от <tex>1</tex> до <tex>k - 1</tex>. Предположим, что <tex>h(t') < h(t)</tex> и работа <tex>k</tex> выполняется во временной промежуток <tex>t</tex>, но не выполняется в <tex>t'</tex> в расписании <tex>B'</tex>. Если в <tex>B'</tex> станок простаивает во время <tex>t'</tex>, мы можем переместить работу <tex>k</tex> из <tex>t</tex> в <tex>t'</tex>. Иначе работа <tex>r > k</tex> находится в расписании в промежутке <tex>t'</tex>, но ее нет в <tex>t</tex>. Мы можем передвинуть <tex>r</tex> в <tex>t</tex> и <tex>k</tex> в <tex>t'</tex> без увеличения целевой функции, потому что <tex>C_k \leqslant C_r</tex>. Продолжая действовать таким образом, мы достигнем оптимального расписания, в котором работы <tex>1 \ldots k</tex> расположены таким же образом, как и в <tex>A</tex>. Мы получили противоречие, так как выбранный <tex>k</tex> оказался не максимальным.
}}

== См. также ==
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
* [[Opij1di|<tex> O \mid p_{i, j} = 1, d_i \mid - </tex>]]
* [[Opij1sumwu|<tex> O \mid p_{i, j} = 1 \mid - \sum w_{i} U_{i}</tex>]]
== Источники информации ==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 171-174 ISBN 978-3-540-69515-8

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

Opij1SumTi

2016-06-08T19:48:17Z

Анна: /* Доказательство корректности */

<tex dpi = "200"> O \mid p_{i,j} = 1 \mid \sum T_{i} </tex>
{{Задача
|definition=
Дано <tex>m</tex> одинаковых станков, которые работают параллельно, и <tex>n</tex> работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания <tex>d_i</tex> {{---}} время, до которого она должна быть выполнена. Необходимо минимизировать суммарную [[Классификация_задач#Критерий оптимизации|медлительность]].
}}
== Описание алгоритма ==
=== Идея ===
Будем полагать, что работы заданы в порядке неубывания их дедлайнов, то есть <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>.
{{Лемма
|statement=
Пусть есть работы <tex>1 \ldots n</tex> с дедлайнами <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Тогда существует оптимальное расписание, в котором времена завершения работ идут в том же порядке, то есть <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex>.
|proof=
Рассмотрим две работы <tex>i</tex> и <tex>j</tex> из какого-либо оптимального расписания такие, что <tex>C_i > C_j</tex> и <tex>d_i < d_j</tex>. Поменяем эти работы в расписании местами, то есть <tex>C'_i = C_j</tex> и <tex>C'_j = C_i</tex>. Если они обе успевали выполниться вовремя, то это свойство сохранится, так как <tex>d_i < d_j</tex>, значит по-прежнему <tex>T_i = 0</tex> и <tex>T_j = 0</tex>, то есть значение целевой функции мы не ухудшили и расписание осталось оптимальным. Если обе работы не успевали выполниться вовремя, то когда мы поменяем их местами ничего не изменится, то есть значение целевой функции останется прежним, так как мы не меняли значения времен окончаний, а только поменяли их местами. Если работа <tex>j</tex> успевала выполниться, а <tex>i</tex> {{---}} нет, то мы снова не ухудшим значение целевой функции. Покажем это. До того, как мы поменяли работы местами, было <tex>T_i + T_j = C_i - d_i</tex>, так как <tex>T_j = 0</tex>. После того, как мы поменяли работы местами, <tex>T_i + T_j = C'_i - d_i + C'_j - d_j = C_j - d_i + C_i - d_j = C_i - d_i + (C_j - d_j)</tex>. Но так как работа <tex>j</tex> успевает выполниться до дедлайна, то <tex>C_j - d_j \leqslant 0</tex>.
}}
Далее будем рассматривать только оптимальное расписание со свойством <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex>.
{{Теорема
|statement=
Всегда существует оптимально расписание такое, что в нем <tex>C_i \leqslant m + i - 1</tex> для любого <tex>i = 1 \ldots n</tex>, где <tex>m</tex> {{---}} количество станков.
|proof=
Рассмотрим оптимальное расписание <tex>S^*</tex>, в котором для любого <tex>i = 1 \ldots k - 1</tex> выполняется <tex>C_i \leqslant m + i - 1</tex>, но <tex>C_k > m + k - 1</tex>, где <tex>k</tex> максимально среди всех возможных. Для начала покажем, что <tex>k</tex> не меньше <tex>2</tex>. Пусть есть оптимальное расписание, у которого <tex>C_1 > m</tex>. Это значит, что есть период времени <tex>t</tex> такой, что первая работа выполняется в момент <tex>t</tex> и не выполняется в <tex>t - 1</tex>. Поменяем эти периоды времени местами. То есть все работы, которые выполнялись в момент <tex>t - 1</tex>, будут выполняться на тех же станках, но в момент <tex>t</tex>, и наоборот. Значение <tex>C_i</tex> для каждой работы <tex>i</tex> не увеличится, так как <tex>C_1</tex> было минимальным из них, а значит ни одна работа не могла быть закончена раньше периода времени <tex>t</tex>. Будем продолжать этот процесс, пока не будет выполнено равенство <tex>C_1 = m</tex>. 
Теперь пусть <tex>C_k = m + k + t</tex>, где <tex>t \geqslant 0</tex>. Будем называть ''итерацией обработки'' работы обработку на одной машине. Разобьем все работы на три множества:
* множество <tex>A</tex> будет содержать все итерации обработки работ <tex>i = 1 \ldots k - 1</tex>
* множество <tex>B</tex> {{---}} все итерации, запланированные в расписании <tex>S^*</tex> строго после момента времени <tex>k + m + t</tex>
* множество <tex>C</tex> {{---}} итерации обработки работ <tex>i = k + 1 \ldots n</tex>, которые в <tex>S^*</tex> запланированы на время <tex>k + m + t</tex> и раньше
Таким образом, мы имеем три непересекающихся множества, которые вместе с работой <tex>k</tex> покрывают все итерации всех работ. 
Построим новое расписание <tex>S^*</tex>. Для начала расставим все работы из множества <tex>A \cup B</tex> так же, как они были запланированы в расписании <tex>S^*</tex>. Так как <tex>C_i \leqslant m + i - 1</tex> для <tex>i = 1 \ldots k - 1</tex>, ни одна итерация обработки в множестве <tex>B</tex> не поставлена раньше момента времени <tex>k + m + t</tex> и к моменту времени <tex>C_k = m + k + t</tex> выполнено <tex>k</tex> работ, то это значит, что между моментами времени <tex>1</tex> и <tex>k + m - 1</tex> на каждой машине есть <tex>m</tex> различных простоев, то есть моментов, когда на ней ничего не обрабатывается. Значит, мы всегда сможем поставить на эти простои итерации обработки работы <tex>k</tex>, даже если эти простои пересекаются. Таким образом, <tex>C_k \leqslant m + k - 1</tex>. 
Теперь назначим машины для операций из множества <tex>C</tex>. До момента времени <tex>k + m + t</tex> сейчас распланировано ровно <tex>k</tex> работ, так как по определению работы из множества <tex>B</tex> запланированы на время строго большее <tex>k + m + t</tex>. Значит, между моментами времени <tex>1</tex> и <tex>k + m + t</tex> есть <tex>k + m + t - k = m + t</tex> различных простоев на каждой машине. Исходя из определения множества <tex>C</tex> и того, что к моменту <tex>k + m + t</tex> распланировано <tex>km</tex> итераций обработок, приходим к неравенству <tex>|C| \leqslant (k + m + t)m - km = (m + t)m</tex>. Значит, мы можем распланировать итерации из множества <tex>C</tex> не позднее момента <tex>k + m + t</tex>. Таим образом, мы снова построили расписание для задачи open shop, которое так же является оптимальным, так как для множеств <tex>A</tex> и <tex>B</tex> все осталось как в оптимальном расписании <tex>S^*</tex>, работу <tex>k</tex> мы научились выполнять быстрее, а для множества <tex>C</tex> ответ был не ухудшен. Любая работа <tex>j</tex>, итерации обработки которой принадлежат множеству <tex>C</tex>, имела время окончания <tex>C_j \geqslant m + k + t</tex>. Однако это противоречит тому, что мы выбрали максимальное <tex>k</tex>.
}}
Отсортируем работы в порядке неуменьшения дедлайнов. Для текущей работы <tex>i</tex> вычислим ''лимит'' <tex>T_i</tex> {{---}} время, до которого закончится обработка данной работы, то есть <tex>1 \leqslant t_1 < t_2 < \ldots < t_m \leqslant T_i </tex>, где <tex>t_j</tex>, <tex>j = 1 \ldots m</tex> {{---}} периоды обработки работы <tex>i</tex>.
Будем выбирать эти периоды среди моментов времени, в которые выполняется наименьшее число работ.

=== Псевдокод ===
Определим ''вектор частот'' <tex>h[t]</tex> {{---}} количество работ во временном интервале <tex>t</tex>. Работы отсортированы в порядке <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>.

'''function''' scheduler():
'''int''' <tex>h[m + n - 1]</tex>
'''vector<int>''' <tex>s[n]</tex>
'''fill'''(<tex>h,\ 0</tex>)
'''fill'''(<tex>s,\ \varnothing</tex>)
'''for''' <tex>i = 1</tex> '''to''' <tex>n</tex>
'''if''' <tex>d_i < m + i - 1</tex>
вычислим <tex>z</tex> {{---}} количество временных интервалов <tex>t = 1 \ldots d_i</tex>, таких, что <tex>h[t] < m</tex>
'''if''' <tex>z \geqslant m</tex>
<tex>T_i = d_i</tex>
'''else'''
<tex>T_i = d_i + m - z</tex>
'''else'''
<tex>T_i = m + i - 1</tex>
вычислим <tex>m</tex> периодов <tex>1 \leqslant t_1 < t_2 < \ldots < t_m \leqslant T_i </tex> с минимальными значениями <tex>h[t_j]</tex>
'''for''' <tex>j = 1</tex> '''to''' <tex>m</tex>
<tex>s[i] = s[i] \cup \{t_j - 1\}</tex> // ставим работу <tex>i</tex> на время <tex>[t_j - 1, t_j]</tex>
<tex>h[t_j] = h[t_j] + 1</tex>
'''return''' <tex>s</tex>

=== Асимптотика ===
Алгоритм может работать за <tex>O(nm)</tex>. Чтобы получить алгоритм с такой сложностью, мы распределяем работы так, чтобы после каждого шага <tex>i</tex> сохранялся инвариант <tex>l_1 \geqslant l_2 \geqslant \ldots \geqslant l_m </tex> при <tex>l_1 \geqslant T_i</tex>, такой, что на станке <tex>M_j</tex> все промежутки <tex>1 \ldots l_j</tex> заняты.
На первом шаге алгоритма <tex> l_1 = l_2 = \ldots = l_m = 0 </tex>. Предположим, что инвариант сохранился после шага <tex> i - 1 </tex>. Тогда <tex> T_{i-1} \leqslant T_i </tex> и, для сохранения инварианта, распределим работу в следующем порядке: 
<center><tex>l_1 + 1 \ldots T_i</tex> на станке <tex> M_1 </tex>, 
<tex>l_2 + 1 \ldots l_1</tex> на станке <tex> M_2 </tex>, 
<tex> \vdots </tex> 
<tex>l_m + 1 \ldots l_{m-1}</tex> на станке <tex> M_1 </tex>.
</center>
Таким образом, мы получаем распределение одной работы по <tex>m</tex> станкам для <tex>n</tex> работ. Итоговая асимптотика {{---}} <tex>O(nm)</tex>.

== Доказательство корректности ==
{{Теорема
|statement=Алгоритм строит оптимальное расписание для задачи <tex> O \mid p_{i,j} = 1 \mid \sum T_{i} </tex>
|proof= Воспользуемся для доказательства леммой и теоремой, которые были доказаны выше. Из них мы знаем, что существует оптимальное расписание, для которого выполняются свойства <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex> и <tex>C_i \leqslant m + i - 1</tex> для любого <tex>i = 1 \ldots n</tex>, где <tex>m</tex> {{---}} число станков. Пусть <tex>B</tex> {{---}} оптимальное расписание, которое удовлетворяет свойству, по которому работы <tex>1 \ldots k - 1 </tex> поставлены в те же временные промежутки, в которых они оказались следуя нашему расписанию <tex>A</tex>. Более того, предположим, что <tex>B</tex> было выбрано так, что <tex>k</tex> максимально.
Пусть <tex>C_k > T_k</tex>. С того момента, как работа <tex>k</tex> поставлена в расписании <tex>A</tex> перед <tex>T_k</tex>, определим временной промежуток <tex>t \leqslant T_k </tex> в месте, где работа <tex>k</tex> не выполняется в <tex>B</tex>. Тогда в самом расписании <tex>B</tex> этот промежуток либо так же пустой, либо он занят работой <tex>r > k</tex>.
* Если он пустой, мы перемещаем операцию <tex>k</tex>, которая была распределена в промежуток <tex>C_k</tex>, в этот промежуток.
* Если работа <tex>r</tex> стоит во время <tex>t</tex>, но не во время <tex>C_k</tex>, то мы меняем между собой операции работ <tex>k</tex> и <tex>r</tex>.
* Если работа <tex>r</tex> поставлена во время <tex>t</tex> и <tex>C_k</tex>, то либо тут есть пустое место в <tex>C_r + 1</tex>, либо там должна быть работа, назовем ее <tex>v</tex>, которая поставлена на время <tex>C_r + 1</tex>, но не поставлена в <tex>C_k</tex>.
Работа <tex>v</tex> точно там есть, потому что <tex>r</tex> и <tex>k</tex> поставлены на время <tex>C_k</tex>, но не поставлены на время <tex>C_r + 1</tex>. Если свободный промежуток есть, тогда переставим работу <tex>r</tex> со времени <tex>t</tex> на время <tex>C_r + 1</tex> и работу <tex>k</tex> со времени <tex>C_k</tex> на <tex>t</tex>. Иначе мы можем переместить работу <tex>r</tex> с времени <tex>t</tex> на время <tex>C_r + 1</tex>, <tex>k</tex> c <tex>C_k</tex> на <tex>t</tex>, и <tex>v</tex> с <tex>C_r + 1</tex> на <tex>C_k</tex>. Тогда <tex>C_k</tex> должно уменьшиться как минимум на один, а <tex>C_r</tex> увеличится не больше, чем на один.
Если мы продолжим так действовать, мы получим оптимальное расписание <tex>B'</tex> с <tex>C_k \leqslant T_k</tex>, в котором работы <tex>1 \ldots k-1</tex> расположены так же, как в расписании <tex>A</tex>.
Пусть <tex>h</tex> {{---}} вектор частот для части расписания из работ от <tex>1</tex> до <tex>k - 1</tex>. Предположим, что <tex>h(t') < h(t)</tex> и работа <tex>k</tex> выполняется во временной промежуток <tex>t</tex>, но не выполняется в <tex>t'</tex> в расписании <tex>B'</tex>. Если в <tex>B'</tex> станок простаивает во время <tex>t'</tex>, мы можем переместить работу <tex>k</tex> из <tex>t</tex> в <tex>t'</tex>. Иначе работа <tex>r > k</tex> находится в расписании в промежутке <tex>t'</tex>, но ее нет в <tex>t</tex>. Мы можем передвинуть <tex>r</tex> в <tex>t</tex> и <tex>k</tex> в <tex>t'</tex> без увеличения целевой функции, потому что <tex>C_k \leqslant C_r</tex>. Продолжая действовать таким образом, мы достигнем оптимального расписания, в котором работы <tex>1 \ldots k</tex> расположены таким же образом, как и в <tex>A</tex>. Мы получили противоречие, так как выбранный <tex>k</tex> оказался не максимальным.
}}

== См. также ==
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
* [[Opij1di|<tex> O \mid p_{i, j} = 1, d_i \mid - </tex>]]
* [[Opij1sumwu|<tex> O \mid p_{i, j} = 1 \mid - \sum w_{i} U_{i}</tex>]]
== Источники информации ==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 171-174 ISBN 978-3-540-69515-8

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

Opij1SumTi

2016-06-08T19:43:37Z

Анна: /* Доказательство корректности */

<tex dpi = "200"> O \mid p_{i,j} = 1 \mid \sum T_{i} </tex>
{{Задача
|definition=
Дано <tex>m</tex> одинаковых станков, которые работают параллельно, и <tex>n</tex> работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания <tex>d_i</tex> {{---}} время, до которого она должна быть выполнена. Необходимо минимизировать суммарную [[Классификация_задач#Критерий оптимизации|медлительность]].
}}
== Описание алгоритма ==
=== Идея ===
Будем полагать, что работы заданы в порядке неубывания их дедлайнов, то есть <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>.
{{Лемма
|statement=
Пусть есть работы <tex>1 \ldots n</tex> с дедлайнами <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Тогда существует оптимальное расписание, в котором времена завершения работ идут в том же порядке, то есть <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex>.
|proof=
Рассмотрим две работы <tex>i</tex> и <tex>j</tex> из какого-либо оптимального расписания такие, что <tex>C_i > C_j</tex> и <tex>d_i < d_j</tex>. Поменяем эти работы в расписании местами, то есть <tex>C'_i = C_j</tex> и <tex>C'_j = C_i</tex>. Если они обе успевали выполниться вовремя, то это свойство сохранится, так как <tex>d_i < d_j</tex>, значит по-прежнему <tex>T_i = 0</tex> и <tex>T_j = 0</tex>, то есть значение целевой функции мы не ухудшили и расписание осталось оптимальным. Если обе работы не успевали выполниться вовремя, то когда мы поменяем их местами ничего не изменится, то есть значение целевой функции останется прежним, так как мы не меняли значения времен окончаний, а только поменяли их местами. Если работа <tex>j</tex> успевала выполниться, а <tex>i</tex> {{---}} нет, то мы снова не ухудшим значение целевой функции. Покажем это. До того, как мы поменяли работы местами, было <tex>T_i + T_j = C_i - d_i</tex>, так как <tex>T_j = 0</tex>. После того, как мы поменяли работы местами, <tex>T_i + T_j = C'_i - d_i + C'_j - d_j = C_j - d_i + C_i - d_j = C_i - d_i + (C_j - d_j)</tex>. Но так как работа <tex>j</tex> успевает выполниться до дедлайна, то <tex>C_j - d_j \leqslant 0</tex>.
}}
Далее будем рассматривать только оптимальное расписание со свойством <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex>.
{{Теорема
|statement=
Всегда существует оптимально расписание такое, что в нем <tex>C_i \leqslant m + i - 1</tex> для любого <tex>i = 1 \ldots n</tex>, где <tex>m</tex> {{---}} количество станков.
|proof=
Рассмотрим оптимальное расписание <tex>S^*</tex>, в котором для любого <tex>i = 1 \ldots k - 1</tex> выполняется <tex>C_i \leqslant m + i - 1</tex>, но <tex>C_k > m + k - 1</tex>, где <tex>k</tex> максимально среди всех возможных. Для начала покажем, что <tex>k</tex> не меньше <tex>2</tex>. Пусть есть оптимальное расписание, у которого <tex>C_1 > m</tex>. Это значит, что есть период времени <tex>t</tex> такой, что первая работа выполняется в момент <tex>t</tex> и не выполняется в <tex>t - 1</tex>. Поменяем эти периоды времени местами. То есть все работы, которые выполнялись в момент <tex>t - 1</tex>, будут выполняться на тех же станках, но в момент <tex>t</tex>, и наоборот. Значение <tex>C_i</tex> для каждой работы <tex>i</tex> не увеличится, так как <tex>C_1</tex> было минимальным из них, а значит ни одна работа не могла быть закончена раньше периода времени <tex>t</tex>. Будем продолжать этот процесс, пока не будет выполнено равенство <tex>C_1 = m</tex>. 
Теперь пусть <tex>C_k = m + k + t</tex>, где <tex>t \geqslant 0</tex>. Будем называть ''итерацией обработки'' работы обработку на одной машине. Разобьем все работы на три множества:
* множество <tex>A</tex> будет содержать все итерации обработки работ <tex>i = 1 \ldots k - 1</tex>
* множество <tex>B</tex> {{---}} все итерации, запланированные в расписании <tex>S^*</tex> строго после момента времени <tex>k + m + t</tex>
* множество <tex>C</tex> {{---}} итерации обработки работ <tex>i = k + 1 \ldots n</tex>, которые в <tex>S^*</tex> запланированы на время <tex>k + m + t</tex> и раньше
Таким образом, мы имеем три непересекающихся множества, которые вместе с работой <tex>k</tex> покрывают все итерации всех работ. 
Построим новое расписание <tex>S^*</tex>. Для начала расставим все работы из множества <tex>A \cup B</tex> так же, как они были запланированы в расписании <tex>S^*</tex>. Так как <tex>C_i \leqslant m + i - 1</tex> для <tex>i = 1 \ldots k - 1</tex>, ни одна итерация обработки в множестве <tex>B</tex> не поставлена раньше момента времени <tex>k + m + t</tex> и к моменту времени <tex>C_k = m + k + t</tex> выполнено <tex>k</tex> работ, то это значит, что между моментами времени <tex>1</tex> и <tex>k + m - 1</tex> на каждой машине есть <tex>m</tex> различных простоев, то есть моментов, когда на ней ничего не обрабатывается. Значит, мы всегда сможем поставить на эти простои итерации обработки работы <tex>k</tex>, даже если эти простои пересекаются. Таким образом, <tex>C_k \leqslant m + k - 1</tex>. 
Теперь назначим машины для операций из множества <tex>C</tex>. До момента времени <tex>k + m + t</tex> сейчас распланировано ровно <tex>k</tex> работ, так как по определению работы из множества <tex>B</tex> запланированы на время строго большее <tex>k + m + t</tex>. Значит, между моментами времени <tex>1</tex> и <tex>k + m + t</tex> есть <tex>k + m + t - k = m + t</tex> различных простоев на каждой машине. Исходя из определения множества <tex>C</tex> и того, что к моменту <tex>k + m + t</tex> распланировано <tex>km</tex> итераций обработок, приходим к неравенству <tex>|C| \leqslant (k + m + t)m - km = (m + t)m</tex>. Значит, мы можем распланировать итерации из множества <tex>C</tex> не позднее момента <tex>k + m + t</tex>. Таим образом, мы снова построили расписание для задачи open shop, которое так же является оптимальным, так как для множеств <tex>A</tex> и <tex>B</tex> все осталось как в оптимальном расписании <tex>S^*</tex>, работу <tex>k</tex> мы научились выполнять быстрее, а для множества <tex>C</tex> ответ был не ухудшен. Любая работа <tex>j</tex>, итерации обработки которой принадлежат множеству <tex>C</tex>, имела время окончания <tex>C_j \geqslant m + k + t</tex>. Однако это противоречит тому, что мы выбрали максимальное <tex>k</tex>.
}}
Отсортируем работы в порядке неуменьшения дедлайнов. Для текущей работы <tex>i</tex> вычислим ''лимит'' <tex>T_i</tex> {{---}} время, до которого закончится обработка данной работы, то есть <tex>1 \leqslant t_1 < t_2 < \ldots < t_m \leqslant T_i </tex>, где <tex>t_j</tex>, <tex>j = 1 \ldots m</tex> {{---}} периоды обработки работы <tex>i</tex>.
Будем выбирать эти периоды среди моментов времени, в которые выполняется наименьшее число работ.

=== Псевдокод ===
Определим ''вектор частот'' <tex>h[t]</tex> {{---}} количество работ во временном интервале <tex>t</tex>. Работы отсортированы в порядке <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>.

'''function''' scheduler():
'''int''' <tex>h[m + n - 1]</tex>
'''vector<int>''' <tex>s[n]</tex>
'''fill'''(<tex>h,\ 0</tex>)
'''fill'''(<tex>s,\ \varnothing</tex>)
'''for''' <tex>i = 1</tex> '''to''' <tex>n</tex>
'''if''' <tex>d_i < m + i - 1</tex>
вычислим <tex>z</tex> {{---}} количество временных интервалов <tex>t = 1 \ldots d_i</tex>, таких, что <tex>h[t] < m</tex>
'''if''' <tex>z \geqslant m</tex>
<tex>T_i = d_i</tex>
'''else'''
<tex>T_i = d_i + m - z</tex>
'''else'''
<tex>T_i = m + i - 1</tex>
вычислим <tex>m</tex> периодов <tex>1 \leqslant t_1 < t_2 < \ldots < t_m \leqslant T_i </tex> с минимальными значениями <tex>h[t_j]</tex>
'''for''' <tex>j = 1</tex> '''to''' <tex>m</tex>
<tex>s[i] = s[i] \cup \{t_j - 1\}</tex> // ставим работу <tex>i</tex> на время <tex>[t_j - 1, t_j]</tex>
<tex>h[t_j] = h[t_j] + 1</tex>
'''return''' <tex>s</tex>

=== Асимптотика ===
Алгоритм может работать за <tex>O(nm)</tex>. Чтобы получить алгоритм с такой сложностью, мы распределяем работы так, чтобы после каждого шага <tex>i</tex> сохранялся инвариант <tex>l_1 \geqslant l_2 \geqslant \ldots \geqslant l_m </tex> при <tex>l_1 \geqslant T_i</tex>, такой, что на станке <tex>M_j</tex> все промежутки <tex>1 \ldots l_j</tex> заняты.
На первом шаге алгоритма <tex> l_1 = l_2 = \ldots = l_m = 0 </tex>. Предположим, что инвариант сохранился после шага <tex> i - 1 </tex>. Тогда <tex> T_{i-1} \leqslant T_i </tex> и, для сохранения инварианта, распределим работу в следующем порядке: 
<center><tex>l_1 + 1 \ldots T_i</tex> на станке <tex> M_1 </tex>, 
<tex>l_2 + 1 \ldots l_1</tex> на станке <tex> M_2 </tex>, 
<tex> \vdots </tex> 
<tex>l_m + 1 \ldots l_{m-1}</tex> на станке <tex> M_1 </tex>.
</center>
Таким образом, мы получаем распределение одной работы по <tex>m</tex> станкам для <tex>n</tex> работ. Итоговая асимптотика {{---}} <tex>O(nm)</tex>.

== Доказательство корректности ==
{{Теорема
|statement=Алгоритм строит оптимальное расписание для задачи <tex> O \mid p_{i,j} = 1 \mid \sum T_{i} </tex>
|proof= Воспользуемся для доказательства леммой и теоремой, которые были доказаны выше. Из них мы знаем, что существует оптимальное расписание, для которого выполняются свойства <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex> и <tex>C_i \leqslant m + i - 1</tex> для любого <tex>i = 1 \ldots n</tex>, где <tex>m</tex> {{---}} число станков. Пусть <tex>B</tex> {{---}} оптимальное расписание, которое удовлетворяет свойству, по которому работы <tex>1 \ldots k - 1 </tex> поставлены в те же временные промежутки, в которых они оказались следуя нашему расписанию <tex>A</tex>. Более того, предположим, что <tex>B</tex> было выбрано так, что <tex>k</tex> максимально.
Пусть <tex>C_k > T_k</tex>. С того момента, как работа <tex>k</tex> поставлена в расписании <tex>A</tex> перед <tex>T_k</tex>, определим временной промежуток <tex>t \leqslant T_k </tex> в месте, где работа <tex>k</tex> не выполняется в <tex>B</tex>. Тогда в самом расписании <tex>B</tex> этот промежуток либо так же пустой, либо он занят работой <tex>r > k</tex>.
* Если он пустой, мы перемещаем операцию <tex>k</tex>, которая была распределена в промежуток <tex>C_k</tex>, в этот промежуток.
* Если работа <tex>r</tex> стоит во время <tex>t</tex>, но не во время <tex>C_k</tex>, то мы меняем между собой операции работ <tex>k</tex> и <tex>r</tex>.
* Если работа <tex>r</tex> поставлена во время <tex>t</tex> и <tex>C_k</tex>, то либо тут есть пустое место в <tex>C_r + 1</tex>, либо там должна быть работа, назовем ее <tex>v</tex>, которая поставлена на время <tex>C_r + 1</tex>, но не поставлена в <tex>C_k</tex>.
Работа <tex>v</tex> точно там есть, потому что <tex>r</tex> и <tex>k</tex> поставлены на время <tex>C_k</tex>, но не поставлены на время <tex>C_r + 1</tex>. Если свободный промежуток есть, тогда переставим работу <tex>r</tex> со времени <tex>t</tex> на время <tex>C_r + 1</tex> и работу <tex>k</tex> со времени <tex>C_k</tex> на <tex>t</tex>. Иначе мы можем переместить работу <tex>r</tex> с времени <tex>t</tex> на время <tex>C_r + 1</tex>, <tex>k</tex> c <tex>C_k</tex> на <tex>t</tex>, и <tex>v</tex> с <tex>C_r + 1</tex> на <tex>C_k</tex>. Тогда <tex>C_k</tex> должно уменьшиться как минимум на один, а <tex>C_r</tex> увеличится не больше чем на один.
Если мы продолжим так действовать, мы получим оптимальное расписание <tex>B'</tex> с <tex>C_k \leqslant T_k</tex>, в котором работы <tex>1 \ldots k-1</tex> расположены так же, как в расписании <tex>A</tex>.
Пусть <tex>h</tex> {{---}} вектор частот для части расписания из работ от <tex>1</tex> до <tex>k - 1</tex>. Предположим, что <tex>h(t') < h(t)</tex> и работа <tex>k</tex> выполняется во временной промежуток <tex>t</tex>, но не выполняется в <tex>t'</tex> в расписании <tex>B'</tex>. Если в <tex>B'</tex> станок простаивает во время <tex>t'</tex>, мы можем переместить работу <tex>k</tex> из <tex>t</tex> в <tex>t'</tex>. Иначе работа <tex>r > k</tex> находится в расписании в промежутке <tex>t'</tex>, но ее нет в <tex>t</tex>. Мы можем передвинуть <tex>r</tex> в <tex>t</tex> и <tex>k</tex> в <tex>t'</tex> без увеличения целевой функции, потому что <tex>C_k \leqslant C_r</tex>. Продолжая действовать таким образом, мы достигнем оптимального расписания, в котором работы <tex>1 \ldots k</tex> расположены таким же образом, как и в <tex>A</tex>. Мы получили противоречие, так как выбранный <tex>k</tex> оказался не максимальным.
}}

== См. также ==
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
* [[Opij1di|<tex> O \mid p_{i, j} = 1, d_i \mid - </tex>]]
* [[Opij1sumwu|<tex> O \mid p_{i, j} = 1 \mid - \sum w_{i} U_{i}</tex>]]
== Источники информации ==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 171-174 ISBN 978-3-540-69515-8

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

Opij1SumTi

2016-06-08T19:30:54Z

Анна: /* Асимптотика */

<tex dpi = "200"> O \mid p_{i,j} = 1 \mid \sum T_{i} </tex>
{{Задача
|definition=
Дано <tex>m</tex> одинаковых станков, которые работают параллельно, и <tex>n</tex> работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания <tex>d_i</tex> {{---}} время, до которого она должна быть выполнена. Необходимо минимизировать суммарную [[Классификация_задач#Критерий оптимизации|медлительность]].
}}
== Описание алгоритма ==
=== Идея ===
Будем полагать, что работы заданы в порядке неубывания их дедлайнов, то есть <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>.
{{Лемма
|statement=
Пусть есть работы <tex>1 \ldots n</tex> с дедлайнами <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Тогда существует оптимальное расписание, в котором времена завершения работ идут в том же порядке, то есть <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex>.
|proof=
Рассмотрим две работы <tex>i</tex> и <tex>j</tex> из какого-либо оптимального расписания такие, что <tex>C_i > C_j</tex> и <tex>d_i < d_j</tex>. Поменяем эти работы в расписании местами, то есть <tex>C'_i = C_j</tex> и <tex>C'_j = C_i</tex>. Если они обе успевали выполниться вовремя, то это свойство сохранится, так как <tex>d_i < d_j</tex>, значит по-прежнему <tex>T_i = 0</tex> и <tex>T_j = 0</tex>, то есть значение целевой функции мы не ухудшили и расписание осталось оптимальным. Если обе работы не успевали выполниться вовремя, то когда мы поменяем их местами ничего не изменится, то есть значение целевой функции останется прежним, так как мы не меняли значения времен окончаний, а только поменяли их местами. Если работа <tex>j</tex> успевала выполниться, а <tex>i</tex> {{---}} нет, то мы снова не ухудшим значение целевой функции. Покажем это. До того, как мы поменяли работы местами, было <tex>T_i + T_j = C_i - d_i</tex>, так как <tex>T_j = 0</tex>. После того, как мы поменяли работы местами, <tex>T_i + T_j = C'_i - d_i + C'_j - d_j = C_j - d_i + C_i - d_j = C_i - d_i + (C_j - d_j)</tex>. Но так как работа <tex>j</tex> успевает выполниться до дедлайна, то <tex>C_j - d_j \leqslant 0</tex>.
}}
Далее будем рассматривать только оптимальное расписание со свойством <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex>.
{{Теорема
|statement=
Всегда существует оптимально расписание такое, что в нем <tex>C_i \leqslant m + i - 1</tex> для любого <tex>i = 1 \ldots n</tex>, где <tex>m</tex> {{---}} количество станков.
|proof=
Рассмотрим оптимальное расписание <tex>S^*</tex>, в котором для любого <tex>i = 1 \ldots k - 1</tex> выполняется <tex>C_i \leqslant m + i - 1</tex>, но <tex>C_k > m + k - 1</tex>, где <tex>k</tex> максимально среди всех возможных. Для начала покажем, что <tex>k</tex> не меньше <tex>2</tex>. Пусть есть оптимальное расписание, у которого <tex>C_1 > m</tex>. Это значит, что есть период времени <tex>t</tex> такой, что первая работа выполняется в момент <tex>t</tex> и не выполняется в <tex>t - 1</tex>. Поменяем эти периоды времени местами. То есть все работы, которые выполнялись в момент <tex>t - 1</tex>, будут выполняться на тех же станках, но в момент <tex>t</tex>, и наоборот. Значение <tex>C_i</tex> для каждой работы <tex>i</tex> не увеличится, так как <tex>C_1</tex> было минимальным из них, а значит ни одна работа не могла быть закончена раньше периода времени <tex>t</tex>. Будем продолжать этот процесс, пока не будет выполнено равенство <tex>C_1 = m</tex>. 
Теперь пусть <tex>C_k = m + k + t</tex>, где <tex>t \geqslant 0</tex>. Будем называть ''итерацией обработки'' работы обработку на одной машине. Разобьем все работы на три множества:
* множество <tex>A</tex> будет содержать все итерации обработки работ <tex>i = 1 \ldots k - 1</tex>
* множество <tex>B</tex> {{---}} все итерации, запланированные в расписании <tex>S^*</tex> строго после момента времени <tex>k + m + t</tex>
* множество <tex>C</tex> {{---}} итерации обработки работ <tex>i = k + 1 \ldots n</tex>, которые в <tex>S^*</tex> запланированы на время <tex>k + m + t</tex> и раньше
Таким образом, мы имеем три непересекающихся множества, которые вместе с работой <tex>k</tex> покрывают все итерации всех работ. 
Построим новое расписание <tex>S^*</tex>. Для начала расставим все работы из множества <tex>A \cup B</tex> так же, как они были запланированы в расписании <tex>S^*</tex>. Так как <tex>C_i \leqslant m + i - 1</tex> для <tex>i = 1 \ldots k - 1</tex>, ни одна итерация обработки в множестве <tex>B</tex> не поставлена раньше момента времени <tex>k + m + t</tex> и к моменту времени <tex>C_k = m + k + t</tex> выполнено <tex>k</tex> работ, то это значит, что между моментами времени <tex>1</tex> и <tex>k + m - 1</tex> на каждой машине есть <tex>m</tex> различных простоев, то есть моментов, когда на ней ничего не обрабатывается. Значит, мы всегда сможем поставить на эти простои итерации обработки работы <tex>k</tex>, даже если эти простои пересекаются. Таким образом, <tex>C_k \leqslant m + k - 1</tex>. 
Теперь назначим машины для операций из множества <tex>C</tex>. До момента времени <tex>k + m + t</tex> сейчас распланировано ровно <tex>k</tex> работ, так как по определению работы из множества <tex>B</tex> запланированы на время строго большее <tex>k + m + t</tex>. Значит, между моментами времени <tex>1</tex> и <tex>k + m + t</tex> есть <tex>k + m + t - k = m + t</tex> различных простоев на каждой машине. Исходя из определения множества <tex>C</tex> и того, что к моменту <tex>k + m + t</tex> распланировано <tex>km</tex> итераций обработок, приходим к неравенству <tex>|C| \leqslant (k + m + t)m - km = (m + t)m</tex>. Значит, мы можем распланировать итерации из множества <tex>C</tex> не позднее момента <tex>k + m + t</tex>. Таим образом, мы снова построили расписание для задачи open shop, которое так же является оптимальным, так как для множеств <tex>A</tex> и <tex>B</tex> все осталось как в оптимальном расписании <tex>S^*</tex>, работу <tex>k</tex> мы научились выполнять быстрее, а для множества <tex>C</tex> ответ был не ухудшен. Любая работа <tex>j</tex>, итерации обработки которой принадлежат множеству <tex>C</tex>, имела время окончания <tex>C_j \geqslant m + k + t</tex>. Однако это противоречит тому, что мы выбрали максимальное <tex>k</tex>.
}}
Отсортируем работы в порядке неуменьшения дедлайнов. Для текущей работы <tex>i</tex> вычислим ''лимит'' <tex>T_i</tex> {{---}} время, до которого закончится обработка данной работы, то есть <tex>1 \leqslant t_1 < t_2 < \ldots < t_m \leqslant T_i </tex>, где <tex>t_j</tex>, <tex>j = 1 \ldots m</tex> {{---}} периоды обработки работы <tex>i</tex>.
Будем выбирать эти периоды среди моментов времени, в которые выполняется наименьшее число работ.

=== Псевдокод ===
Определим ''вектор частот'' <tex>h[t]</tex> {{---}} количество работ во временном интервале <tex>t</tex>. Работы отсортированы в порядке <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>.

'''function''' scheduler():
'''int''' <tex>h[m + n - 1]</tex>
'''vector<int>''' <tex>s[n]</tex>
'''fill'''(<tex>h,\ 0</tex>)
'''fill'''(<tex>s,\ \varnothing</tex>)
'''for''' <tex>i = 1</tex> '''to''' <tex>n</tex>
'''if''' <tex>d_i < m + i - 1</tex>
вычислим <tex>z</tex> {{---}} количество временных интервалов <tex>t = 1 \ldots d_i</tex>, таких, что <tex>h[t] < m</tex>
'''if''' <tex>z \geqslant m</tex>
<tex>T_i = d_i</tex>
'''else'''
<tex>T_i = d_i + m - z</tex>
'''else'''
<tex>T_i = m + i - 1</tex>
вычислим <tex>m</tex> периодов <tex>1 \leqslant t_1 < t_2 < \ldots < t_m \leqslant T_i </tex> с минимальными значениями <tex>h[t_j]</tex>
'''for''' <tex>j = 1</tex> '''to''' <tex>m</tex>
<tex>s[i] = s[i] \cup \{t_j - 1\}</tex> // ставим работу <tex>i</tex> на время <tex>[t_j - 1, t_j]</tex>
<tex>h[t_j] = h[t_j] + 1</tex>
'''return''' <tex>s</tex>

=== Асимптотика ===
Алгоритм может работать за <tex>O(nm)</tex>. Чтобы получить алгоритм с такой сложностью, мы распределяем работы так, чтобы после каждого шага <tex>i</tex> сохранялся инвариант <tex>l_1 \geqslant l_2 \geqslant \ldots \geqslant l_m </tex> при <tex>l_1 \geqslant T_i</tex>, такой, что на станке <tex>M_j</tex> все промежутки <tex>1 \ldots l_j</tex> заняты.
На первом шаге алгоритма <tex> l_1 = l_2 = \ldots = l_m = 0 </tex>. Предположим, что инвариант сохранился после шага <tex> i - 1 </tex>. Тогда <tex> T_{i-1} \leqslant T_i </tex> и, для сохранения инварианта, распределим работу в следующем порядке: 
<center><tex>l_1 + 1 \ldots T_i</tex> на станке <tex> M_1 </tex>, 
<tex>l_2 + 1 \ldots l_1</tex> на станке <tex> M_2 </tex>, 
<tex> \vdots </tex> 
<tex>l_m + 1 \ldots l_{m-1}</tex> на станке <tex> M_1 </tex>.
</center>
Таким образом, мы получаем распределение одной работы по <tex>m</tex> станкам для <tex>n</tex> работ. Итоговая асимптотика {{---}} <tex>O(nm)</tex>.

== Доказательство корректности ==
{{Теорема
|statement=Алгоритм строит оптимальное расписание для задачи <tex> O \mid p_{i,j} = 1 \mid \sum T_{i} </tex>
|proof= Воспользуемся для доказательства леммой и теоремой, которые доказаны выше. Из них мы знаем, что существует оптимальное расписание, для которого выполняются свойства <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex> и <tex>C_i \leqslant m + i - 1</tex> для любого <tex>i = 1 \ldots n</tex>, где <tex>m</tex> {{---}} число станков. Пусть <tex>B</tex> оптимальное расписание, которое удовлетворяет свойству, по которому работы <tex>1 \ldots k - 1 </tex> поставлены в те же временные промежутки, в которых они оказались следуя нашему расписанию <tex>A</tex>. Более того, предположим, что <tex>B</tex> было выбрано так, что <tex>k</tex> максимально.
Пусть <tex>C_k > T_k</tex>. С того момента, как работа <tex>k</tex> поставлена в расписании <tex>A</tex> перед <tex>T_k</tex>, определим временной промежуток <tex>t \leqslant T_k </tex> в месте, где работа <tex>k</tex> не выполняется в <tex>B</tex>. Тогда в самом расписании <tex>B</tex> этот промежуток или также пустой или он занят работой <tex>r > k</tex>.
* Если он пустой, мы перемещаем операцию <tex>k</tex>, которая была распределена в промежуток <tex>C_k</tex>, в этот промежуток.
* Если работа <tex>r</tex> стоит во время <tex>t</tex>, но не во время <tex>C_k</tex>, то мы меняем между собой операции работ <tex>k</tex> и <tex>r</tex>.
* Если работа <tex>r</tex> поставлена во время <tex>t</tex> и <tex>C_k</tex>, то, либо тут есть пустое место в <tex>C_r + 1</tex>, либо там должна быть работа, назовем ее <tex>v</tex>, которая поставлена на время <tex>C_r + 1</tex>, но не поставлена в <tex>C_k</tex>.
Работа <tex>v</tex> точно там есть, потому что <tex>r</tex> и <tex>k</tex> поставлены на время <tex>C_k</tex>, но не поставлены на время <tex>C_r + 1</tex>. Если свободный промежуток есть, тогда переставим работу <tex>r</tex> со времени <tex>t</tex> на время <tex>C_r + 1</tex> и работу <tex>k</tex> со времени <tex>C_k</tex> на <tex>t</tex>. Иначе мы можем переместить работу <tex>r</tex> с времени <tex>t</tex> на время <tex>C_r + 1</tex>, <tex>k</tex> c <tex>C_k</tex> на <tex>t</tex>, и <tex>v</tex> с <tex>C_r + 1</tex> на <tex>C_k</tex>. Тогда <tex>C_k</tex> должно уменьшиться как минимум на один, а <tex>C_r</tex> увеличится не больше чем на один.
Если мы продолжим так действовать, мы получим оптимальное расписание <tex>B'</tex> с <tex>C_k \leqslant T_k</tex>, в котором работы <tex>1 \ldots k-1</tex> расположены так же, как в расписании <tex>A</tex>.
Пусть <tex>h</tex> {{---}} вектор частот для части расписания из работ от <tex>1</tex> до <tex>k - 1</tex>. Предположим, что <tex>h(t') < h(t)</tex> и работа <tex>k</tex> выполняется во временной промежуток <tex>t</tex>, но не выполняется в <tex>t'</tex> в расписании <tex>B'</tex>. Если в <tex>B'</tex> станок простаивает во время <tex>t'</tex>, мы можем переместить работу <tex>k</tex> из <tex>t</tex> в <tex>t'</tex>. Иначе работа <tex>r > k</tex> находится в расписании в промежутке <tex>t'</tex>, но ее нет в <tex>t</tex>. Мы можем передвинуть <tex>r</tex> в <tex>t</tex> и <tex>k</tex> в <tex>t'</tex> без увеличения целевой функции, потому что <tex>C_k \leqslant C_r</tex>. Продолжая действовать таким образом, мы достигнем оптимального расписания, в котором работы <tex>1 \ldots k</tex> расположены таким же образом, как и в <tex>A</tex>. Мы получили противоречие, так как выбранный <tex>k</tex> оказался не максимальным.
}}

== См. также ==
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
* [[Opij1di|<tex> O \mid p_{i, j} = 1, d_i \mid - </tex>]]
* [[Opij1sumwu|<tex> O \mid p_{i, j} = 1 \mid - \sum w_{i} U_{i}</tex>]]
== Источники информации ==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 171-174 ISBN 978-3-540-69515-8

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

Opij1SumTi

2016-06-05T11:38:05Z

Анна: /* Псевдокод */

Opij1SumTi

2016-06-05T11:30:10Z

Анна: /* Псевдокод */

Opij1SumTi

2016-06-05T11:26:00Z

Анна: /* Псевдокод */

Opij1SumTi

2016-06-05T11:17:46Z

Анна: /* Псевдокод */

Opij1SumTi

2016-06-05T11:11:39Z

Анна: /* Псевдокод */

Opij1SumTi

2016-06-05T11:10:51Z

Анна: /* Псевдокод */

Opij1SumTi

2016-06-05T11:10:08Z

Анна: /* Псевдокод */

Opij1SumTi

2016-06-05T08:01:17Z

Анна: Новая страница: «<tex dpi = "200"> O \mid p_{i,j} = 1 \mid \sum T_{i} </tex> {{Задача |definition= Дано <tex>m</tex> одинаковых станков, которые ...»