Теория автоматов (задача про кубик)

[alexandr66]

Всем доброго времени суток. Друзья, реально горю, времен ив обрез.

Друзья, препод дал задачу вот такую:
Игральный кубик многократно подбрасывается вверх, он падает, выпадает какое то число (от 1 до 6) и делаются следующие отметки:
1) При выпадении цифры 1 каждый второй раз делается одна отметка.
2) При выпадении цифры 1 три раза подряд делается вторая отметка.
3) При выпадении цифры 2 каждый второй раз делается третья отметка.
4) При выпадении цифры 2 три раза подряд делается четвертая отметка.
...............
И так далее до цифры 6.

В общем как я начал делать, что за что обозначил:
x1 - выпадение цифры 1
x2 - выпадение цифры 2
х3 - выпадение цифры 3
х4 - выпадение цифры 4
х5 - выпадение цифры 5
х6 - выпадение цифры 6

y1 - отметка при цифре 1 каждый второй раз
y2 - отметка при цифре 2 каждый второй раз
y3 - отметка при цифре 3 каждый второй раз
y4 - отметка при цифре 4 каждый второй раз
y5 - отметка при цифре 5 каждый второй раз
y6 - отметка при цифре 6 каждый второй раз

y11 - отметка при цифре 1 три раза подряд
y22 - отметка при цифре 2 три раза подряд
y33 - отметка при цифре 3 три раза подряд
y44 - отметка при цифре 4 три раза подряд
y55 - отметка при цифре 5 три раза подряд
y66 - отметка при цифре 6 три раза подряд

Нужно нарисовать таблицу переходов, по вертикали и горизонтали состояния. И нарисовать потом по таблице граф (ну это я сам). Граф как мне сказали будет ПОЛНЫМ, то есть всё со всем связанно.

Я пообщался еще с программистами, и пришли мы к такому выводу:
Автомат должен помнить, чётное или нечётное число единиц, двоек... шестёрок выпало в прошлом и на каждом чётном выпадении ставить метку. Уже для решения этой задачи нужен автомат с 2^6 = 64 состояниями. Чтобы отслеживать тройки подряд по шести позициям, нужен автомат с 18 состояниями. Чтобы отслеживать обе эти ситуации, нужно декартово произведение этих двух автоматов, то есть 64*18 =1152 состояния.

Я подошел к преподу, сказал об этом, он согласился что состояний много, но можно как то оптимизировать всё, объединить что ли, и вообще свести автомат как то к общему случаю что ли, до 6-10 состояний оптимизировать. Предложили взять q0 начальное состояние - это типа когда фишка в руках и только собрались подбрасывать;
q1 - состояние, в котором выпала цифра Xi первый раз
q11 - состояние, в котором выпала цифра Xi второй раз и тут делается отметка.
q12 - состояние, в котором выпала цифра Xi три раза подряд и тут делается отметка.

q2 - состояние, в котором выпала цифра Xi+1 первый раз
q21 - состояние, в котором выпала цифра Xi+1 второй раз и тут делается отметка.
....
и так далее

Помогите пожалуйста что ли придумать, заранее благодарен.

[alexandr66]

Парни кто нибудь в курсе а?

[alexandr66]

срочно нужно

[alexandr66]

ребята ну помогите кто нибудь

[alexandr66]

вообще ничего не понимаю

[alexandr66]

парни, кто нибудь сможет помочь все таки ли нет?

[rrrFer]

Нельзя тут оптимизировать. У обычного автомата нет памяти, он не может помнить какая там фишка выпала.

Что значит "делается отметка"? - у ОБЫЧНОГО автомата ПО ОПРЕДЕЛЕНИЮ нет памяти. Если у тебя автомат с памятью, то такой таблицей, как ты хочешь, его не представить, таблица должна отражать состояние памяти.

Узнай у препода нормально что он хочет. Задание он сам придумывал?

Автомат с магазинной памятью вообще не графом описывается. Потому что ты запаришься узлы рисовать. Ведь узлы, хранящие разные значения в памяти - это совсем разные узлы, из них (в зависимости от значения) могут быть разные переходы (разные связи с другими узлами) и в твоей задаче это более чем хорошо видно. нельзя вот так просто взять и соединить 2 состояния в одно. Что ты с дугами при этом будешь делать?

Самый простой вариант тут - написать программу, которая построить здоровенную таблицу для препода, а потом скрипт, который построит граф в графвизе. Я бы делал именно так.

[alexandr66]

Это как автоматы МИЛИ или МУРА например надо сделать, где в таблице переходов может писаться через запитую x и y, где например x - цифра, а y - отметка. Вот мне и нужно как то оптимизировать, как то уменьшить состояния, более общий случай сделать для 6 цифр этих на кубике, итеративно как то, вот посмотри еще вот тут я обсуждаю эту тему http://www.cyberforum.ru/automata-th...ad1183232.html

[alexandr66]

че парни подскажите а

[rrrFer]

Не могу посмотреть, на том форуме меня забанили.

В том примере, что ты привел, отметка привязывается к дуге.
Состояние не знает по какой дуге в него попали, потому что не имеет памяти.

Я тебе уже сказал как решается твоя задача - пишешь программу, она строит большую таблицу. Если нужно нарисовать граф - запрегай скрипт для графвиза.