Задача 1: С помощью алгоритма минимизации ДКА докажите, что ДКА КМП A_{w} для любого слова w ∈ T^{∗} является минимальным полным ДКА для языка Suff(w) = T^{∗}w всех слов, оканчивающихся на w. T = {a,b}.

Задача 2: Пусть дан регулярный язык L над алфавитом T = {a,b} и минимальный полный ДКА A, распознающий этот язык.

  1. Докажите, что если при прочтении двух слов x,y ∈ T^{∗} автоматом A автомат оказывается в одном и том же состоянии u, то x ∼L y.
  2. Докажите, что если два слова x,y ∈ T^{∗} L-эквивалентны, то при их прочтении автоматом A он окажется в одном и том же состоянии.
  3. Используя результаты Задачи 1, опишите классы эквивалентности Майхилла-Нероуда для языка Suff(w). Описание не должно использовать состояния автомата (т.е. надо именно описать классы, а не ссылаться на факт, что классы М.-Н. - это правые или левые языки состояний минимального полного ДКА)

задан 11 Окт 23:19

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×194
×86
×34

задан
11 Окт 23:19

показан
61 раз

обновлен
11 Окт 23:19

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru