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

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

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

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

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

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

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

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

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

(+|-|)ц+

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

// Реализация конечного автомата таблицей
// Beg     - начальное состояние
// A       - после знака
// B       - после цифры
// En      - конечное состояние
// Err     - состояние ошибки
// Digit   - встречена цифра
// Sign    - встречен знак
// Eot     - встречен конец текста
// Unknown - встречен неизвестный символ

type
  States = (Beg,A,B,En,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, En, Err));

procedure error();
begin
  writeln('error');
  halt;
end;

var 
  ch: Char;
  State: States := Beg;
begin
  read(ch);
  while (State<>En) 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. Составить таблицу конечного автомата для распознавания идентификаторов. Проверить работу программы в случае правильного и неправильного ввода. Выводить разную диагностику в зависимости от типа ошибки.
4. Нарисовать граф автоматной грамматики для целого со знаком, начинающегося не с цифры 0. Реализовать конечный автомат. Оттестировать.
5. Нарисовать граф автоматной грамматики для чередующихся букв и цифр. Реализовать конечный автомат. Оттестировать.
6. Нарисовать граф автоматной грамматики для списка букв, разделенных символом , или ;. Реализовать конечный автомат. Оттестировать.
7. Нарисовать граф автоматной грамматики для списка цифр, разделенных одним или несколькими пробелами. Реализовать конечный автомат. Оттестировать.
8. Нарисовать граф автоматной грамматики для выражения вида 1+2-3-4+5. Реализовать конечный автомат. Оттестировать.
9. Нарисовать граф автоматной грамматики для вещественного с десятичной точкой 123.45678. Реализовать конечный автомат. Оттестировать.
10. В программе 1 попытаться восстановиться после ошибки, возвращаясь в предыдущее состояние и выводя предупреждение с местом ошибки и неверным символом