Множества правых контекстов

Определение 6.1.1.

Пусть

и . Тогда множество правых контекстов слова y относительно языка L определяется следующим образом:

Пример 6.1.2.

Пусть

и . Тогда

2. если , то ;
3. если , то ;
4. если , то .

Определение 6.1.3.

Для любого состояния p полного детерминированного конечного автомата

и любого слова w обозначим через

такое состояние q, что существует путь из p в q с меткой w (в силу полноты и детерминированности такое состояние существует и единственно).

Лемма 6.1.4.

Если язык L распознается полным детерминированным конечным автоматом , то

Доказательство. Пусть I = {s}. Введем обозначение

Определим функцию , положив f(A) равным , где y - некоторое слово, для которого выполнено условие

(если существует несколько таких слов y, то можно использовать, например, первое среди них в лексикографическом порядке).

Заметим, что для любых слов u и v, если , то . Следовательно, функция f является инъективной. Но тогда .

Пример 6.1.5.

Рассмотрим язык L, порождаемый полным детерминированным конечным автоматом

из примера 2.6.4. Тогда

Лемма 6.1.6.

Если

и множество

конечно, то язык L является автоматным.

Доказательство. Язык L распознается полным детерминированным конечным автоматом , где

Пример 6.1.7.

Пусть . Рассмотрим автоматный язык L = a+b*. Обозначим

Тогда . Язык L распознается полным детерминированным конечным автоматом , где , , ,

Теорема 6.1.8.

Язык

является автоматным тогда и только тогда, когда множество

конечно.

Доказательство. Необходимость доказана в лемме 6.1.4, достаточность - в лемме 6.1.6.

Замечание 6.1.9.

В силу леммы 6.1.4 полный детерминированный конечный автомат, построенный в доказательстве леммы 6.1.6, является минимальным (по количеству состояний) среди всех полных детерминированных конечных автоматов, распознающих заданный язык. Можно доказать, что любой минимальный полный детерминированный конечный автомат, распознающий заданный язык, изоморфен этому автомату.

Упражнение 6.1.10. Пусть

и

Сколько элементов содержит множество ?

Упражнение 6.1.11. Найти минимальный полный детерминированный конечный автомат для языка {ab,abb}*.

Упражнение 6.1.12. Найти минимальный полный детерминированный конечный автомат для языка

Упражнение 6.1.13. Найти минимальный полный детерминированный конечный автомат для языка

Упражнение 6.1.14. Найти минимальный полный детерминированный конечный автомат для языка

Содержание раздела

---

---