All posts by admin

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

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

Вопрос 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}.

1. Автомат. Подходы к определению и изучению автоматов. Концепция порождения и распознавания. Применение теории автоматов. 2. Знак. Символ. Алфавит. Множество универсум. Слово. Строка. Конкатенация. Формальный язык. Операции над формальными языками. 

Определение LL(k)-грамматик. Для начала предположим, что G=(N,E,P,S) — однозначная грамматика и w=a1,a2…an — цепочка из L(G). Тогда существует единственная последовательность левовыводимых цепочек b0,b1..bm, для которой S=b0,bi,pi ? bi+1 при 0<=i<m и am=w. Последовательность p0p1..pm-1 -левый разбор цепочки w.

Учебное пособие для вузов Рекомендовано научно-методическим советом Приднестровского государственного университета в качестве учебного пособия для студентов высших технических учебных заведений

Занятие 1.1. Формальные языки Задача 1 Задан алфавит и строка над этим алфавитом. Перечислить префиксы, суф¬фиксы и подстроки строки . Оценить, сколькими способами для строки дли¬ной можно выбрать суффикс, префикс и подстроку.

Занятие 2.1. Машина Тьюринга (МТ) Задача 23 МТ задана таблицей. 

Занятие 3.1. Минимизация автоматов Задача 39 КА задан в виде графа.

Занятие 4.1. Синтез комбинационных автоматов Задача 45 Заданы два КА и в виде автоматных таблиц. Построить КА , эквивалентный последовательному соединению автоматов и .