Конечные автоматы и реализация распознавателей на их основе — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Admin (обсуждение | вклад) (→Задания к теме 1 «Конечные автоматы и реализация распознавателей на их основе».) |
Admin (обсуждение | вклад) (→Основные определения) |
||
Строка 3: | Строка 3: | ||
===Основные определения=== | ===Основные определения=== | ||
*[http://ru.wikipedia.org/wiki/%D0%98%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D1%8F_%D0%A5%D0%BE%D0%BC%D1%81%D0%BA%D0%BE%D0%B3%D0%BE Иерархия грамматик Хомского] | *[http://ru.wikipedia.org/wiki/%D0%98%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D1%8F_%D0%A5%D0%BE%D0%BC%D1%81%D0%BA%D0%BE%D0%B3%D0%BE Иерархия грамматик Хомского] | ||
− | *[http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8 Автоматная грамматика] | + | *[http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8 Автоматная (регулярная) грамматика] |
*[http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 Конечный автомат] | *[http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 Конечный автомат] | ||
Версия 20:54, 13 февраля 2013
Содержание
- 1 Основные определения
- 2 Тема 1. Конечные автоматы и реализация распознавателей на их основе
- 2.1 Автоматная грамматика для целого со знаком
- 2.2 Граф автоматной грамматики для целого со знаком
- 2.3 Регулярное выражение для целого со знаком
- 2.4 Программа 1 с таблицей переходов
- 2.5 Граф автоматной грамматики идентификаторов
- 2.6 Задания к теме 1 «Конечные автоматы и реализация распознавателей на их основе»
Основные определения
Тема 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. Проверить, верно ли она распознает целое без знака. Если верно, формировать соответствующее целое со знаком.Сделать все варианты ошибок.
- Назвать состояния ошибок Err1, Err2 и т.д. В зависимости от типа ошибки выдавать диагностику. Предусмотреть диагностики вида: "Неверный символ", "Знак + не может содержаться внутри целого", "После целого не может быть других символов"
- Составить таблицу конечного автомата для распознавания идентификаторов. Проверить работу программы в случае правильного и неправильного ввода. Выводить разную диагностику в зависимости от типа ошибки.
- Нарисовать граф автоматной грамматики для целого со знаком, начинающегося не с цифры 0. Реализовать конечный автомат. Оттестировать.
- Нарисовать граф автоматной грамматики для чередующихся букв и цифр. Реализовать конечный автомат. Оттестировать.
- Нарисовать граф автоматной грамматики для списка букв, разделенных символом , или ;. Реализовать конечный автомат. Оттестировать.
- Нарисовать граф автоматной грамматики для списка цифр, разделенных одним или несколькими пробелами. Реализовать конечный автомат. Оттестировать.
- Нарисовать граф автоматной грамматики для выражения вида 1+2-3-4+5. Реализовать конечный автомат. Оттестировать.
- Нарисовать граф автоматной грамматики для вещественного с десятичной точкой 123.45678. Реализовать конечный автомат. Оттестировать.
- В программе 1 попытаться восстановиться после ошибки, возвращаясь в предыдущее состояние и выводя предупреждение с местом ошибки и неверным символом