![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Пример. (про АО см.10 вопр)
13. Сети и коллективы автоматов.
19. Конечный автомат – математическая модель дискретных объектов, в которых переход из одного состояния в любое другое может быть совершен за конечное число шагов.
Конечный автомат является частным случаем машины Тьюринга < A1, Q1, S>, а именно: · внешний алфавит конечного автомата А1=АÈ В, АÇ В=Æ, где А – входной алфавит, В – выходной алфавит; · внутренний алфавит Q1=Q (т.е. D={dл, dп, dн}=Æ); соответствие S вход-выход конечного автомата Q´ A®Q´ B, Dom S Í Q´ A, Jm S Í Q´ B.
В этом плане конечный автомат U3 = < A, Q, B, S> в общем случае (как трансдъюсер) является частичным (т.е. не всюду определенным) и недетерминированным. Автомат U3=< A, Q, B, Г>, где Г – отображения, будем называть всюду определенным недетерминированным конечным автоматом. Автомат U3=< A, Q, B, Гf>, где Гf – функциональное отображение, называется всюду определенным детерминированным конечным автоматом. Далее будем рассматривать инициальные автоматы, в которых Гf есть характеристические функции перехода d ивыхода l, т.е: U3(q0)=< A, Q, B, q0, d, l>, q0Î Q, d: Q´ A ® Q, l: Q´ A ® B
Напоминание: 1) Кортеж < A, Q, B, d, l> есть трансдьюсер, т.е. Гf: А*®В* 2) Кортеж < A, Q, d> - акцептор (распознаватель), т.е. aÎ L (s3)Ì А*, если `d(q0, a)= qiq0..qz, qzÎ Q, qz – конечное состояние конечного автомата. 3)Конечный автомат называется комбинационным автоматом, если все его состояния Q эквивалентны между собой, т.е. be=l(qi, а)= l(qj, а) (выходной символ beÎ В не зависит от состояния автомата, а определяется только входным символом аÎ А). В свете этого определения минимальный (приведенный) комбинационный автомат, т.е. если |Q|=1, есть автомат без памяти < A, B, l>, для которого функция переходов d вырождена, а функция выходов имеет вид функции одного аргумента – l(ai)= bj, aiÎ А, bjÎ В 4) Конечный автомат, в котором А=В={0, 1}называют логическим.
|