Как построить конечный автомат?

[Gilb007]

Есть конечный автомат.На выходе всегда только повторяющаяся последовательность с периодом (1111110).Сколько состояний у этого автомата??
Понятно,что можно построить с 7-ю состояниями,но получается можно меньше (по диаграмме Мура,наверно).Причем в условии задачи преподаватель вначале сказал,что на вход ничего не подается,но я смог убедить что нужно подавать какие-то входные слова (число состояний конечного автомата посути есть вес ограниченно-детерминированной функии,а т.к о.-д ф.-ии входят в класс детерминированных функций,то по одному из определений .что число входных символов равно числу числу символов на выходе).Пробывал строить информационное дерево,но пока не могу обосновать почему можно меньше 7-ми состояний.

[arseniiv]

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

Если символы выводить можно "как попало", то можно сделать автомат с двумя состояниями: одно выводит "111111" и идёт ко второму, а другое - "0", идя обратно. И всё.

Никогда, честно говоря, не знал, что есть КА с выводом

[Xaositect]

arseniiv в сообщении #223488 писал(а):

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

Есть автоматы-распознаватели(без выхода) и автоматы-преобразователи(с выходом). Символ на выходе ровно один(по другим определениям, не больше одного) на каждом шаге. На самом деле есть еще и автоматы без входа.

Откуда такая уверенность, что можно меньше семи? После склейки эквивалентных состояний и удаления недостижимых мы получим из автомата без входа автомат такого вида:

*-->...-->*-->*-->...-->*-->*
              ^             |
              +-------------+

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

[Gilb007]

arseniiv в сообщении #223488 писал(а):

Как это - "на выходе" у автомата?

Да я сам как бы удивился,но не стал возрожать по этому поводу когда давали условие)Преподаватель на листке просто нарисовал ящик,говорит это конечный автомат и на входе ничего не подается,а на выходе только $(1111110)^*$.Задача найти состояния у этого автомата.
Я сразу сказал про 7-м,но сказал подумать по поводу нижней оценки (т.е ни да,ни нет).

Xaositect в сообщении #223490 писал(а):

Есть автоматы-распознаватели(без выхода) и автоматы-преобразователи(с выходом). Символ на выходе ровно один(по другим определениям, не больше одного) на каждом шаге. На самом деле есть еще и автоматы без входа.

Откуда такая уверенность, что можно меньше семи? После склейки эквивалентных состояний и удаления недостижимых мы получим из автомата без входа автомат такого вида:

*-->...-->*-->*-->...-->*-->*
              ^             |
              +-------------+

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

Не совсем понял как выглядит ваш автомат.Это диаграмма Мура?
Не поленился нарисовать дерево .

Показал только 7-мь ярусов.Специально обозначил вершины.

[Xaositect]

Gilb007 в сообщении #223506 писал(а):

Не совсем понял как выглядит ваш автомат.Это диаграмма Мура?

Да, это диаграмма Мура.

[Gilb007]

Xaositect,скажите пожалуйста,какие состояния вы объеденили,чтобы получить диаграмму Мура что вы привели выше?

[Xaositect]

Я утвеждал, что можно для любого автомата без входа (или при условии, что выходная последовательность не зависит от входа) построить ему эквивалентный автомат такого $\rho$-образного вида, у которого не меньше количество состояний.

[Gilb007]

Хорошо,но как он тогда выглядит?)

[Xaositect]

Gilb007 в сообщении #223615 писал(а):

Хорошо,но как он тогда выглядит?)

В каком смысле?
Я непонятно диаграмму Мура нарисовал?

[Gilb007]

Xaositect,да.Не совсем понял как он выглядит.

[Xaositect]

Цепочка состояний $q_0,q_1,\dots,q_k,dots,q_n$, начинающаяся с начального состояния. Из состояний $q_0,\dots, q_{n-1}$ по любому символу идет переход на следующее состояние в цепочке. Из состояния $q_n$ идет переход на $q_k$. Если на выход при переходе из состояния $q_i$ в $q_{i+1}$ выдается символ $a_i$, при переходе из $q_n$ в $q_k$ - символ $a_n$, то такой автомат независимо от входа порождает последовательность $a_0 a_1\dots a_{k-1}(a_k a_{k+1}\dots a_n)^{\omega}$. В Вашем случае $k=0$

[Gilb007]

можно меньше 7-ми построить