Конечные автоматы и реализация распознавателей на их основе

К основной странице курса

Основные определения

• Иерархия грамматик Хомского
• Автоматная (регулярная) грамматика
• Конечный автомат

Тема 1. Конечные автоматы и реализация распознавателей на их основе

Правая автоматная грамматика для целого со знаком

Beg -> +A | -A | цB
A -> цB
B -> цB | ε

Граф автоматной грамматики для целого со знаком

Регулярное выражение для целого со знаком

(+|-|)ц+

Программа 1 с таблицей переходов

// Реализация конечного автомата таблицей

// Состояния:
// S       - начальное состояние
// A       - после знака
// B       - после цифры
// Fin     - конечное состояние
// Err     - состояние ошибки

// Символы:
// Digit   - встречена цифра
// Sign    - встречен знак
// Eot     - встречен конец текста
// Unknown - встречен неизвестный символ
 
type
  States = (S,A,B,Fin,Err);
  KindCh = (Digit, Sign, Eot, Unknown);
 
function Kind(ch: char): KindCh;
begin
  case ch of
'0'..'9':   Result := Digit;
'+','-':    Result := Sign;
#13,#10:    Result := Eot;
  else   Result := Unknown; 
  end;
end;  
 
var P: array [Beg..B,Digit..Unknown] of States :=
  ((B, A, Err, Err),
   (B, Err, Err, Err),
   (B, Err, Fin, Err));
 
procedure error();
begin
  writeln('error');
  halt;
end;
 
var 
  ch: Char;
  State: States := Beg;
begin
  write('Введите целое со знаком: ');
  read(ch);
  writeln('Состояния:');
  while (State<>Fin) and (State<>Err) do
  begin
    writeln(State);
    State := P[State,Kind(ch)];
    read(ch);
  end;
  writeln(State);
end.

Граф автоматной грамматики идентификаторов

Задания к теме 1 «Конечные автоматы и реализация распознавателей на их основе»

Общее

1. Реализовать программу 1. Проверить, верно ли она распознает целое без знака. Если верно, формировать соответствующее целое со знаком.
2. Назвать состояния ошибок Err1, Err2 и т.д. В зависимости от типа ошибки выдавать диагностику. Предусмотреть диагностики вида: "Неверный символ", "Знак + не может содержаться внутри целого", "После целого не может быть других символов"
3. Выдавать место ошибки в виде

+123+
    ^

1. В программе 1 попытаться восстановиться после ошибки, возвращаясь в предыдущее состояние и выводя предупреждение с местом ошибки и неверным символом

Индивидуальные задания

1. Нарисовать граф автоматной грамматики для целого со знаком, начинающегося не с цифры 0. Реализовать конечный автомат. Оттестировать.
2. Нарисовать граф автоматной грамматики для чередующихся букв и цифр. Реализовать конечный автомат. Оттестировать.
3. Нарисовать граф автоматной грамматики для списка букв, разделенных символом , или ;. Реализовать конечный автомат. Оттестировать.
4. Нарисовать граф автоматной грамматики для списка цифр, разделенных одним или несколькими пробелами. Реализовать конечный автомат. Оттестировать.
5. Нарисовать граф автоматной грамматики для выражения вида 1+2-3-4+5. Реализовать конечный автомат. Оттестировать.
6. Нарисовать граф автоматной грамматики для вещественного с десятичной точкой 123.45678. Реализовать конечный автомат. Оттестировать.
7. Составить таблицу конечного автомата для распознавания идентификаторов. Проверить работу программы в случае правильного и неправильного ввода. Выводить разную диагностику в зависимости от типа ошибки.