Category Archives for Теория автоматов

Определение: Асинхронным автоматом называется конечный автомат все составляющие которого, устойчивы по всем входным знакам. Это означает, что для всех состояний и .

Определение: Произвольный асинхронный автомат может быть представлен ( реализован ) автоматной сетью, состоящей из двух комбинационных автоматов ? и ? ( без линии задержки ).

Определение: Элемент задержки на один такт, используемый в теореме о структурном синтезе автомата КА, — является асинхронным автоматом.

Представим схему, полученную в результате структурного синтеза синхронного автомата.

DL – триггер. Рассмотрим пример синтеза асинхронного автомата, который называется DL – триггером.

Дискретное устройство – это устройство, функционирующее в дискретные моменты времени и обрабатывающее дискретные сигналы.

Комбинационной схемой называется сеть из логических элементов, реализующая некоторый комбинационный автомат. Следовательно, комбинационная схема реализует однозначное соответствие между значениями входных и выходных сигналов.

Идея теоремы состоит в том, что одни и те же схемы можно организовать по-разному:

Ранее было показано, что автоматы можно разделить на: • комбинационные • асинхронные • синхронные

У асинхронных потенциальных автоматов входные сигналы оказывают потенциальное воздействие на схему, т.е. смена сигнала на входе задает такты функционирования автомата, а сами сигналы воздействуют на него все время.

Синтез синхронных автоматов, свободных от критических состязаний. Введение тактового сигнала позволяет исключить из рассмотрения переходные процессы.

Вопрос 1. Автомат. Подходы к определению и изучению автоматов. Концепция порождения и распознавания. Применение теории автоматов. Теория автоматов специальный раздел дискретной математики изучающий математические модели преобразователей дискретной информации (данных).

Вопрос 3. Формальная грамматика. Терминальный и нетерминальные знаки. Продукция. Сентенциальная форма. Формальной грамматикой G называется алгебраическая система G = < V, W, P, I > , где V — алфавит терминальных знаков (основных) , W — алфавит нетерминальных знаков (вспомогательных) , P — множество продукций (правил вывода) , I — аксиома грамматики (начальный знак) , Читать далее

Вопрос 6. Лемма о виде продукции формальных грамматик. Теорема об е-свободной КС-грамматике. Грамматики свободные от пустой строки или e-свободные грамматики.

Вопрос 7. Теорема о приведении КС-грамматики. 1. Достижимым, называется такой нетерминальный знак A?W, что существует вывод I ?G ? A ? , где ?, ? ? (V?W)*. 2. Производящим называется нетерминальный знак A?W, если существует вывод A?G ? , где ? ? V*.

Вопрос 9. Разрешимость языков. Теоремы о разрешимости языков, заданных произвольной и не укорачивающей грамматикой.

Вопрос 12. Машина Тьюринга. Способы задания машины Т. Конфигурация. Тезис Тьюринга. Определение: МТ — это алгоритмическая модель представляющая собой некоторое идеализированное устройство. Существует наиболее распространенные 3 типа универсальных моделей: 1) детерминированные устройства: МТ , машина Поста (процедурное программирование); 2) рекурсивные функции, 3) формальные системы.

Вопрос 13. Вычислимость по Тьюрингу. Операции над МТ. Тезис Тьюринга: Любой алгоритм может быть реализован МТ. Замечание: Тезис Т. невозможно ни доказать, ни опровергнуть, это некоторое утверждение, которое связывает мат. теорию с объектами для которых эта теория предназначена.

Вопрос 18. Теорема об универсальной машине Т. Теорема Шеннона и Боброу-Минского. Универсальная МТ — это такая МТ U реализующая систему команд любой другой МТ. T=< V, Q, P, I > U=< Vu, Qu, Pu, Iu > Iu=qu1P || q1?

Вопрос 20. Теорема Райса. Теорема 2.6. Никакое нетривиальное свойство вычислимой функции не является алгоритмически разрешимым. Доказательство:

Вопрос 23. Тезис Поста. Теорема о распознавании и порождении языков, заданных произвольными грамматиками. ТЕЗИС ПОСТА : грамматика типа 0 может быть представлена как МТ .

Вопрос 25. Сеть Петри. Способы задания и функционирование. Языки сети Петри. В чистом виде СП не является автоматом типа 1 . СП – некая абстрактная модель . Условие реализации события . те ситуацией при которых данное событие может произойти будем обознчать О .

Вопрос 26. Свободный, префиксный и терминальный языки сети Петри. Теорема о мощности классов языков сети Петри. Свободный Язык СП : S –это множество последовательностей срабатывания ? переходов сети S 

Вопрос 27. Магазинный автомат. Детерминированный и недетерминированный магазинный автомат. Теорема о магазинном автомате и КС-языках. СП- не является автоматом типа 1 Магазинный автомат –(М ) – совокупность пяти (шести ) объектов М=<A,Q,S,P,I,(B)>

Вопрос 33. Конечный автомат и регулярные языки. Теорема 3.6 «О конечных автоматах и регулярных языках» Для любого языка, заданного регулярной грамматикой существует конечный автомат возможно недетерминированный, принимающий множество строк, совпадающих с этим языком. Верна и обратная: для любого конечного автомата множество принимаемых им строк может быть описано регулярной грамматикой.

Вопрос 36. Теорема о минимизации КА. Алгоритм Мили. Эквивалентным преобразованием называется переход от автомата K к автомату K’ который неотличим от исходного. Постановка задачи минимизации : среди автоматов неотличимых от автомата K найти автомат Ko с наименьшим числом состояний. 

Вопрос 39. Теорема о представимости регулярных языков конечными автоматами. Теорема 3.3. Для любого непустого языка L порождаемого регулярной грамматикой G3, существует КА К, возможно недетерминированный, представляющий ( порождающий и распознающий) язык L. ? L=L(G3), L? {e};

Вопрос 42. Источник. Источник и регулярный язык. Теорема о детерминации КА. Теорема : ( детерминация КА). Для любого недетерминированного КАвтомата K=< A,Q,B,?,?> сущ. Эквивалентный ему детерминированный КАвтомат K1=< A,Q,B,?1,?1> имеющий не более чем 2^n состояний ( n=|Q| , |Q1|=2^|Q| =2^n). ДОК-ВО : 1). Кпр=< A,Q,B,?,?>

Вопрос 45. Терема о структурном синтезе КА. Пусть задан некоторый КА в общем виде K=<A,Q,B,???>. Теорема 4.2.: Любой К. автомат K может быть реализован сетью из ??? и элемента задержки D с не более , чем |Q| состояниями. b(t)=?(q(t), a(t)) q? (t) = ? (q(t), a(t))

Вариант №6 Задание №1 (20 б): Является ли грамматика: G=<{a,b,c}, {A,B,C}, D, A} LL(k) грамматикой, где k<3 и P={A?b | bc | BC, B?a | b, C? aac}.