2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Автомат
Сообщение23.01.2008, 21:46 
Аватара пользователя


13/01/08
22
Москва
Автомат задан набором $(\{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$ мы вообще не попадаем.

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

 Профиль  
                  
 
 
Сообщение23.01.2008, 21:51 
Заморожен
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение23.01.2008, 21:54 
Аватара пользователя


13/01/08
22
Москва
В виде регулярного выражения

 Профиль  
                  
 
 
Сообщение23.01.2008, 22:02 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
mastedm писал(а):
С поиском языка голову сломал. У кого-нить есть соображения по этому поводу?

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

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

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

 Профиль  
                  
 
 
Сообщение23.01.2008, 22:08 
Заморожен
Аватара пользователя


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

Хотя для этого автомата никаких алгоритмов не нужно: всё и так видно невооружённым глазом. Состояние $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: Когда разберётесь с этим, хотите, я Вам действительно сложный автомат подкину? :D

 Профиль  
                  
 
 
Сообщение23.01.2008, 22:29 
Аватара пользователя


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

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

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

 Профиль  
                  
 
 
Сообщение23.01.2008, 22:40 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Профессор Снэйп писал(а):
Боже, ну что там упрощать? В детский сад что ли играем?

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

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

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

 Профиль  
                  
 
 
Сообщение23.01.2008, 23:18 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
незваный гость писал(а):
И, кстати, зачем там * в последнем члене (при $\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 Боюсь, что тогда на неё просто никто внимания не обратил (ну или не захотел писать известное ему решение).

 Профиль  
                  
 
 
Сообщение23.01.2008, 23:26 
Аватара пользователя


13/01/08
22
Москва
$$
(aaa|bbb)^*
$$

 Профиль  
                  
 
 
Сообщение23.01.2008, 23:30 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
mastedm писал(а):
$$
(aaa|bbb)^*
$$


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

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

 Профиль  
                  
 
 
Сообщение23.01.2008, 23:30 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Профессор Снэйп писал(а):
незваный гость писал(а):
И, кстати, зачем там * в последнем члене (при $\Lambda$)?


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

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


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

 Профиль  
                  
 
 
Сообщение23.01.2008, 23:34 
Аватара пользователя


13/01/08
22
Москва
Мда, что-то я поспешил

 Профиль  
                  
 
 
Сообщение23.01.2008, 23:35 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Someone писал(а):
Не знаю насчёт языков, но символ $\Lambda$ часто используется для обозначения пустого множества. Во всяком случае, я к такому обозначению сильно привык.


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

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

 Профиль  
                  
 
 
Сообщение24.01.2008, 22:53 
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение25.01.2008, 10:10 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
mastedm писал(а):
Я правильно понимаю, что исходной автомат уже детерминированный? Единственно только можно убрать состояние $q_1$.


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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 36 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group