Построение регулярного выражения по данному ДКА.

[Edmonton]

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

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

$\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?

[Deggial]

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

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

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

[Sonic86]

Не знаю, зачем Вы стерли регулярки, ну да ладно.
Также мне не очень понятно, почему Вы начали исключать вершину $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$. И есть большая и понятная картинка.

[Edmonton]

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$, помеченный некоторым регулярным выражением. Ответом же будет итерация этого самого РВ. Но я не уверен в правильности своих рассуждений.

[Xaositect]

Edmonton в сообщении #787022 писал(а):

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

Все так.

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

[Sonic86]

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

Edmonton в сообщении #787022 писал(а):

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

Да-да-да, все так.

[Edmonton]

Xaositect
Sonic86
Большое спасибо!