Механизмы распознавания языков

Определение распознавателя

Обратной к задаче генерации строк языка является задача проверки принадлежности исходной строки заданному языку. Для решения этой проблемы создается механизм распознавания, или распознаватель.

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

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

Схема работы распознавателя

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

Входная головка в каждый момент обозревает одну ячейку. За один шаг работы распознавателя головка сдвигается на одну ячейку влево (вправо) или остается неподвижной. Распознаватель, не перемещающий входную головку влево, называется односторонним.

Управляющее устройство – это программа управления распознавателем. Она задает конечное множество состояний распознавателя и определяет переходы из состояния в состояние в зависимости от прочитанного символа входной ленты и содержимого вспомогательной памяти.

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

а₁а₂ … а_n Входная лента

Рисунок 1.4 – Схема распознавателя

Поведение распознавателя можно представить с помощью его конфигураций.

Определение Конфигурация распознавателя есть совокупность следующих элементов:

- состояние управляющего устройства;

- содержимое входной ленты и положение входной головки;

- содержимое вспомогательной памяти.

Определение Управляющее устройство называется детерминированным, если для каждой конфигурации распознавателя существует не более одного возможного следующего шага, в противном случае управляющее устройство называется недетерминированным.

Определение Конфигурация распознавателя называется начальной, если управляющее устройство находится в заданном начальном состоянии, входная головка обозревает самый левый символ на входной ленте и вспомогательная память имеет заранее установленное начальное состояние.

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

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

Определение Множество всех строк, допускаемых распознавателем, называется языком распознавателя.

Классификация распознавателей

Для каждого класса грамматик из иерархии Хомского существует класс распознавателей, определяющих тот же класс языков. Чем шире класс грамматик, тем сложнее класс соответствующих распознавателей.

Для языков типа 0 распознавателями являются машины Тьюринга.

Распознаватели КЗ-языков называются линейными ограниченными автоматами (машины Тьюринга с конечным объемом ленты).

Распознавателями для КС-языков являются автоматы с магазинной памятью.

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

Регулярные грамматики и языки

Регулярные выражения

Регулярный язык L в некотором алфавите V представляет собой регулярное множество строк.

Определение Регулярное множество есть Æ, либо {e}, либо {а} для некоторого а Î V, либо множество, которое можно получить из указанных множеств путем применения конечного числа операций сцепления, объединения и итерации.

В основе метода определения регулярности заданного языка лежит лемма о разрастании языка.

Лемма о разрастании языка

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

Пример Язык L₁ = {a^mbⁿ| m, n ³ 0} – регулярный, т.к., например, в строке aabbb повторение любой подстроки, образованной только из нулей или единиц, порождает строки (aaaabbb, aaabbb, aabbbb, aabbbbbb и т.д.) языка L₁.

Язык L₂ = {aⁿbⁿ| n ³ 1} – не регулярный, т.к. Действительно, любая итерация подстроки, состоящей только из нулей или единиц, нарушает баланс нулей и единиц. Подобные действия со смешанными подстроками, содержащими нули и единицы, приводят к нарушению порядка следования нулей и единиц. Таким образом, для языка L₂не строк, удовлетворяющих условиям леммы.

Удобным средством формального определения регулярных языков являются регулярные выражения.

Определение Регулярные выражения над алфавитом S определяются следующим образом:

1) Æ - регулярное выражение (обозначает пустоте регулярное множество Æ );

2) e - регулярное выражение (обозначает регулярное множество {e}, состоящее из пустой строки);

3) а Î S - регулярное выражение (обозначает множество {а});

4) если p и q – регулярные выражения, обозначающие множества P и Q, то посредством операций над выражениями определяются выражения следующих трех типов:

а) p|q или p+q – регулярное выражение (обозначает объединение PÈ Q), где символ | или + называют операцией или (альтернативы);

б) pq или p× q – регулярное выражение (обозначает множество PQ = {xy | x Î P, y Î Q}), где символ «точка» (возможно умалчиваемый) называют операцией сцепления (конкатенации);

в) p^* - регулярное выражение (обозначает множество P^*), где символ «*» называют операцией итерации.

Соотношение между регулярными языками и регулярными выражениями устанавливает теорема Клини.

Теорема Клини. Каждому регулярному языку из S^* соответствует регулярное выражение над множеством S.

Пример Примеры регулярных выражений и их значений представлены в таблице 2.1.

Таблица 2.1 – Примеры регулярных выражений

Регулярное выражение	Значение регулярного выражения
	единственная строка 01
0\|1	две строки: 0 и 1
1^*	строки, образованные из единиц, включая пустую строку
(0\|1)^*	строки, образованные из символов 0 и 1, включая пустую строку
0\|1^*	строки, состоящие из нуля и любой строки единиц, включая пустую
0\|1^*	строки, состоящие из нуля и любой строки единиц, включая пустую
(0\|1)^*011	строки, образованные из символов 0 и 1, включая пустую, обязательно оканчивающиеся строкой 011

В практических приложениях вводятся дополнительные соглашения относительно записи регулярных выражений, например, запись вида р⁺ используется для обозначения выражения рр^*.

Конечные автоматы

⇐ Предыдущая 1 234 5 6 7 8 9 10 Следующая ⇒