Тема 2: Распознаватели и автоматы.
Понятие и виды распознавателей.
Конечные автоматы.
Эквивалентные преобразования недетерминированных автоматов в детерминированные и ДА в НДА.
Понятие и виды распознавателей.
Распознаватель – это схематизированный алгоритм, определяющий некоторое множество.
Описание
языков с помощью распознавателей
является альтернативой описания языков
с помощью грамматик.
Распознаватели
состоят из четырёх частей: Входная
головка
УУ
|
a1 |
a2 |
… |
an |
Входная лента – последовательность ячеек, в каждой из которых содержится 1 символ алфавита языка.
Самый левый и правый символ – концевые маркеры.
Входная головка каждый момент считывает только один символ. Под УУ входная головка может переместиться на 1 шаг вправо или влево, либо остаться на месте.
Распознаватель, перемещающий головку только вправо, называется односторонним.
Распознаватель, который не только считывает символы ячейки, но и заменяет их на новые, называется преобразователем.
Внешняя память – хранилище информации некоторым типом, которая может быть организована по принципу магазина. Распознаватель будет с магазинной памятью.
Существует соответствие между видами распознавателей и видами грамматик.
Язык L автоматный тогда и только тогда когда он определяется односторонним детерминированным конечным автоматом.
Язык L контекстно-свободный тогда и только тогда когда он определяется односторонним недетерминированным автоматом с магазинной памятью.
Язык L контекстный тогда и только тогда когда он – двусторонний линейно-недетерминированный автомат.
Язык L перечислимый (язык типа 0) тогда и только тогда когда он является машиной Тьюринга общего вида.
Конечные автоматы.
Это пятёрка следующих объектов:
KA = <Q, ∑, б, q0, F>, где:
Q – множество состояний автомата.
∑ – множество символов алфавита языка
б – отображение множества состояний терминалов символов в множество состояний, которое записывается в виде таблицы перехода: б – Q x ∑ Q.
q0 – множество начальных состояний автомата.
F –множество конечных состояний автомата.
|
∑ \ Q |
|
… |
|
|
|
|
|
|
|
… |
|
… |
|
|
|
|
|
|
Допускающие обрыв цепочки.
Отвергающие обрыв цепочки.
Под последней строкой ставится признак каждого состояния, допускаемый или отвергаемый обрыв цепочки.
|
z \ |
S |
A |
F |
|
|
A…Z |
A |
A |
|
|
|
0…9 |
|
A |
|
|
|
; |
|
F |
|
|
|
|
|
0 |
0 |
1 |
Если на пересечении строки и столбца таблицы перехода множество состояний, а не одно состояние, такой автомат недетерминированный.
|
∑ \ Q |
|
… |
|
|
|
|
|
|
|
… |
|
… |
|
|
|
|
|
|
Эквивалентные преобразования недетерминированных автоматов в детерминированные и ДА в НДА.
Автоматы являются эквивалентными, если они допускают одинаковое множество цепочек. Для любого недетерминированного автомата существует эквивалентный ему детерминированный.
|
∑ \ Q |
A |
B |
C |
|
0 |
A,B |
B |
|
|
1 |
C |
C |
A,C |
|
|
0 |
1 |
1 |
|
∑ \ Q |
{A,B} |
{C} |
{A,C} |
|
0 |
{A,B} |
|
{A,B} |
|
1 |
{C} |
{A,C} |
{A,C} |
|
|
1 |
1 |
1 |
Такие дела.
Описание алгоритма преобразования НДА в ДА:
В соответствии с множеством начальных состояний НДА, в ДА формируется новое имя, в которое включаются исходные имена НДА.
В соответствии с новым состоянием ДА по таблице НДА для любого символа алфавита формируются новые имена, включаемые на пересечении строк и столбцов.
Для любого символа алфавита записываем состояния на пересечении строк и столбцов ДА.
Для вновь появившихся имён состояний добавляются столбцы в ДА, для каждого из которых выполняется пункт 2.
Состояние ДА = 1, если хотя бы 1 из имён состояний НДА имел признак 1.
28 сентября 2013 г.
Практика №2.
Построить контекстно-свободную (КС) и автоматную грамматику с графом состояний цепочек, состоящих из одного или нескольких идущих без разделения блоков. Каждый блок начинается с одной буквы и содержит в качестве продолжения от 1 до 3 цифр.
Решение:
Контекстно-свободная грамматика:
S XY|XYS
X a|…|z
Y C|CC|CCC, C 0|…|9
Автоматная грамматика (терминальный символ, либо терминальный символ и состояние):
S aA|…|zA
A 0B|…|9B|0S|…|9S|0|…|9
B 0Z|…|9Z|0S|…|9S|0|…|9
Z 0|…|9|0S|…|9S
F
a…z
a…z
S A: 0…9
S
A
B
Z
a…z
a…z
a…z
Граф состояний:
a…z
a…z
Построить КС-грамматику, детерминированную автоматную грамматику и граф состояний языка индексов Фортрана. Идентификатор начинается с буквы и включает произвольное число букв и цифр. Константа включает произвольное число цифр.
Условие индексов:
(I) (I+K)
(K) (I+K)
(K*I)(K*I+K)(K*I-K)
Решение:
Контекстно-свободная грамматика:
S (I)|(K)|(I+K)|(I-K)|(K*I+K)|(K*I-K)
I V|VG
G V|C|VG|CG
K C|CK
C 0|…|9
V a|…|z
Граф состояний:
S
A
B
D
F
F
C
E
a…z
a…z|0…9
Построить граф состояний языка цепочек (см. предыдущее занятие). Написать программу синтаксического анализа языка цепочек. В качестве семантики подсчитать число букв «X», «Y», «Z».
Решение:
Граф состояний.
S
X
Y
Z
F
x
y
z
j
x
y
z
Анализатор:
enum State {S, X, Y, Z, F, E}
string str;
char sc;
int i;
intix,iy,iz;
// ввод строки
Ix = 0; iy = 0; iz = 0;
State sta = State.S;
int len = str.length;
i = 0;
while (sta != State.E && sta != State.F && pos < len)
{ sc = str[i]; i++;
Switch (sta)
{ case State.S
{if (sc == ‘x’)
{sta = State.X; ix++;}
else {sta = State.E}
break; } // вывод сообщения
case State.X
{if (sc == ‘y’)
{sta = State.Y; iy++;}
else if (sc == ‘x’) ix==;}
else{sta=state.E;} // ошибка: допустимы толькоXиY.
case State.Y
{if (sc == ‘z’)
{sta = State.Z; iz++;}
else if (sc == ‘y’) iy==;}
else {sta = state.E;}
break;
case State.Z
{if (sc == ‘z’)
{iz++;}
else if (sc == ‘y’)
{sta=state.E;}
// вывод сообщения, вывод ix,iy,iz.