Опубликовать ОпубликоватьРеферат на тему:
Теория автоматов — раздел дискретной математики, изучающий абстрактные автоматы — вычислительные машины, представленные в виде математических моделей — и задачи, которые они могут решать.
Теория автоматов наиболее тесно связана с теорией алгоритмов: автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результат по шагам заданного алгоритма.
Символ — любой атомарный блок данных, который может производить эффект на машину. Чаще всего символ — это буква обычного языка, но может быть, к примеру, графическим элементом диаграммы.
Говорят, что язык L читается (принимается) автоматом M, если он состоит из слов w на базе алфавита Σ таких, что если эти слова вводятся в M, по окончанию обработки он приходит в одно из принимающих состояний F:
Обычно автомат переходит из состояния в состояние с помощью функции перехода δ, читая при этом один символ из ввода. Есть также автоматы, которые могут перейти в новое состояния без чтения символа. Функция перехода без чтения символа называется ε-переход (эпсилон-переход).
Практически теория автоматов применяется при разработке лексеров и парсеров для формальных языков (в том числе языков программирования), а также при построении компиляторов и разработке самих языков программирования.
Другое важнейшее применение теории автоматов — математически строгое нахождение разрешимости и сложности задач.
Категории: Теория автоматов.
Текст доступен по лицензии Creative Commons Attribution-ShareAlike.wreferat.baza-referat.ru
ОпубликоватьРеферат на тему:
Теория автоматов — раздел дискретной математики, изучающий абстрактные автоматы — вычислительные машины, представленные в виде математических моделей — и задачи, которые они могут решать.
Теория автоматов наиболее тесно связана с теорией алгоритмов: автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результат по шагам заданного алгоритма.
Символ — любой атомарный блок данных, который может производить эффект на машину. Чаще всего символ — это буква обычного языка, но может быть, к примеру, графическим элементом диаграммы.
Говорят, что язык L читается (принимается) автоматом M, если он состоит из слов w на базе алфавита Σ таких, что если эти слова вводятся в M, по окончанию обработки он приходит в одно из принимающих состояний F:
Обычно автомат переходит из состояния в состояние с помощью функции перехода δ, читая при этом один символ из ввода. Есть также автоматы, которые могут перейти в новое состояния без чтения символа. Функция перехода без чтения символа называется ε-переход (эпсилон-переход).
Практически теория автоматов применяется при разработке лексеров и парсеров для формальных языков (в том числе языков программирования), а также при построении компиляторов и разработке самих языков программирования.
Другое важнейшее применение теории автоматов — математически строгое нахождение разрешимости и сложности задач.
Категории: Теория автоматов.
Текст доступен по лицензии Creative Commons Attribution-ShareAlike.www.wreferat.baza-referat.ru
Как известно цифровые электронные вычислительные машины, т. е. компьютеры, предназначены для обработки цифровой информации и являются частным, но наиболее распространенным видом цифровых автоматов. Для успешного изучения общих принципов обработки цифровой информации рационально, по возможности максимально, отвлечься от реального аппаратного обеспечения компьютера и рассматривать компьютер как некоторый абстрактный цифровой автомат, предназначенный для обработки информации, представленной в цифровой форме. Знания по прикладной теории таких автоматов необходимы для успешного поиска новых принципов построения компьютеров, совершенствования уже известных алгоритмов обработки цифровой информации, грамотной эксплуатации вычислительной техники и разработки различного программного обеспечения.
Для всего этого необходимы четкие знания арифметических и логических основ цифровых автоматов, принципов анализа и синтеза этих автоматов. Все это является теоретической основой специальных инженерных дисциплин по вычислительной технике, изучаемых на последующих курсах студентами, которых готовят как специалистов в области эксплуатации, проектирования и создания аппаратного и программного обеспечения вычислительной техники, а также автоматизации различных научно-технических систем.
Исходя из всего выше сказанного, тему моего реферата считаю важной и актуальной на данном этапе обучения.
Необходимо рассмотреть такие вопросы как:
o Основные понятия теории автоматов
o Входной алфавит и выходной алфавит
o Представление событий в автоматах
o Автоматы Мили и Мура
1. Основные понятия теории автоматов
Термин «автомат», как правило, используется в двух аспектах. С одной стороны, автомат — это устройство, выполняющее некоторые функции без непосредственного участия человека. В этом смысле мы говорим, что ЭВМ автомат, так как после загрузки программы и исходных данных ЭВМ решает заданную задачу без участия человека. С другой стороны, термин «автомат» как математическое понятие обозначает математическую модель реальных технических автоматов. В этом смысле автомат представляется как «черный ящик», имеющий конечное число входов и выходов и некоторое множество внутренних состояний Q = {q1(t), q2(t), …, qn (t)}, в которые он под действием входных сигналов переходит скачкообразно, т. е. практически мгновенно, минуя промежуточное состояние. Конечно, это условие не выполняется в реальности, так как любой переходный процесс длится конечное время.
Автомат называется конечным, если множество его внутренних состояний и множество значений входных сигналов конечные множества.
На практике часто используется понятие цифрового автомата, под которым понимают устройство, предназначенное для преобразования информации. С общей точки зрения, процесс получения информации есть ни что иное, как процесс снятия неопределенности в результате того, что из некоторой совокупности возможных в данной конкретной ситуации явлений выделяется явление, фактически имевшее место.
Таким образом, в понятии информации существенно не само происшедшее явление, а лишь его отношение к совокупности явлений, которые могли произойти.
Устройства, служащие для преобразования дискретной информации, называются дискретными автоматами.
В современных дискретных автоматах принято обычно отождествлять буквы используемого стандартного алфавита с цифрами той или иной системы счисления.
В состав цифровых автоматов обязательно входят запоминающие элементы (элементы памяти). Выходные сигналы в таких автоматах формируются в зависимости от входных сигналов и состояний, в которых находятся элементы памяти. Поэтому дискретные автоматы принято называть также цифровыми автоматами.
Основным качеством, выделяющим дискретные автоматы из числа всех других преобразователей информации, является наличие дискретного множества внутренних состояний и свойства скачкообразного перехода автомата из одного состояния в другое. Скачкообразность перехода означает возможность трактовать этот переход как мгновенный, хотя для любого реально существующего автомата имеет место конечная длительность переходных процессов, так что требование скачкообразности перехода не удовлетворяется.
Второе допущение состоит в том, что после перехода автомата в произвольное состояние переход в следующее состояние оказывается возможным не ранее, чем через некоторый фиксированный для данного автомата промежуток времени > 0, так называемый интервал дискретности автомата. Это допущение дает возможность рассматривать функционирование цифрового автомата в дискретном времени. При построении автоматов с дискретным автоматным временем различают синхронные и асинхронные автоматы.
В синхронных автоматах моменты времени, в которые оказывается возможным изменение состояния автомата, определяются специальным устройством генератором синхронизирующих импульсов. Соседние моменты времени оказываются при этом обычно разделенными равными временными промежутками.
В асинхронных автоматах моменты переходов из одного состояния в другое заранее не определены и могут совершаться через неравные между собой промежутки времени.
Изменения состояний цифрового автомата вызываются входными сигналами, которые возникают вне автомата и передаются в автомат по конечному числу входных каналов. В отношении входных сигналов цифровых автоматов принимаются два допущения: во-первых, для любого цифрового автомата число различных входных сигналов обязательно конечно, а, во-вторых, входные сигналы рассматриваются как причина перехода автомата из одного состояния в другое и относятся к моментам времени, определяемым соответствующими им переходами.
Отметим, что при таком допущении входной сигнал рассматривается как мгновенный, хотя в действительности он имеет конечную длительность. Особо следует подчеркнуть, что реальный физический входной сигнал, вызывающий изменение состояния автомата в момент времени t, может кончиться до наступления этого момента, однако, тем не менее, он относится именно к текущему моменту времени t, а не к предыдущему (t 1).
Результатом работы цифрового автомата является выдача выходных сигналов, передаваемых из автомата во внешние цепи по конечному числу выходных каналов.
В отношении выходных сигналов вводятся допущения, аналогичные допущениям для входных сигналов. Во-первых, число различных выходных сигналов для любого цифрового автомата всегда конечно. Во-вторых, каждому отличному от нуля моменту автоматного времени относится соответствующий ему входной сигнал. Реальный физический выходной сигнал y (t), отнесенный к моменту времени t, появляется всегда после соответствующего этому же моменту времени входного сигнала x (t). Что же касается момента времени t перехода автомата из состояния q (t1) в состояние q (t), то сигнал y (t) может фактически появится либо раньше, либо позже этого момента.
В первом случае принимается, что выходной сигнал y (t) однозначно определяется входным сигналом x (t) и состоянием q (t1) автомата в предыдущий момент времени, во втором случае сигнал y (t) однозначно определяется парой (x (t), q (t)). Будем считать, что для любого момента времени всегда имеет место лишь одна из этих возможностей (одновременно для всех переходов).
Цифровые автоматы, в которых выходной сигнал y (t) определяется парой (x (t), q (t 1)), будем называть автоматами первого рода, а автоматы, в которых сигнал y (t) определяется парой (x (t), q (t)), автоматами второго рода.
Цифровой автомат (первого или второго рода) называется правильным, если выходной сигнал y (t) определяется одним лишь его состоянием (q (t 1) или q (t)) и не зависит явно от входного сигнала x (t).
Автоаты первого рода обычно называют автоматами Мили, а автоматы второго рода автоматами Мура.
Общая теория автоматов при сделанных выше допущениях разбивается на две большие части, которым присвоены названия абстрактной теории автоматов и структурной теории автоматов. Различие между ними заключается в том, что в абстрактной теории не учитываются структура как самого автомата, так и структуры его входных и выходных сигналов. Входные и выходные сигналы рассматриваются при этом просто как буквы двух фиксированных для данного автомата алфавитов:
o входного и выходного. Не интересуясь способом построения автомата, абстрактная
o теория изучает лишь те переходы, которые претерпевает автомат под воздействием
o входных сигналов, и те выходные сигналы, которые он при этом выдает.
Показать Свернутьwestud.ru
Теория автоматов.
На протяжении последних десятилетий велись и ведутся интенсивные работы по созданию и использованию различных систем и устройств для переработки дискретной информации. Преобразователи дискретной информации широко используются в качестве различного рода технических автоматов, вычислительных устройств и их функциональных блоков, устройств управления роботами, управляющих объектами по заданному алгоритму. Широкий класс таких преобразователей объединяется под общим названием -автоматы. Эти устройства имеют конечное число входов, воспринимающих информацию, и конечное число выходов для выдачи переработанной информации. Зависимость между входами и выходами задается предписанным алгоритмом переработки информации. Информация на входе и выходе представляется символами, физическими носителями которых являются квантованные по времени сигналы.
Если «К» символов одновременно следующих по параллельным входным либо выходным каналам, рассматривать как один символ из соответствующего алфавита, следующего по единому "склеенному" каналу, то такой автомат можно представить как устройство с одним входом и одним выходом (Рис. 1)
Рис. 1 - Общая функциональная модель преобразователя дискретной информации
Известны два подхода к определению термина автомат. При первом его истолковывают как устройство, которое без непосредственного участия человека выполняет функции приема, преобразования и передачи энергии, информации и т.п. в соответствии с заложенной в него программой, при втором - как математическую модель реальных преобразователей дискретной информации. Функционирование его состоит в том, что последовательность z1,z2,... символов конечного или в общем случае бесконечного алфавита Z, поступающая на вход, вызывает на его выходе определенную последовательность w1,w2,... символов того же или другого алфавита. Таким образом, самой общей математической моделью преобразователя дискретной информации является последовательностная функция, отображающая множество Z всех последовательностей символов алфавита Z в другое множество W* последовательностей символов алфавита W. Такая интерпретация позволяет схематично представить преобразователь как устройство, реализующее отображение одного множества на другое (рис. 2а).
Рис. 2а - Формальная модель преобразователя
Данное отображение называется алфавитным отображением или алфавитным оператором.
Теория автоматов - это раздел теории управляющих систем, изучающий математические модели преобразователей дискретной информации, называемые автоматами. С определенной точки зрения такими преобразователями являются как реальные устройства (вычислительные машины, живые организмы), так и абстрактные системы (например, формальная система – это совокупность абстрактных объектов, не связанных с внешним миром, в котором представлены правила оперирования множеством символов в строго синтаксической трактовке без учета смыслового содержания, т.е. семантики; аксиоматические теории, описывающие определенную совокупность явлений в их причинно-следственной связи друг с другом).
Наиболее тесно теория автоматов связана с теорией алгоритмов. Это объясняется тем, что автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результирующую информацию по шагам заданного алгоритма. Эти преобразования возможны с помощью технических и/или программных средств. Автомат можно представить как некоторое устройство (чёрный ящик), на которое подаются входные сигналы и снимаются выходные и которое может иметь некоторые внутренние состояния. При анализе автоматов изучают их поведение при различных возмущающих воздействиях и минимизируют число состояний автомата для работы по заданному алгоритму. Такой автомат называют абстрактным, т.к. абстрагируются от реальных физических входных и выходных сигналов, рассматривая их просто как буквы некоторого алфавита и в связи с идеализированным дискретным временем. При синтезе автоматов (процесс соединения или объединения) формируют систему из элементарных автоматов, эквивалентную заданному абстрактному автомату. Такой автомат называется структурным. Особое место в теории автоматов занимает понятие конечного автомата.
Результат преобразования вход => выход (рис.2а) зачастую зависит не только от входа в данный момент времени, но и от того, что было раньше на входе, от входной истории, т.е. от предыстории преобразования. Число возможных входных историй бесконечно (счетно), даже если различных элементов входной информации у автомата конечное число (как в конечном функциональном преобразователе). Чтобы эти предыстории как-то запоминать и отличать друг от друга преобразователь должен иметь память. Для этого в устройство (рис. 1.1,6) вводится алфавит состояний Q = {qx,q2,...qm).
Понятие состояния q при этом играет очень важную роль. В своих состояниях автомат запоминает свое концентрированное прошлое. На один и тот же входной сигнал преобразователь может реагировать по-разному в зависимости от того, в каком состоянии он находится в данный момент
Конечный автомат (рис.2б) — математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных, при условии, что общее возможное количество состояний Q и множество входных сигналов Z конечны. Конечный автомат является частным случаем абстрактного автомата.
Рис.2б – Конечный автомат
Конечный автомат является одним из важнейших видов управляющих систем. Главным достоинством конечных автоматов является то, что в них естественным образом описываются системы, управляемые внешними событиями.
Теория автоматов занимается изучением процессов, протекающих в автоматах различного рода, и общих закономерностей, которым они подчинены, широко применяя для этого алгебраический аппарат, математическую логику, комбинаторный анализ и теорию вероятностей. Конструируя надежные, хорошо работающие автоматы, приходится решать необычайно сложные задачи. Например, надо определять устойчивость систем, чтобы уменьшить различные отклонения в работе автоматических машин. Надо изучать и чувствительность автоматов, так как в процессе работы свойства систем регулирования не остаются постоянными.
Теория автоматов находит применение как в математике, так и в решении практических задач. Например, средствами теории автоматов доказывается разрешимость некоторых формальных исчислений. Применение методов и понятий теории автоматов к изучению формальных и естественных языков привело к возникновению математической лингвистики (математическая лингвистика - математическая дисциплина, предметом которой является разработка формального аппарата для описания строения естественных и некоторых искусственных языков.) Понятие автомата может служить модельным объектом в самых разнообразных задачах, благодаря чему возможно применение теории автоматов в различных научных и прикладных исследованиях.
Актуальность теории автоматов
Существует множество объектов управления, связанных с большой ответственностью: ядерные и химические реакторы, комплексы промышленного, оборонного, космического назначения, горное дело. Успех в работе с ними прямо зависит от четкости и слаженности действий, от умения принимать выверенные решения и грамотно анализировать ситуацию, от возможности однозначной интерпретации информации. Различная природа физических процессов, протекающих в объектах, сложный характер взаимодействия между ними и управляющими системами обуславливает трудности разработки, алгоритмизации и программирования задач управления. Возникают трудности, связанные с необходимостью достижения наглядности и структурированности.
Для решения этих задач используется развитый математический аппарат теории автоматов.
Описание логики поведения (при каких условиях необходимо выполнить те или иные действия) при автоматном подходе структурировано. Это свойство делает автоматное описание сложного поведения наглядным и ясным. Корректность работы при использовании автоматов закладывается еще на этапе проектирования, благодаря графическому представлению, т.е.
1) наглядно представляется поведение управляющих автоматов (графически, таблично) и композиций из них;
2) композиций из них;
3) отображаются желаемые состояния;
4) можно легко увидеть возможные ошибки в проектировании, такие как отсутствие некоторого перехода, недоступность состояния и т.д.
Все это приводит к четкому пониманию работы устройства. Процессы управления, проектирования могут быть представлены в виде элементов с предсказуемым поведением.
Пример: один из крупнейших мировых производителей авиационной, космической и военной техники – американская корпорация «Боинг» занимается системами стабилизации самолетов с использованием чистой теории автоматов. Большая часть теории автоматов была успешно использована в системных программах и текстовых фильтрах в ОС UNIX. Это позволяет множеству людей работать на высоком уровне и разрабатывать очень эффективные программы.
Области применения ТА поражают своим размахом и не ограничиваются узкой направленностью и специализацией. Рассмотрим некоторые из них.
myunivercity.ru
Размещено на
1
Содержание
| Значение признака С и знака остатка | Комментарий микрооперации в следующем такте | Значение очередной цифры частного | |
| Пробное вычитание(в см ) | |||
| С=0, остаток<0 | Деление состоитсяСдвиг влево на 1р. | - | |
| После пробного вычитания | |||
| С=0, остаток<0 | Сложение( в сумматор посылаетя У), затем сдвиг влево на 1р. | 0Zi=Ci | |
| С=0, остаток>=0 | Вычитание (в сумматор посылаетя ), затем сдвиг влево на 1р. | 1Zi=Ci |
Turbo Debugger Log
Variables
a 28912 (70F0h)
b 36860 (8FFCh)
c 's' 115 (73h)
ost ' ' 0 (00h)
rez ' ' 0 (00h)
start @5F9C:0000
CPU 80486
ds:0000 F0 70 FC 8F 73 00 00 00 Ёp№Пs
ds:0008 00 00 00 00 00 00 00 00
ds:0010 B8 9B 5F 8E D8 8B 1E 00 ¬Ы_О+Л_
ds:0018 00 2B 1E 02 00 70 70 83 +__ ppГ
CPU 80486
ax 5F9B
bx 0000
cx 0000
dx 0000
si 0000
di 0000
bp 0000
sp 0280
ds 5F9B
es 5F63
ss 5F73
cs 5F9C
ip 0005
CPU 80486
c=0
z=0
s=0
o=0
p=0
a=0
i=1
d=0
CPU 80486
ax 0001
bx E0F4
cx 0000
dx 0000
si 0000
di 0000
bp 0000
sp 0280
ds 5F9B
es 5F63
ss 5F73
cs 5F9C
ip 0089
CPU 80486
c=1
z=0
s=1
o=1
p=0
a=1
i=1
d=0
Variables
a 28912 (70F0h)
b 36860 (8FFCh)
c 's' 115 (73h)
ost ' ' 0 (00h)
rez ' ' 0 (00h)
start @5F9C:0000
CPU 80486
ax 5F9B
bx E0F4
cx 0000
dx 0000
si 0000
di 0000
bp 0000
sp 0280
ds 5F9B
es 5F63
ss 5F73
cs 5F9C
ip 0005
Далее приведен листинг LOG - файла при обработке исключительной ситуации - делении на ноль
Turbo Debugger Log
Variables
a 208 (D0h)
b 65516 (FFECh)
c ' ' 0 (00h)
ost ' ' 0 (00h)
rez ' ' 0 (00h)
start @5F9C:0000
CPU 80486
ax 5F9B
bx 00D0
cx 0000
dx 0000
si 0000
di 0000
bp 0000
sp 0280
ds 5F9B
es 5F63
ss 5F73
cs 5F9C
ip 0009
CPU 80486
c=0
z=0
s=0
o=0
p=0
a=0
i=1
d=0
CPU 80486
ds:0000 D0 00 EC FF 00 00 00 00 ¦ ь
ds:0008 00 00 00 00 00 00 00 00
ds:0010 B8 9B 5F 8E D8 8B 1E 00 ¬Ы_О+Л_
ds:0018 00 2B 1E 02 00 70 70 83 +__ ppГ
CPU 80486
ax 0001
bx 00E4
cx 0000
dx 0000
si 0000
di 0000
bp 0000
sp 027E
ds 5F9B
es 5F63
ss 5F73
cs 5F9C
ip 0089
CPU 80486
c=0
z=1
s=0
o=0
p=1
a=0
i=1
d=0
CPU 80486
ds:00...
www.tnu.in.ua
