2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Конечные автоматы
Сообщение21.04.2014, 19:00 
Аватара пользователя
***
Во всех задачах про автоматы входной и выходной алфавиты всегда {0,1}, число состояний – степень двойки 2^n. Автомат задается каноническими уравнениями: в 1-й строке записано n – число переменных, кодирующих состояние, потом пробел, потом значения этих переменных в начальном состоянии (без пробела) потом n строк – вектора значений (см. п.1) функций перехода (каждая от n+1 переменной, вход – последняя переменная), потом еще одна строка – вектор значений функции выхода (тоже от n+1 переменной, вход – последняя переменная). Например, единичная задержка (автомат с одним входом, одним выходом и двумя состояниями, функция перехода F(q,x)=x, функция выхода G(q,x)=q) с начальным состоянием 0 задается так:
1 0
2 2 0101
2 2 0011
***

Возник вопрос, как мне определить, что я получу на выходе подавая автомату на вход различные слова ?

Исходя из данного представления, то есть представления в виде канонической таблицы, конечно на листочке с бумагой можно построить систему канонических уравнений автомата или что тоже самое о-д. функцию(автоматную). Там та все ясно. А как быть тут ?

 
 
 
 Re: Конечные автоматы
Сообщение22.04.2014, 15:15 
если имеется ввиду автомат без памяти ,имеющий m-входов и n-выходов,
то как черный ящик он полностью будет определяться эмпирической
или наперед заданной, таблицей истинности-$2^m$ состояний
входов и аналогичнно для выходов
в данном случае(простейшем) предполагается, что внутри находятся двоичные
логические элементы (в настоящее время есть третье состояние-высокий импеданс)
-к примеру на входе дешифратор а далее схемы к каждому выходу
Создавая логическую функцию между входным словом и выходом Вы
описываете внутреннюю структуру-и экономите кремний.
Если состояние выхода автомата зависит от порядка следования входных
"векторов"-это автомат с памятью -например сумматор (простейшая схема
регистра)
У них делают сброс(reset)-иначе все описывать можно будет
только с помощью теории вероятностей-и далее два варианта:
принцип программного управления облегчит Вам жизнь но замедлит работу автомата и аппаратно-
можно подумать ,поломать голову, будет сложнее, но работает быстрее
Еще есть тактовый генератор
не знаю это ли Вы хотели услышать?

-- 22.04.2014, 17:26 --

На каждом такте 1,2,3... у автомата сигнал получают все входы-работать
схема должна предсказуемо- по Вашей функции

 
 
 
 Re: Конечные автоматы
Сообщение04.04.2015, 23:12 
Не хотелось создавать тему -- потому здесь у меня такой вопрос -- мне надо построить конечный автомат который допускает строки в которых 3ий и 5 ый символ идут в произвольной последоватольности. Например -- BCACABC (алфавит АВС). Непонятно как то даже не вдаваясь вдетали--ведь оба символы здесь А, как тогда должны идти остальные символы. И если 3 и 5 символы идут в прозв. Послед. Значит ли то что они могут быть любой из этой комбинации -- АА, АВ, АС, ВА, ВВ, ВС, СА, СВ, СС. Какая должна быть длина такой строки и как вообще должен выглядеть этот автомат?

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group