Автомат

[mastedm]

Автомат задан набором $(\{a,b\},\{q_1,q_2,q_3,q_4,q_5\}, Q_s, Q_f)$, где $\{a,b\}$ - алфавит, $Q_s=\{q_2\}$ - начальные состояния, $Q_f=\{q_3, q_4\}$ - множество конечных состояний. Запись $(i,j,a,b)$ означает, что дуга $(i,j)$, идущая из $q_i$ в $q_j$ имеет метки $a,b$:

$$ (1,2,a), (1,5,b), (2,5,b), (2,4,a), (3,2,a,b), (4,3,b), (5,4,a) $$

1. Построить граф автомата и найти язык L, допускаемый автоматом
2. Детерминизировать автомат

Граф получился такой:


В $q_1$ мы вообще не попадаем.

С поиском языка голову сломал. У кого-нить есть соображения по этому поводу?

[Профессор Снэйп]

Ну а с чем тут могут быть проблемы? Проще конечных автоматов, по моему, вообще ничего не бывает.

Вам язык в каком виде надо найти: в виде регулярного выражения или в каком-то другом?

[mastedm]

В виде регулярного выражения

[незваный гость]

mastedm писал(а):

С поиском языка голову сломал. У кого-нить есть соображения по этому поводу?

Попробуйте порисовать примеры.

Для простоты $q_1$ проще всего стереть, чтобы не мешался.

Как первый шаг, удобно посмотреть язык, порождаемый автоматом со временно стёртой дугой $q_3 \to q_2$.

[Профессор Снэйп]

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

Хотя для этого автомата никаких алгоритмов не нужно: всё и так видно невооружённым глазом. Состояние $q_1$ действительно лишнее: оно недостижимо и можете смело выкинуть его с диаграммы. Остаётся цикл (правда, один раз ветвящийся в состоянии $q_2$, но там ветвимость тоже очень простая). Как автомат может распознать слово? Очевидно, единственная возможность для этого --- из начального состояния $q_2$ пройти цикл ноль или более раз, а затем, покинув последний раз $q_2$, прийти в одно из конечных состояний: $q_3$ или $q_4$.

Исходя из этих соображений регулярное выражение выписывается очевидным образом:

$$ \big( (a \cup ba)b(a \cup b) \big)^\ast (a \cup ba)(\varnothing^\ast \cup b) $$

Добавлено спустя 2 минуты 14 секунд:

незваный гость писал(а):

Как первый шаг, удобно посмотреть язык, порождаемый автоматом со временно стёртой дугой $q_3 \to q_2$.

Боже, ну что там упрощать? В детский сад что ли играем?

to mastedm: Когда разберётесь с этим, хотите, я Вам действительно сложный автомат подкину?

[mastedm]

Понял. У меня собственно проблема была с переходом $q_3 \to q_4$ - не знал как его обыграть. Приблизительно такое же выражение у меня получалось, но я думал, что может как-то проще записать можно.

По поводу соответствия автомата регулярному выражению я знаю. Опять таки хотелось что-то простое по записи получить.

Сейчас займусь детерминизацией.

[незваный гость]

Профессор Снэйп писал(а):

Боже, ну что там упрощать? В детский сад что ли играем?

Пфуй... Нет, не в детский сад. Поверите или нет, но я составил регулярное выражение. Но вопрос в том, что mastedm только учится его составлять. Нормальный способ изучения — это делать работу по шагам. И, кстати, это нормальный практический способ построения рег. выражения. То, что Вы написали решение и ответ — неочевидное для меня действие. И, кстати, зачем там * в последнем члене (при $\Lambda$)?

Профессор Снэйп писал(а):

to mastedm: Когда разберётесь с этим, хотите, я Вам действительно сложный автомат подкину?

Я хоть и не mastedm, но хочу!

[Профессор Снэйп]

незваный гость писал(а):

И, кстати, зачем там * в последнем члене (при $\Lambda$)?

Там не $\Lambda$, а $\varnothing$

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

Символ $\varnothing$ обозначает пустой язык (то есть язык, не содержащий ни одного слова). Навешивание на этот язык звёздочки Клини как раз и даёт язык, состоящий из пустого слова.

незваный гость писал(а):

Профессор Снэйп писал(а):

to mastedm: Когда разберётесь с этим, хотите, я Вам действительно сложный автомат подкину?

Я хоть и не mastedm, но хочу!

Ну... боюсь, она Вам такой уж сложной не покажется. Впрочем, автомат такой:

Три состояния: $q_1$, $q_2$ и $q_3$. Состояние $q_1$ начальное, оно же заодно и конечное. Других конечных состояний нет. Алфавит состоит из символов $a$ и $b$. Всего в автомате 3 $a$-перехода: из $q_1$ в $q_2$, из $q_2$ в $q_3$ и из $q_3$ в $q_1$ и 3 $b$-перехода: из $q_1$ в $q_3$, из $q_3$ в $q_2$ и из $q_2$ в $q_1$.

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

Кстати, я как-то недавно постил уже здесь на форуме гораздо более интересную задачу, касающуюся конечных автоматов. Вот ссылка: http://dxdy.ru/viewtopic.php?t=10741 Боюсь, что тогда на неё просто никто внимания не обратил (ну или не захотел писать известное ему решение).

[mastedm]

$$ (aaa|bbb)^* $$

[Профессор Снэйп]

mastedm писал(а):

$$ (aaa|bbb)^* $$

Вертикальной чёрточкой Вы, наверное, объединение обозначаете? Я с теорией автоматов по книге Пападимитроу когда-то знакомился, он чёрточек не пишет.

Если чёрточка --- это объединение, то тогда, конечно, неправильно. Вот, например, слово $ab$. Автомат его распознает. А как оно из Вашего выражения вытаскивается? Похоже, что никак.

[Someone]

Профессор Снэйп писал(а):

незваный гость писал(а):

И, кстати, зачем там * в последнем члене (при $\Lambda$)?

Там не $\Lambda$, а $\varnothing$

Символ $\varnothing$ обозначает пустой язык (то есть язык, не содержащий ни одного слова).

Не знаю насчёт языков, но символ $\Lambda$ часто используется для обозначения пустого множества. Во всяком случае, я к такому обозначению сильно привык.

[mastedm]

Мда, что-то я поспешил

[Профессор Снэйп]

Someone писал(а):

Не знаю насчёт языков, но символ $\Lambda$ часто используется для обозначения пустого множества. Во всяком случае, я к такому обозначению сильно привык.

Всё-таки $\varnothing$ для пустого множества более употребительно.

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

[mastedm]

Я правильно понимаю, что исходной автомат уже детерминированный? Единственно только можно убрать состояние $q_1$.

[Профессор Снэйп]

mastedm писал(а):

Я правильно понимаю, что исходной автомат уже детерминированный? Единственно только можно убрать состояние $q_1$.

Исходный --- это вы про свой?

Если про свой, заданный в первом сообщении темы, то нет, конечно, он не детерминированный. Из состояния $q_5$ не выходит стрелки, помеченной символом $b$, а из состояния $q_4$ --- стрелки, помеченной символом $a$. Между тем на диаграмме детерминированного автомата из каждого состояния должно выходить столько стрелок, сколько всего символов в алфавите, ровно по одной стрелке на каждый символ.

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