Постановка задачи к лабораторной работе № 7

 

Разработать программное средство, автоматизирующее процесс разбора цепочек для грамматик простого предшествования. Программное средство должно выполнять следующие функции:

1) ввод произвольной грамматики;

2) построение множеств L (A) и R (A)для каждого нетерминального символа грамматики;

3) формирование матрицы простого предшествования для введенной грамматики;

4) проверка условия простого предшествования для данной грамматики;

5) моделирование функционирования распознавателя для грамматик простого предшествования.

Составить набор контрольных примеров для случаев:

а) введенная грамматика не является грамматикой простого предшествования;

б) исходная грамматика является грамматикой простого предшествования, но анализируемая строка не принадлежит языку грамматики;

в) заданная грамматика является грамматикой простого предшествования и входная строка принадлежит языку грамматики.

Разбор цепочек представить в виде таблицы, строки вывода и дерева вывода.

Вариантами индивидуального задания к лабораторной работе № 7 являются выходные данные лабораторной работы № 4.

 

Тема и цель лабораторной работы

Лабораторная работа № 2.

Тема: «Построение конечного автомата по регулярной грамматике»

 

Цель: -закрепить понятия «регулярная грамматика», «недетерминированный и детерминированный конечный автомат»;

- сформировать умения и навыки построения конечного автомата по регулярной грамматике и преобразования недетерминированного конечного автомата к детерминированному конечному автомату.

 

Постановка задачи

Дана регулярная грамматика G = ({ A, B, C, S }, { a, b }, P, S), где Р: 1) S ® aB | aA;

2) A ® aA | bC | b;

3) B ® bB | aC | a.

 

Разработать программное средство, реализующее следующие функции:

1) ввод произвольной формальной грамматики с клавиатуры и проверка ее на принадлежность к классу регулярных грамматик;

2) построение по заданной регулярной грамматике конечного автомата;

3) преобразование недетерминированного конечного автомата к детерминированному конечному автомату;

4) вывод графа результирующего конечного автомата на экран.

3 Формальная модель задачи

Определение 1. Детерминированным конечным автоматом (ДКА) называется пятерка объектов:

 

, (2.1)

 

где - конечное множество состояний автомата;

- конечное множество допустимых входных символов;

- функция переходов, отображающая множество Q´T во множество Q;

- конечное множество начальных состояний автомата;

Z - множество заключительных состояний автомата, Z Í Q.

Определение 2. Недетерминированным конечным автоматом (НКА) называется конечный автомат, в котором в качестве функции переходов используется отображение во множество всех подмножеств множества состояний автомата , т.е. функция переходов неоднозначна, так как текущей паре соответствует множество очередных состояний автомата .