Приведение КА к полному ДКА.

[antondm]

Вот сел за Формальные языки и грамматики.
В обще есть на неком сайте

(Оффтоп)

http://www.intuit.ru/department/algorithms/mathformlang/class/free/2/4.html

задача к следующей теореме.
Т. Каждый автоматный язык распознается некоторым полным детерминированным конечным автоматом.
Ну вот и там автор строит его следующим образом.
$ \begin{aligned} & M\rightleftharpoons \{Q,\Sigma,\Delta,I,F\}\text{ -- начальный автомат}\\ & \Delta=\{\langle p,a,q\rangle | \text{$p\in Q\, $, $q\in Q \, $ , $a\in\Sigma\,$}\}\\ \end{aligned} $
$ \text{Пусть $\rho(Q)$ -- множество всех подмножеств множества $Q$} \text{ и $a\in \Sigma,\,H\subseteq Q$}\\ \text{тогда обозначим через } \\ \Delta_a(H) = \{q\in Q | \langle p,a,q \rangle \in \Delta \text{ для некоторого }p \in H \} $
В общем новый полный ДКА должен выглядеть так:
$ \begin{aligned} &M^{'}\rightleftharpoons \{Q^{'} ,\Sigma,\Delta^{'} ,I^{'} ,F^{'} \}\text{ -- конечный автомат}\\ &Q^{'}=\rho(Q)\\ &\Delta^{'}=\{\langle H,a,\Delta_a(H) \rangle |\, H\subseteq Q,\, a\in \Sigma\}\\ &I=I^{'}\\ &F=\{H\subseteq Q | H \cap F \neq \varnothing\} \end{aligned} $
Автор предлагает задачу.
У. Найти полный детерминированный конечный автомат, эквивалентный автомату, изображенному на диаграмме.
Автомат следующий:
$M=\{\{1,2},{a,b},{\langle 1,ab,2\rangle\ , \langle 2,a,2 \rangle\},\{1\},\{2\}\}$
Я привел его к нормальному виду
$M=\{\{1,2,3},{a,b},{\langle 1,ab,2\rangle\ , \langle 2,b,3 \rangle\ , \langle 3,a,3 \rangle\ , \langle 1,a,3 \rangle\},\{1\},\{1,3\}\}$
и применил описанный в теореме процесс
$ \begin{aligned} & I = \{1\}\\ & F = \{1,3\}\\ & \text{ а $\Delta^{'}$ лучше всего записать в виде таблички }\\ \end{aligned} $
$ \begin{tabular}{|l|l|l|} \hline & a & b \\ \hline \{1\} & \{2,3\} & \varnothing \\ \hline \{2\} & \varnothing & \{3\} \\ \hline \{3\} & \{3\} & \varnothing \\ \hline \{1,2\} & \{2,3\} & \{3\} \\ \hline \{1,3\} & \{2,3\} & \varnothing \\ \hline \{2,3\} & \{3\} & \{3\} \\ \hline \end{tabular} $
В общем получается не идентичный автомат начальному. Начальный автомат мог распознавать слова {ab,aba^k,a^k| k>=0}, а этот { ab,aba^k | k>=0} . После построения схемы теоремы я отсек все недостижимые пути.
Подскажите как вообще приводить автомат к ДКА. Если можно ссылки на литературу тоже.

[Null]

У меня получился автомат с состояниями 12,23 и 2, со входом 12, выходами 12,23 и 2.
12,a->23
23,a->2
23,b->2
2,a->2
где 3 -состояние на ребре помеченном ab, его разбить надо.


удаленны вершины 1,3,13,123 как недостижимые.(123-выход)
связи были
1,a->3
3,b->2
13,a->3
13,b->2
123,a->23
123,b->2


Прикольный метод, буду знать))

[antondm]

Метод так себе. На практике он применим только как решение небольших задач - слишком большое множество подмножеств получается даже при небольшом количестве состояний.

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

antondm в сообщении #350292 писал(а):

Метод так себе. На практике он применим только как решение небольших задач - слишком большое множество подмножеств получается даже при небольшом количестве состояний.

А ничего лучшего и не существует

Чтоб убедится в этом, предлагаю решить следующую задачу. Для произвольного натурального $n$ придумать конечный автомат с $n$ состояниями, такой что любой эквивалентный (то есть распознающий тот же самый язык) полный детерминированный конечный автомат содержит не менее чем $2^n$ состояний.

[Null]

Букв в алфавите 2? Если $2^n$, то просто вроде.
И может $2^n-1$, а то пустое состояние всегда недоступно и выкидывается?

[Null]

Оно может быть достижимым, но оно конечное и не выход, т.е его можно удалить

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

Null в сообщении #350603 писал(а):

Букв в алфавите 2? Если $2^n$, то просто вроде.
И может $2^n-1$, а то пустое состояние всегда недоступно и выкидывается?

Да, в алфавите две буквы. А построить в задаче просят полный ДКА, то есть с пустым состоянием.

Тут, кстати, на этом форуме в прошлом году обсуждение было, должно ли "пустое состояние" (не знаю, насколько это адекватный перевод английского trap state) присутствовать в ДКА (там, где оно, естественно, подразумевается). Если брать определения из англоязычной литературы, то да. Если из русскоязычной, то нет. Сравните хотя бы две статьи из Википедии:

http://ru.wikipedia.org/wiki/%D0%9A%D0% ... 1.82.D1.8C и диаграмму из этой статьи.

http://en.wikipedia.org/wiki/Determinis ... te_machine

[Null]

Я назвал его пустым потому что оно соответствует пустому множеству в приведенном вначале алгоритмом.
Автоматы пораждающие слова с n-1 c конца буквой а подходят?
эх $2^{n-1}$ состояний будут

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

Null в сообщении #350744 писал(а):

Я назвал его пустым потому что оно соответствует пустому множеству в приведенном вначале алгоритмом.

Я так и понял.

Null в сообщении #350744 писал(а):

Автоматы пораждающие слова с n-1 c конца буквой а подходят?

А вот этого не понял. Автоматы не порождают слова, а распознают их. Поясните, какой конкретно автомат Вы имели в виду.

[Null]

Ну если взять не детерминированный, то это будет
1,a->1
1,b->1
1,a->2
2,a->3
2,b->3
.....
n-1,a->n
n-1,b->n

1 - вход n-выход

его минимальная детерминированная форма содержит $2^{n-1}$ состояний

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

Понятно. Пример с $2^n$ состояниями выглядит похоже. Не буду лишать Вас удовольствия найти его самому

А почему в Вашем примере минимальный детерминированный автомат имеет $2^{n-1}$ состояний я, признаться, не понял. Мне кажется, что их меньше.

[Null]

Просто если на двух словах $S_1$ и $S_2$ длинны N-1 мы окажемся в одном состоянии и эти слова различаются в iтой букве то на словах $S_1+b^{i-1}$ и $S_2+b^{i-1}$ мы окажемся опять в одном состоянии, но одно слово допустимо а другое нет, т.е. это выход и не выход

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

Чувствуется, что в примере ошибка, но уже вечер и спать хочется... Завтра с утра найду

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

Null в сообщении #350839 писал(а):

Просто если на двух словах $S_1$ и $S_2$ длинны N-1 мы окажемся в одном состоянии и эти слова различаются в iтой букве то на словах $S_1+b^{i-1}$ и $S_2+b^{i-1}$ мы окажемся опять в одном состоянии, но одно слово допустимо а другое нет, т.е. это выход и не выход

Опять не понял объяснение. Что у Вас за сумма слов такая? Конкатенация имеется в виду или что-то другое?

Но с утверждением о том, что минимальный ДКА в Вашем примере имеет $2^{n-1}$ состояние, всё же вынужден согласиться. Да, это действительно так. Ошибки в примере нет.

Но $2^{n-1}$ недостаточно. Нужно $2^n$