ТМВ-2019-Семинар-04.02.2020

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Введение

Из курса «Архитектура вычислительных систем» мы знаем, что есть довольно много различных архитектур построения компьютеров, все они разные, но в то же время мы понимаем, что элементарно они примерно одинаковые, т. е. решают примерно схожие задачи. Мы же хотим рассуждать обо всех компьютерах на неком простом языке в контексте вопроса: «Какие задачи мы можем решать с помощью компьютера?».

Для этого нужно разобраться сначала с тем, что же есть компьютер? Ввести некий формализм понятия «компьютер». Таким понятием, характеризующим компьютер как математическую модель, является автомат. Автоматы очень просты, и эта математическая простота позволяет довольно легко рассуждать и манипулировать ими. При этом, если мы выберем достаточно точную математическую модель, то мы сможем утверждать, что знаем практически всё о сложном компьютере, так как автомат, который нами уже исследован, может делать всё, что и компьютер.

Автоматы бывают различными. Начнём знакомство с конечными автоматами.

Конечные автоматы

Рис. 1 — Примеры автоматов

Конечные автоматы – автоматы, которые имеют конечное число состояний. Такие автоматы характеризуют компьютеры с ограниченными ресурсами. На рис. 1 приведены 3 различных конечных автомата (в этом случае ресурсами являются состояния). Модели конечных автоматов показывают на что способны компьютеры (верхняя граница создаваемых компьютеров). Рассмотрим некоторые базовые понятия, необходимые для дальнейшей работы. Более подробно все термины будут даваться на лекциях.

Одним из основных понятий являются языки. Язык – множество некоторых слов. В свою очередь, слово – последовательность букв. Также у нас есть алфавит. Алфавит – непустое конечное множество букв. В теории формальных языков буквы – это некоторые символы. Буквы составляются в некоторый алфавит, слова являются буквами. Для каждого слова можно сказать, в каком алфавите или множестве алфавитов оно находится. А язык – нечто, что определено на алфавите, которое определяет множество слов. При этом мы решаем вопрос: «А для каких языков мы можем построить автоматы, которые точно смогут сказать: является ли слово частью языка или нет?». Например, рассмотрим крайний слева автомат на рис. 1. Как сказано ранее, данный автомат является конечным. На изображении автомата мы видим:

  • конечное число состояний \(q_i\), обозначаемых кружочками;
  • переходы между состояниями, обозначаемые стрелками и помеченные буквами (могут быть и слова);
  • специальные состояния: начальное \(q_0\) (состояние, переход в которое пустой) и конечное \(q_3\) (кружочек с маленьким кружочком внутри).

Соответственно пусть нам дана некая строчка: \(0100\). Последовательность обработки этого слова, следующая:

\[q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_3 \xrightarrow{0} q_2 \xrightarrow{0} q_3\]

Если после обработки слова мы оказались в конечном состоянии, то можно сделать вывод, что слово является частью языка.

Приведём контрпример: \(01111\). Обрабатывая это слово, делаем вывод: оно не является частью языка.

\[q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_3 \xrightarrow{1} q_1 \xrightarrow{1} q_3 \xrightarrow{1} q_1\]

Важно понимать, что на самом деле, анализируя работу такого автомата, мы не помним историю переходов из одного состояния в другое. Всегда, находясь в каком-то очередном состоянии, зная какой символ слова рассматриваем, можем продолжать операции. Это довольно простая модель, и при этом автомат не может находиться в нескольких состояниях одновременно.

Рассмотрим автомат по центру на рис. 1. Видим проблему, что, например, рассматривая слово \(000\), после перехода из \(q_0\) в \(q_1\) дальнейший переход невозможен, так как нет соответствующего пути. Теперь посмотрим на автомат справа на рис. 1. Рассматривая слово \(1001\) снова натыкаемся на проблему, но уже другую. После перехода из \(q_0\) в \(q_1\) дальнейший переход из \(q_1\) возможен по двум путям. Эти проблемы мы решим в дальнейшем. Пока будем ограничиваться строгим формализмом, для которого проблем, обозначенных выше не будет.

Рис. 2 — Автомат, определяющий слово, заканчивающееся на 00 или 11

Обозначим свойства такого строгого автомата:

  • наличие конечного состояния (не обязательно одного);
  • наличие единственного начального состояния;
  • для каждой буквы алфавита \(\Sigma\) есть единственный переход из каждого состояния по этой букве.

Рассмотрим автомат на рис. 2 и попытаемся определить, какой язык он определяет. Нетрудно заметить, что языком данного автомата будет любое слово на алфавите, которое заканчивается на \(00\) или \(11\).

Перейдём к такому понятию как язык автомата. Язык \(L\) автомата \(D\) – такое множество слов, что \(D\) определяет это множество.

$$L(D)=\{\,\omega\in\Sigma^*\mid\omega$$ определяется $$D\}$$

Здесь \(\Sigma^*\) – множество всех слов алфавита \(\Sigma\), включая пустое слово \(\varepsilon\).

Решение задач

Задача 1. Количество по модулю

Построить автомат на алфавите \(\Sigma = \{a, b\}\), чтобы количество букв \(b\) по модулю \(3\) было равно \(2\).

$$L =\{\,\omega\in\{a, b\}^*\mid k_b \mod 3 = 2\}$$
1 3 — Автомат (b mod 3 = 2).jpg

Задача 2

Построить автомат, определяющий слова в которых после \(1\) всегда идёт \(0\).

$$L =\{\,\omega\in\{0, 1\}^*\mid $$ после \(1\) всегда следует \(0\)$$\}$$
1 4 — Автомат (после 1 всегда идёт 0).jpg

Задача 3

Построить автомат, в котором каждое слово заканчивается на два нуля.

$$L =\{\,\omega\in\{0, 1\}^*\mid\omega$$ заканчивается на \(00\)$$\}$$
1 5 — Автомат (слова, заканчивающиеся на 00).jpg

Задача 4. Подстрока

Построить автомат, в котором есть подстрока из двух нулей.

$$L =\{\,\omega\in\{0, 1\}^*\mid\omega$$ содержит \(00\)$$\}$$
1 6 — Автомат (слова, содержащие 00).jpg

Задача 5. Доска Гальтона

Построить автомат, определяющий, что шарик на доске Гальтона упадёт в ящик \(C\).

Обозначим: \(0\) – если шарик на очередном штырке падает влево, \(1\) – вправо.

1 7 — Автомат (доска Гальтона).jpg

Задача 6. Комментарии на С++

Построить автомат, определяющий корректные комментарии вида /*...*/ на языке С++. Алфавитом будет $$\Sigma = \{a, *, /\}$$, где \(a\) – любой допустимый символ, кроме /, *.

1 8 — Автомат (корректный комментарий на C++).jpg

Пересечение и объединение двух автоматов

Рис. 3 — Пересечение автоматов

Попробуем построить автомат, определяющий слова, в которых после \(1\) всегда идёт \(0\) и которые оканчиваются на \(00\).

Нетрудно заметить, что нами в задаче 2 и задаче 3 уже построены автоматы для каждого из двух условий строимого автомата. Воспользуемся этими автоматами для построения, т. е. найдём пересечение этих двух автоматов.

Для начала необходимо построить декартово произведение всех состояний. Для удобства переобозначим состояния автомата из задачи 3: $$r_i=q_i\: \forall i$$. На рис. 3 изображены все пары состояний \((q_i,r_j)\). Нетрудно догадаться, что начальным состоянием будет пара \((q_0, r_0)\), т. к. оба этих состояния являются начальными в своих автоматах. Соответственно, конечным состоянием будет – \((q_0, r_2)\) (оба состояния в этой паре – конечные).

Начинаем строить автомат. Из \((q_0, r_0)\) по \(0\) мы перейдём в \((q_0, r_1)\), т. к. на первом автомате \(q_0 \xrightarrow{0} q_0\), а на втором автомате \(r_0 \xrightarrow{0} r_1\). Аналогично строим все оставшиеся пути. Глядя на получившийся автомат, можно заметить, что состояния \((q_2,r_i)\:\forall i = \overline {0, 2}\) можно объединить в одно тупиковое, т. к. ни из одного из них невозможно попасть в конечное состояние.

При построении объединения двух автоматов отличием будет лишь то, что конечными состояниями будут пары, в которых хотя бы одно состояние из двух конечное в своём автомате. В нашем примере помимо \((q_0, r_2)\) это будут пары \((q_0, r_0),\:(q_0, r_1),\:(q_1, r_2),\:(q_2, r_2)\).

Задача для самостоятельного разбора

Построить автомат, определяющий слова, в которых каждая десятая буква справа есть \(1\).