2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Построение регулярного выражения по данному ДКА.
Сообщение10.11.2013, 00:14 


24/03/11
64
Предисловие: Изучаю алгоритм построения РВ по ДКА, изложенный в книге Хопкрофта. Не уверен, что правильно его понял. Прошу вашей помощи.

Есть данный ДКА

$\begin{tabular}{c|c|c}
\hline
& 0 & 1 \\
\hline
\to *  p & s & p \\
\hline
q & p & s \\
\hline
r & r & q \\
\hline
s & q & r \\
\end{tabular}$

нужно получить соответствующее РВ, пользуясь методом исключения состояний. Вроде сначала всё идёт хорошо, но когда остаётся два состояния, путаюсь с тем, что надо делать. Подскажите пожалуйста!

Шаг 1:
Исключаю состояние $s$

$\begin{tabular}{c|c|c|c|c}
\hline
& 0 & 1 & 01 & 11 \\
\hline
\to *  p & \varnothing & p & \{q, r\} & \varnothing \\
\hline
q & p & \varnothing & \varnothing & \{q, r\} \\
\hline
r & r & q & \varnothing & \varnothing \\
\end{tabular}$

Шаг 2:
Исключаю состояние $q$
(Проверьте, правильно ли я всё делаю на шаге 1-2, особенно интересуют новые переходы из $p$ в $p$)

$\begin{tabular}{c|c|c|c|c}
\hline
& 1+01(11)^*0 & 01+01(11)^*11 & 1(11)^*0 & 0+1(11)^*11 \\
\hline
\to *  p & p & r & \varnothing & \varnothing \\
\hline
r & \varnothing & \varnothing & p & r \\
\end{tabular}$

Можно ли далее с двумя оставшимися состояниями поступать также, как и на шаге 1-2?

 Профиль  
                  
 
 Posted automatically
Сообщение10.11.2013, 10:50 
Супермодератор
Аватара пользователя


20/11/12
5728
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

Edmonton
Наберите все формулы и термы $\TeX$ом и таблицу тоже. Я понимаю, что у Вас в основном картинки, но постарайтесь максимально разгрузить текст темы от картинок, сами автоматы можно и кодом записать, регулярные выражения - только $\TeX$ом Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
вернул

 Профиль  
                  
 
 Re: Построение регулярного выражения по данному ДКА.
Сообщение10.11.2013, 11:22 
Заслуженный участник


08/04/08
8556
Не знаю, зачем Вы стерли регулярки, ну да ладно.
Также мне не очень понятно, почему Вы начали исключать вершину $s$ с 4-я дугами, а не вершину $r$, у которой 2 дуги и одна петля, ну да ладно.
Я построил графы, исходный и полученный Вами на шаге 1. Решительно не понимаю, откуда Вы взяли такой результат шага 1. Ячейка $q\xrightarrow{11}\{q,r\}$ ведь обозначает, что из $q$ в $q$ и в $r$ ведет дуга с меткой $11$? И откуда она у Вас взялась? В исходном графе есть только пусть $q\xrightarrow{1}s\xrightarrow{0}q$. Может опечатка?

Edmonton в сообщении #786871 писал(а):
Изучаю алгоритм построения РВ по ДКА, изложенный в книге Хопкрофта. Не уверен, что правильно его понял.
Если я сам правильно помню :-), то смысл следующий: у Вас есть граф ДКА, Вы его хотите упростить, уменьшая число вершин. Пусть мы хотим исключить вершину $s$. Вы ее исключаете, но дуги, ведущие в $s$ и из $s$ надо заменить эквивалентными дугами. Какие это дуги? Ясно, что если есть 2 дуги $x\xrightarrow{R_1} s\xrightarrow{R_2} y$ ($x,y$ здесь, есс-но, необязательно различны), и есть петля $s\xrightarrow{T} s$, то соответствующую тройку дуг мы должны заменить на дугу $x\xrightarrow{R_1(T)^{\ast}R_2} y$. Пробежавшись по всем тройкам дуг и исключив их, мы сможем исключить и саму вершину $s$. Вот и весь смысл.

Только Вы меня проверьте, могу наврать, а я еще сам себя тоже проверю...

upd: Проверил: так и есть, только афторы еще и меняют 2 разные дуги $x\xrightarrow{R} y$ и $x\xrightarrow{T} y$ на дугу $x\xrightarrow{R+T} y$. И есть большая и понятная картинка.

 Профиль  
                  
 
 Re: Построение регулярного выражения по данному ДКА.
Сообщение10.11.2013, 12:54 


24/03/11
64
Sonic86 в сообщении #786972 писал(а):
Я построил графы, исходный и полученный Вами на шаге 1. Решительно не понимаю, откуда Вы взяли такой результат шага 1. Ячейка $q\xrightarrow{11}\{q,r\}$ ведь обозначает, что из $q$ в $q$ и в $r$ ведет дуга с меткой $11$? И откуда она у Вас взялась? В исходном графе есть только пусть $q\xrightarrow{1}s\xrightarrow{0}q$. Может опечатка?


Абсолютно верно, в этом моменте ошибся по невнимательности. Тогда после шага 1 выходит

$\begin{tabular}{c|c|c|c|c|c|c}
\hline
& 0 & 1 & 00 & 01 & 10 & 11 \\
\hline
\to *  p & \varnothing & p & q & r & \varnothing & \varnothing \\
\hline
q & p & \varnothing & \varnothing & \varnothing & q & r \\
\hline
r & r & q & \varnothing & \varnothing & \varnothing & \varnothing \\
\end{tabular}$

Или вот

Изображение

Тогда шаг 2.

$\begin{tabular}{c|c|c|c|c}
\hline
& 1+00(10)^*0 & 01+00(10)^*11 & 1(10)^*0 & 0+1(10)^*11 \\
\hline
\to *  p & p & r & \varnothing & \varnothing \\
\hline
r & \varnothing & \varnothing & p & r \\
\end{tabular}$

Или

Изображение

Предположим, что во второй раз я не налажал на шагах 1-2. Тогда дальше я немного не понимаю, что делать. Ибо в учебнике разобран случай, когда начальное и конечное состояния отличаются, тут же оно у меня одно и то же - $p$. Как я понимаю, нужно из оставшегося автомата исключить состояние $q$, и получить переход из $p$ в $p$, помеченный некоторым регулярным выражением. Ответом же будет итерация этого самого РВ. Но я не уверен в правильности своих рассуждений.

 Профиль  
                  
 
 Re: Построение регулярного выражения по данному ДКА.
Сообщение10.11.2013, 13:04 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Edmonton в сообщении #787022 писал(а):
Как я понимаю, нужно из оставшегося автомата исключить состояние $q$, и получить переход из $p$ в $p$, помеченный некоторым регулярным выражением. Ответом же будет итерация этого самого РВ. Но я не уверен в правильности своих рассуждений.
Все так.

Можно исключать любые вершины, кроме начальной и конечной.Соответственно, в итоге получится либо автомат с одной вершиной (если в исходном начальная совпадала с конечной), либо с двумя.

 Профиль  
                  
 
 Re: Построение регулярного выражения по данному ДКА.
Сообщение10.11.2013, 13:07 
Заслуженный участник


08/04/08
8556
После шага 1 у меня получился такой же граф, что и у Вас.
Шаг 2 проверять лень :-)

Edmonton в сообщении #787022 писал(а):
Как я понимаю, нужно из оставшегося автомата исключить состояние $q$, и получить переход из $p$ в $p$, помеченный некоторым регулярным выражением. Ответом же будет итерация этого самого РВ. Но я не уверен в правильности своих рассуждений.
Да-да-да, все так.

 Профиль  
                  
 
 Re: Построение регулярного выражения по данному ДКА.
Сообщение10.11.2013, 13:23 


24/03/11
64
Xaositect
Sonic86
Большое спасибо!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

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



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

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


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

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