Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Задача 1 « Построение конечного автомата»

Теоретическая часть:

Определение: Регуля́рные выраже́ния (англ. regular expressions, сокр. RegExp, RegEx, жарг. регэ́кспы или ре́гексы) — система синтаксического разбора текстовых фрагментов по формализованному шаблону, основанная на системе записи образцов для поиска.

Определение: Регуля́рным мно́жеством (или, регуля́рным языком) называется формальный язык, который удовлетворяет приведённым ниже свойствам.

Определение: Диаграмма переходов – стилизованная блок-схема, изображает действия, выполняемые лексическим анализатором при вызове его синтаксическим анализатором для получения очередного токена.

Позиции в диаграмме переходов изображаются кружками и называются состояниями. Состояния соединены стрелками, называемыми дугами.

Одно из состояний имеет метку start – это начальное состояние диаграммы переходов в момент начала распознавания токена.

Определение: Конечный автомат — в теории алгоритмов математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных, при условии, что общее возможное количество состояний конечно. Конечный автомат является частным случаем абстрактного автомата.

Определение: Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.

Определение: Распознавателем языка называется программа, которая получает на вход строку х и отвечает «да», если х – предложение языка, или в противном случае «нет».

Определение: Недетерминированный автомат может иметь более одного перехода из состояния при одном и том же входном символе.

Правила, которые определяют регулярные выражения над алфавитом E.

1. Е представляет собой регулярное выражение, обозначающее {e}, т е множество, содержащее пустую строку.

2. Если а является символом из Е, то а – регулярное выражение, обозначающее {a}, т е множество, содержащее строку а. Хотя мы используем одну и ту же запись, технически регулярное выражение а отличается от строки а и символа а. Говорим ли мы о регулярном выражении, строке или символе – становится понятно из контекста.

3. Предположим, что r и s – регулярные выражения, обозначающие языки L( r) и L(s).

Тогда

• ( r)|(s) представляет собой регулярное выражение, обозначающее L( r) и L(s).

• ( r)(s) – регулярное выражение , обозначающее L( r)L(s).

• ( r)* - регулярное выражение, обозначающее (L( r))*.

• ( r) – регулярное выражение, обозначающее L( r).

Язык, задаваемый регулярным выражением, называется регулярным множеством.

Пусть Е={a,b}.

1. Регулярное выражение a|b обозначает множество {a,b}.

2. Регулярное выражение (a|b)(a|b) – {aa, ab, ba,bb}, множество всех строк из а и b длины 2. Другое регулярное выражение для того же множества – аа | ab | ba | bb.

3. Регулярное выражение а* - множество всех строк из нуля или более а, т е {e, a, aa,aaa, …}.

4. Регулярное выражение (a|b)* обозначает множество всех строк, содержащих нуль или несколько экземпляров а и b, т е множество всех строк из а и b. Другое регулярное выражение для этого множества – (а*b*)*.

5. Регулярное выражение а| a*b – множество содержащее строку а и все ее строки, состоящие из нуля или нескольких а, за которыми следует b.

Алгебраические свойства регулярных выражений

Недетерминированный конечный автомат (nondeterministic finite automaton, NFA) представляет собой математическую модель, состоящую из

• Множества состояний s;

• Множества входных символов Е (символов входного алфавита);

• Функции переходов move, которая отображает пары символ-состояние на множество состояний;

• Состояния s_0, известное как стартовое (начальное);

• Множества состояний F, известных как допускающие (конечные);

Детерминированный конечный автомат (deterministic finite automaton, DFA) является специальным случаем недетерминированного конечного автомата, в котором

• Отсутствуют состояния, имеющие е-переходы;

• Для каждого состояния s и входного символа а существует не более одной дуги, исходящей из s и помеченной как а.

Детерминированный конечный автомат имеет для любого входного символа не более одного перехода из каждого состояния. Если для представления функции переходов ДКА используется таблица, то каждая запись в ней представляет собой единственное состояние. Следующий алгоритм имитирует поведение ДКА при обработке входной строки.

Алгоритм «Моделирование ДКА»

Вход. Входная строка х, завершаемая символом конца файла eof, и ДКА D со стартовым состоянием s₀ и множеством заключительных состояний F.

Выход. «Да», если D допускает х, и «нет» в противном случае.

Метод. Ко входной строке х применяется алгоритм. Функция move(s,c) дает состояние, в которое происходит переход из состояния s при входном символе с. Функция nextchar возвращает очередной символ строки х.

S:=s₀;

C:= nextchar;

While c≠ eof do begin

S:= move(s,c);

C:= nextchar;

End;

If s € F then

Return “yes”

Else return “no”

Алгоритм. «Построение ДКА из НКА (построение подмножества)

Вход. НКА N.

Выход. ДКА D, допускающий тот же язык.

Метод. Данный алгоритм строит таблицу переходов Dtran так, чтобы D «параллельно» все возможные перемещения N по данной входной строке.

Операции над состояниями НКА

Построение подмножества

Изначально e-closure(s₀) является единственным состоянием в Dstates и непомечено;

While в Dstates имеется непомеченное состояние Т do begin

Пометить Т;

For каждый входной символ а do begin

U:=e-closure(move(T,a));

If U not € Dstates then

Добавить U как непомеченное состояние в Dstates;

Dtran[T,a]:=U

End

End

Множество состояний Dstates автомата D и таблицу его переходов Dtran можно создать следующим образом. Каждое состояние D соответствует множеству состояний НКА, в которых может находиться N после чтения некоторой последовательности входных символов, включая все возможные е-переходы до и после считанных символов. Стартовое состояние D – e-closure(s₀). Состояния и переходы добавляются в D согласно алгоритму. Состояние D является допускающим, если оно представляет собой множество состояний НКА, содержащих как минимум одно допускающее состояние N.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов книги