Конечные автоматы – распознаватели

Распознаватели

Поиск образцов в тексте

РВ являются основным средством приложений для поиска образцов, шаблонов в тексте. Они задают «схему» образца поиска. С помощью РВ можно не прилагая больших усилий, описывать такие образцы и быстро менять такие описания, если результат не устраивает.

РВ компилируются в ДКА или НКА, которые затем моделируются для получения программы распознавания образов в тексте.

Пример 1.

Зададим шаблон (образец) для распознавания названий улиц поисковой системой при просмотре сайтов.

Название улицы может начинаться с «улица», «ул.», «проспект», «пр.», «переулок», «пер.».

улица | ул\. | проспект | пр\. | переулок | пер\.

Затем идет название улицы. Оно начинается с прописной буквы и затем идет несколько строчных.

[А-Я][а-я]*

Название улицы может состоять из нескольких слов с заглавной буквы (например, ул. Карла Маркса)

[А-Я][а-я]*([А-Я][а-я]*)*

Итоговое выражение

(улица| ул\.|проспект|пр\.|переулок|пер\.) [А-Я][а-я]*([А-Я][а-я]*)*

Таким образом, распознавание адресов на web-страницах с помощью компилятора РВ намного проще по сравнению с программой на традиционном языке программирования.

Написать РВ для поиска сотовых и 6-значных городских телефонных номеров.

Ранее мы рассмотрели задание языков через механизм порождения, с помощью грамматики. Теперь рассмотрим второй основной подход задания языков – через механизм распознавания.

Распознаватель, по сути, является процедурой специального вида, которая по заданной цепочке определяет, принадлежит ли она языку. Если принадлежит, то процедура останавливается с ответом «да», т. е. допускает цепочку; иначе – останавливается с ответом «нет» или зацикливается. Язык, определяемый распознавателем – это множество всех цепочек, которые он допускает.

Определение. Распознавателем языка называется алгоритм или физическое устройство, которое по произвольной цепочке определяет, принадлежит ли она данному языку или нет.

Начнем с распознавателя регулярных языков – конечного автомата.

Определение. Детерминированным конечным автоматом – распознавателем называется устройство или алгоритм А = (Q, S, d, q₀, F), где Q – непустое конечное множество состояний, S – конечный входной алфавит, q₀ Î Q – начальное состояние, d - функция переходов, F Î Q – множество заключительных состояний.

На автомат можно смотреть как на физическое устройство, состоящее из устройства управления и входной ленты, которая разделена на ячейки и в них записаны символы. В каждый момент времени УУ находится в некотором состоянии и видит одну ячейку ленты. УУ считывает символ, определяет новое состояние, переходит в него и сдвигается вправо. Такт работы состоит в переходе из текущего состояния при текущем входном символе в следующее состояние.

Определение. Автомат распознает (допускает) цепочку, если по окончании цепочки перейдет в одно из заключительных состояний. Распознаваемым языком называется множество всех цепочек, распознаваемых этим автоматом.

Задание распознающего КА

1) расширенная таблица переходов

2) диаграмма переходов

Расширенная таблица переходов – таблица значений функции переходов d, первая строка которой соответствует начальному состоянию, а заключительные состояния помечены единицей в дополнительном столбце.

Диаграммой переходов называется ориентированный граф, вершины которого – состояния автомата, а дуги помечены элементами алфавита.

Начальное состояние помечено двойным кружком, а конечные состояния помечены жирными кружками.

Дата добавления: 2015-05-26