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

Текст из файла (страница 2)

Вычисление е-замыкания

Внести все состояния множества Т в стек stack;

Инициализировать e-closure(T) множеством Т;

While stack не пуст do begin

Снять со стека верхний элемент t

For каждое состояние u c дугой

От t к u, помеченной е do

If u not € e-closure(T) then begin

Добавить u к e-closure(T);

Поместить u в stack

End

End

Алгоритм. «Минимизация количества состояний ДКА»

Вход. ДКА М с множеством состояний S: множеством входных символов Е: переходами, определенными для всех состояний и входных символов: стартовым состоянием s₀ и множеством заключительных состояний F.

Выход. ДКА M’, допускающий тот же язык, что и М, и имеющий наименьшее возможное количество состояний.

Метод.

1. Построить начальное разбиение П множества состояний с двумя группами; заключительные состояния F и незаключительные состояния S-F.

2. Применить процедуру к разбиению П для построения нового разбиения Пн.

3. Если П_new=П, то П_final=П, и перейти к шагу (4). В противном случае повторить шаг (2) с П:=П_new

4. Выбрать одно состояние в каждой группе разбиения П_final в качестве представителя этой группы. Представители будут состояниями ДКА М’. пусть s является представителем. Предположим, что для входного символа а в М существует переход из s в t. Пусть r - представитель группы, в которой находится t (r может являться t). Тогда М’ имеет переход из s в r по а. Стартовым состоянием M’ сделать представителя группы, содержащей стартовое состояние s₀ автомата М, а заключительными состояниями М’ – представителей в F.

5. Если М’ имеет мертвое состояние, т е состояние d, которое не является заключительным и имеет переходы в себя для всех входных символов, удалим его из M’. Удалим также все состояния не достижимые из стартового.

Построение П_new

For каждая группа G € П do begin

Разделить G на подгруппы, такие, что два состояния s и t из G находятся в одной и той же подгруппе тогда и только тогда, когда для всех входных символов а состояния s и t переходы по а в состояния из одной и той же группы П

Заменить G в П_new множеством всех созданных групп

End

Условие:

1. По регулярному выражению построить диаграмму переходов конечного автомата.

2. По построенной диаграмме построить таблицу состояний.

3. Проверить является ли построенный конечный автомат недетерминированным, записать объяснение.

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

5. Проверить является ли построенный конечный автомат минимальным, записать объяснение.

6. Если конечный автомат не является минимальным, то минимизировать его.

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

Варианты:

Пример построения конечного автомата:

1. Формулировка задания: d|a²(ab)*c

2. Диаграмма переходов конечного автомата:

Примечание:

1. Построенный автомат является недетерминированным, потому что есть е-переходы. Детерминируем конечный автомат.

1. Для полученного конечного автомата построим таблицу состояний.

1. Конечный автомат является неминимизированным. Минимизируем .

Вводим дополнительное состояние q6

Строим дерево разбора.

Алгоритм минимизации.

1. Пусть множество П(0,1,2,3,4,5,6) – множество всех состояний. Разобьем его на два подмножества согласно условию с состояниями (0,1,2,3,4,6) и (5).

2. Первое подмножество разбиваем еще на 2 с состояниями (0,1,3,6) и (2,4), потому что для всех входных символов переход по входному символу в состояние из одной и той же группы.

3. Первое подмножество делим на 2 с состояниями (0,1,6) и (3).

4. Перовое подмножество делим на 2 с состояниями (0,6) и (1).

5. Первое подмножество после предыдущего деления делим на 2 с состояниями (0) и (6).

В результате получили, что из состояний 2 и 4 можно оставить только одно, например 2. Количество состояний конечного автомата уменьшилось на одно.

Из полученного дерева видим, что состояния q2 и q4 можно объединить в одно состояние q3.

Получили детерминированный и минимизированный конечный автомат.

Задача 2 «Построение КС-грамматики»

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

Определение: Контекстно-свободная грамматика состоит из 4 компонентов - терминалов, нетерминалов, стартового символа и продукций.

Определение: Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII — латинские буквы, цифры и спец. символы.

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

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

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

Определение: Продукция называется продукцией нетерминала, если он записан в левой части.

Определение: порождающая грамматика G – это четверка (VT, VN, P, S), где

VT – алфавит терминальных символов (терминалов),

VN – алфавит нетерминальных символов (нетермитналов), не пересекающийся с VT,

P – конечное подмножество множества (VTﮟVN)⁺ *(VT∩VN)*; элемент (α, β) множества Р называется правилом вывода и записывается в виде α → β,

S – начальный символ (цель) грамматики, S € VN.

Определение: дерево называется деревом вывода (или деревом разбора) в КС-грамматике G = (VT, VN, P, S), если выполнены следующие условия:

1. каждая вершина помечена символом из множества (VTﮟVNﮟε), при этом корень дерева помечен символом S; листья – символами из (VTﮟε);

2. если вершина дерева помечена символом А € VN, а ее непосредственные потомки – символами а₁, а₂, ..., а_n, где каждое a_i € (VTﮟVN), то А→а₁а₂...а_n – правило вывода в этой грамматике;

3. если вершина дерева помечена символом А € VN, а ее единственный непосредственный потомок помечен символом ε , то А → ε – правило вывода в этой грамматике.

Определение: КС-грамматика называется неоднозначной, если существует хотя бы одна цепочка α € L(G), для которой может быть построено два или более различных деревьев вывода.

Определение: Левая факторизация представляет собой преобразование грамматики в пригодную для предикативного анализа.

Определение: Грамматика является леворекурсивной, если в ней имеется нетерминал А, такой, что существует порождение А =>Aα для некоторой строки α.

Соглашения по обозначениям

1. Эти символы являются терминалами:

А) строчные буквы из начала алфавита, такие как a,b,c;

Б) символы операторов, такие как +, -, и т.п.;

В) символы пунктуации, такие как запятые, скобки и т.п.;

Г) цифры 0, 1, 2, …, 9;

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

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