Лекции по дискретке (1021001), страница 21

Файл №1021001 Лекции по дискретке (Лекции по дискретке) 21 страницаЛекции по дискретке (1021001) страница 212017-07-092017-07-09СтудИзба

Лекции по дискретке

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

Регистрация/авторизация

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

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

Переходы можно представить также с помощью таблицы и схематически:

Определение.

Автомат называется детерминированным, если в каждом элементе таблицы переходов содержится одно состояние. В недетерминированном конечном автомате это положение не выдерживается.

Следовательно, автомат — детерминированный.

65.Последовательность выполнения.

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

Таким образом, последовательность выполнения лабораторной работы следующая:

Ознакомится с теорией регулярных грамматик.
В соответствии с заданным регулярным выражением написать регулярную грамматику.
Записать соответствующий детерминированный конечный автомат с указанием таблицы переходов.
Написать и отладить на компьютере синтаксический анализатор, распознающий выражения регулярного языка.
Привести контрольную распечатку.
Оформить отчет.

Работа считается выполненной только после оформления отчета, защиты и подписи преподавателя.

66.Методический пример.

Программа "grammatika", представляющая синтаксический анализатор, соответствующий детерминированному конечному автомату М, имеет следующий вид:

program grammatika;

uses crt;

type perehod = record

old, term, new: char;

end;

var sost:array [1 .. 13] of perehod;

stroka: string [255];

sim, neterm: string [1];

dlina, n, i: integer;

ok: boolean;

begin { блок определения таблицы переходов }

sost[1].old :='S'; sost[1].term :='2'; sost[1].new := 'A';

sost[2].old :='A'; sost[2].term :='2'; sost[2].new := 'B';

sost[3].old :='B'; sost[3].term :='1’; sost[3].new := 'C';

sost[4].old := 'C'; sost[4].term := 'b'; sost[4].new := 'S';

sost[5].old := 'S'; sost[5].term := 'b'; sost[5].new := 'D';

sost[6].old :='D'; sost[6].term :='2'; sost[6].new :='E';

sost[7].old :='E'; sost[7] .term := '1'; sost[7].new :='F';

sost[8].old := 'F'; sost[8].term := 'b'; sost[8].new := 'D';

sost[9].old := 'F'; sost[9].term := '2'; sost[9].new := 'K';

sost[10].old:='B'; sost[10].term :='2'; sost[10].new := 'K';

sost[11].old := 'K'; sost[11].term := '2'; sost[11].new := 'L';

sost[12].old := 'L'; sost[12].term := '2'; sost[12].new := 'M';

sost[13].old := 'M'; sost[13].term := '2'; sost[13].new := 'L';

clrscr;

{ блок основной программы }

while TRUE do begin

writeln ('Введите строку символов^’);

readln (stroka);

dlina := length (stroka);

n:=0;

ok :=' TRUE;

neterm := 'S';

while ok and (n < dlina) do

begin i := 0;

n:=n+ 1

sim := copy (stroka, n, 1);

ok := FALSE;

repeat i:=i+l;

if ((sost [i].old = neterm) and

(sost [i].term = sim)) then

begin

ok := TRUE;

neterm := sost[i].new;

end;

until ( ok or (i = 13));

end;

if ((neterm = 'S') or (neterm = 'B') or (neterm = 'F') or (neterm = 'L') and ok then writeln ('Данная строка принадлежит языку')

else writeln ('Данная строка не принадлежит языку'); readkey; end; end.