Конечный автомат: различия между версиями
| [отпатрулированная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
MBH (обсуждение | вклад) |
|||
Строка 66:
Хотя теоремы Клини и отвечают на вопрос о том, что может делать конечный автомат, но отвечают они на этот вопрос неэффективно. Сделаны первые попытки построения иных языков, на которых ответ может быть дан эффективно. Эта проблема языка, играющая кардинальную роль в получении эффективного ответа на вопрос, что может и что не может «делать» конечный автомат, имеет решающее значение и для первых этапов синтеза автомата, то есть для ответа на второй из сформулированных выше вопросов. Если расширить класс динамических систем, которые мы определили терминами «конечный автомат» и «последовательностная машина», включением бесконечной памяти (моделью бесконечной памяти может быть, например, бесконечная лента для хранения символов или бесконечное число состояний), то для динамических систем этого более широкого класса (абстрактные системы этого класса называют [[Машина Тьюринга|машинами Тьюринга]]) ответ на вопрос «что они могут делать?» значительно проще — они могут реализовать '''любой наперед заданный алгоритм'''. При этом само понятие алгоритма трактуется в современной математике как реализация вычисления значений какой-либо [[Рекурсивная функция (теория вычислимости)|рекурсивной функции]]. Столь однозначный и четкий ответ на вопрос «что может делать машина Тьюринга?» дает возможность положить понятие о машине Тьюринга в основу определения понятия алгоритма: алгоритмом называется любой процесс, который может быть осуществлен на конечном автомате, дополненном бесконечной памятью, то есть алгоритмически полных машинах, на машине Тьюринга, на [[Машина Поста|машине Поста]] и др.
''Берем автомат без выхода. Обозначаем состояния и входные сигналы натуральными числами. Фиксируем значение входного сигнала и начинаем прогонять автомат на этом постоянном сигнале от начального состояния до зацикливания. Получаем конечную таблицу значений зависимости следующего состояния от предыдущего. Интерполируем эту функцию полиномом, который единственен и имеет степень длины полученного цикла. Затем из полученных полиномов по известным правилам строим полином отвечающий любым значениям входного сигнала. И получает воo-оот такое здоровенное аналитическое выражение для функции состояния s(t+1)=f(s(t),x(t)), чем по идее и решается задача синтеза...что-то в этом роде...но это надо обдумать, может где-то и глюкануло...Ну а оптимизация сводится к тому, чтобы это выражение упростить. ''
Да, например, для простенькой задачки из учебника Гилла:
расписывая изолированные циклы (зависимость s(t+1)=f(s(t)) отдельно для каждого входного х) и путем двойного интерполирования по Лагранжу вроде бы получаем для состояния:
s(t+1)=(2-x(t))*(3-s(t))+(x(t)-1)*s(t) = 2x(t)s(t)-3s(t)-3x(t)+6
вход x принимает два значения:
1~"положительный стимул"
2~"отрицательный стимул"
состояние s тоже 2:
1 ~ "реакция на последний положительный"
2 ~ "нет реакции на последний положительный"
осталось то же самое проделать для выхода и получаем чисто аналитическую модель автомата.
<br />
== Примечания ==
| |||