2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Конечные автоматы
Сообщение21.04.2014, 19:00 
Аватара пользователя


08/11/13
66
***
Во всех задачах про автоматы входной и выходной алфавиты всегда {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 


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

-- 22.04.2014, 17:26 --

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

 Профиль  
                  
 
 Re: Конечные автоматы
Сообщение04.04.2015, 23:12 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group