Вопросы для самостоятельной подготовки и защиты л.Р.

На защите лабораторной работы студент должен знать:

– определение множества как понятия, способы задания множеств, мощность множества;

– определение вектора как понятия, отличия вектора от множества;

– операцию «прямое произведение множеств», ее свойства;

– действия с алфавитом по созданию формального языка (возведение алфавита в целую положительную и нулевую степень, итерация, усеченная итерация алфавита);

– переход от вектора к цепочке (слову), операции с цепочками (конкатенация (сцепление), итерация (возведение в степень), понятия «длина цепочки», пустая цепочка.

уметь:

– выполнять действия с множествами, алфавитом, цепочками;

– определять мощность множеств, степеней алфавита, длину цепочек;

– объяснять по листингу программы процесс проверки цепочки на ее принадлежность к языку.

Лабораторная работа № 2 Построение конечного автомата – распознавателя для заданного регулярного множества

Цель работы: – выработка навыков построения и минимизации конечных автоматов для распознания регулярного множества цепочек.

Задание

Построить конечный автомат (КА–распознаватель) для распознания регулярного множества цепочек трехсимвольного алфавита в соответствии с вариантом и реализовать его в виде программы на С++ :

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

2.Составить таблицу переходов конечного автомата в стандартном виде и убедиться в правильности его работы (для проверки вручную пошагово распознать правильную цепочку длиной не менее 6-ти символов).

3. Минимизировать полученный КА (проверить полученный автомат на эквивалентность и достижимость состояний).

4.Привести полное описание конечного автомата.

5.Составить и продемонстрировать программу на С++, реализующую работу конечного автомата.

Выбор варианта: студент выбирает № варианта задания, определив значение t , где t = N mod10 – остаток от деления нацело числа N (порядковый номер студента в основном списке).

Таблица 2– Индивидуальные задания к лабораторной работе 2

t (инд.вар)	Описание регулярного множества
0	Содержит ровно два символа «b», заканчивается на «ас» и символы «b» и «с» не стоят рядом
1	Содержит не менее двух символов «с», начинается на символ «а», а символ «b» встречается только по парам
2	Начинается с символа «b», заканчивается символом «а», а символ «с» встречается в сочетании по два не менее одного раза
3	Начинается с символа «b», сочетание символов «ас» встречается не менее двух раз, а заканчивается на сочетание «bb»
4	Начинается на сочетание «aa», символ «b» встречается не менее двух раз, и цепочка заканчивается на сочетание «ас»
5	Содержит не более двух символов «b», начинается на «ас», а символ «с» встречается только парами
6	Содержит ровно два символа «с», заканчивается на «bс» и символы «а» и «b» не стоят рядом
7	Содержит не более двух символов «с», начинается на «сb», а символ «а» встречается только парами
8	Содержит не менее двух символов «b», заканчивается на «аа» и символы «b» и «с» не стоят рядом
9	Содержит не более двух символов «с», начинается на «ас», а символы «а» встречается только по одному

Вопросы для самостоятельной подготовки и защиты л.р.

1 Понятие конечного автомата (КА); задание КА.

2 Минимизация КА. Алгоритмы поиска, эквивалентных и недостижимых состояния КА.

3 Построение диаграммы переходов КА.

4 Построение таблицы переходов для КА.

5 Hедетерминированный конечный автомат (HКА); преобразование HКА в эквивалентный КА.

Лабораторная работа № 3

Построение автоматов с магазинной памятью (МП – автоматов)

Цель работы – выработка навыков построения МП–автоматов для распознания множества А или трансляции множества А входных цепочек в множество В выходных цепочек.

Задание

Построить в соответствии с вариантом МП–распознаватель или МП–транслятор для распознания множества А входных цепочек (или преобразования(трансляции) множества А входных цепочек в множество В выходных цепочек) и реализовать его в виде программы на С++.

Для этого:

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

2 Составить управляющую таблицу в стандартном виде в соответствии с описанием в п.1.

3 Убедиться в правильности работы МП–автомата, распознав (преобразовав) пошагово несколько цепочек.

4 Привести полное описание МП–автомата.

5 Реализовать полученный МП–автомат в виде программы на С++ и продемонстрировать его работу.

Выбор варианта: студент выбирает № варианта задания, определив значение t , где t = N mod11 – остаток от деления нацело числа N (порядковый номер студента в основном списке).