Разрешимые алгоритмические проблемы, связанные с автоматными языками

1) Проблема принадлежности:

Дано описание языка L и цепочка a. Принадлежит ли цепочка a языку L. Существует алгоритм, который за конечное количество шагов решает эту проблему.

Дано: А – автомат, a – цепочка.

Выход: «Да», если aÎL(A). «Нет», если aÏL(A).

Метод решения: распишем цепочку a посимвольно: a= a₁a₂…a_n.

Обозначим z₁= t(z₀, a₁), z₂= t(z₁, a₂), …, z_n= t(z_n-1, a_n).

Если z_nÎF (где F – множество заключительных состояний), то цепочка a принадлежит языку L. В противном случае – нет.

2) Проблема пустоты: Дано определение языка. Пустой ли этот язык.

Дано: конечный автомат А.

Выход: «Пустой» или «Непустой» язык L(A).

Метод: Найти множество состояний, достижимых из начального состояния. Если это множество содержит какое-либо заключительное состояние, то ответ «Да», иначе – «Нет». Множество достижимых состояний находят перебором всех возможных путей в графе автомата.

3) Проблема эквивалентности: Даны два определения языка. Определить, описывают ли они один и тот же язык.

Дано: 2 конечных автомата А₁= (X₁, Z₁, t₁, z₀¹, F₁) и А₂= (X₂, Z₂, t₂, z₀², F₂).

Предполагаем, что множества состояний этих автоматов не пересекаются: Z₁ÇZ₂= Æ.

Выход: «Да» – если L(A₁) = L(A₂), «Нет» – если L(A₁) ¹ L(A₂).

Метод: построим объединенный автомат А: (X₁ È X₂, Z₁ È Z₂, t₁ È t₂, z₀, F₁ È F₂).

Определим, различимы ли конечные состояния данного автомата. Если они различимы, то «Нет», иначе – «Да».

Вопросы и упражнения

1. Почему данные проблемы называют алгоритмическими?

2. Как доказывается, что они разрешимы?