Определение.
Если после считывания последней литеры строки автомат будет находиться в одном из последних состояний, то о строке говорят, что она принадлежит языку, принимаемому автоматом. В противном случае строка не принадлежит языку, принимаемому автоматом.
Пример.
Рассмотрим автомат M0 = (К, , , S, F),
где К ={А, В}, S = {0, 1}, S = {A}, F = {A},
= { (А, 0) = А,
(А, 1) = В, (В, 0) = В,
(В, 1) = А}.
Эти переходы означают, что "при чтении 0 в состоянии А управление передается в состояние А и т. д.
При чтении строки 0110010111 управление последовательно передается в следующем порядке через состояния А, А, В, А, А, А, В, В, А, В, А.
Так как А — есть последнее состояние, строка принимается конечным автоматом.
Однако, при чтении строки 00111 автомат
проходит через состояния А, А, А, В, А, В.
В не является последним состоянием
строка 00111 не принимается, т.е. она не
принадлежит языку, принимаемому этим
автомат.
В связи с тем, что нули не влияют на состояние автомата, каждая единица изменяет его состояние с А на В и с В на А, и начальное состояние является тем же, что и последнее состояние. Язык, принимаемый автоматом, состоит из тех строк, которые содержат четное число единиц.
Переходы можно представить также с помощью таблицы и схематически:
Определение.
Автомат называется детерминированным, если в каждом элементе таблицы переходов содержится одно состояние. В недетерминированном конечном автомате это положение не выдерживается.
Следовательно, автомат
— детерминированный.
-
Последовательность выполнения.
Для выполнения лабораторной работы требуется умение писать программы на алгоритмическом языке, а также начальные знания по порождающим грамматикам.
Таким образом, последовательность выполнения лабораторной работы следующая:
-
Ознакомится с теорией регулярных грамматик.
-
В соответствии с заданным регулярным выражением написать регулярную грамматику.
-
Записать соответствующий детерминированный конечный автомат с указанием таблицы переходов.
-
Написать и отладить на компьютере синтаксический анализатор, распознающий выражения регулярного языка.
-
Привести контрольную распечатку.
-
Оформить отчет.
Работа считается выполненной только после оформления отчета, защиты и подписи преподавателя.
-
Методический пример.
Программа "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.