Теория автоматов. Ответы на вопросы экзамена. Теория автоматов ответы к экзамену. Вопросы к экзамену Строки. Префиксы, суффиксы, подстроки. Формальные языки

• Название: Вопросы к экзамену Строки. Префиксы, суффиксы, подстроки. Формальные языки
• Анкор: Теория автоматов. Ответы на вопросы экзамена
• Дата: 03.01.2023
• Размер: 4.63 Mb.
• Имя файла: Теория автоматов ответы к экзамену.docx
• Тип: Вопросы к экзамену; #871438
• страница: 1 из 4

Вопросы к экзамену

1. 
   Строки. Префиксы, суффиксы, подстроки. Формальные языки.
   
2. 
   Дерево вывода. Синтаксическое и семантическое деревья. Примеры.
   
3. 
   Контекстная грамматика. Контекстно-свободная грамматика.
   
4. 
   Регулярные грамматики и конечный автомат.
   
5. 
   Эквивалентность автоматов.
   
6. 
   Аксиомы и основные теоремы булевой алгебры
   
7. 
   Теорема о структурной полноте В.М.Глушкова.
   
8. 
   Канонический метод структурного синтеза автоматов (Модель дискретного преобразователя В.М.Глушкова)
   
9. 
   СДНФ и СКНФ
   
10. 
    Синтез автомата на D- и RS-триггерах.
    
11. 
    СНФ в базисе «Стрелка Пирса» и «Штрих Шеффера»
    
12. 
    Графический метод структурного синтеза автоматов.
    
13. 
    Свойства функций «Исключающее ИЛИ», «Импликция от У к Х».
    
14. 
    Синтез комбинационных схем на ПЗУ.
    
15. 
    Свойства функций «Штрих Шеффера», «Стрелка Пирса».
    
16. 
    Дешифратор в цепи ОС структурного автомата.
    
17. 
    Классы логических функций.
    
18. 
    Теорема Поста-Яблонского.
    
19. 
    Состязания (гонки) в автоматах.
    
20. 
    Аппаратные противогоночные средства: импульсная синхронизация, двойная память, апериодические схемшы.
    
21. 
    Связь между моделями Мура и Мили.
    
22. 
    Базисы логических функций.
    
23. 
    Абсолютно минимальные формы представления ФАЛ.
    
24. 
    Построение комбинационной схемы автомата. Ограничения по базису, по количеству входов и выходов.
    
25. 
    Полнота переходов и полнота выходов автомата Мура.
    
26. 
    Синтез комбинационных (n,k)-полюсников
    
27. 
    Элементарные автоматы.
    
28. 
    Минимизация сложности комбинационных схем: аналитический метод, метод Карт Карно (3,4,5 переменных).
    
29. 
    Понятие базиса логических функций. Примеры.
    
30. 
    Минимизация сложности комбинационных схем: метод Квайна-Мак-Класски
    
31. 
    Типовые функциональные узлы для синтеза комбинационных схем: дешифраторы, мультиплексоры.
    
32. 
    Типовые функциональные узлы для синтеза комбинационных схем - ПЗУ.
    
33. 
    Синтез комбинационных схем по не полностью определенным ФАЛ.
    
34. 
    Синтез комбинационных схем на 2-х и 3-х входовых элементах «Штрих Шеффера» по заданной ДНФ.
    
35. 
    Синтез комбинационных схем на дешифраторах и мультиплексорах.циклы
    
36. 
    Соединения автоматов: последовательное, параллельное.
    
37. 
    Соединение автоматов с обратной связью.
    
38. 
    Синтез схем по временным булевым функциям
    
39. 
    Синтез и анализ последовательностных автоматов
    
40. 
    Циклы и тупиковые состояния в последовательностных автоматах.
    
41. 
    Форма Бэкуса-Наура, применение БНФ при синтаксическом разборе предложений.
    
42. 
    Синтез комбинационных схем на 2х- и 3х входовых элементах «Стрелка Пирса» по заданной КНФ
    
43. 
    Определение абстрактного автомата. Автоматы Мура и Мили.
    
44. 
    Способы задания автоматов.
    
45. 
    Связь между моделями Мура и Мили.
    
46. 
    Структурный автомат, интерпретация состояния автомата состояниями элементов памяти.
    
47. 
    Элементарные автоматы: RS-, D-, DV-триггеры
    
48. 
    Элементарные автоматы: JK-, T-,триггеры
    
49. 
    Реакции автоматов Мили и Мура. Примеры.
    
50. 
    Распознаватели цепочек символов на базе конечных автоматов
    

то, что красным выделено, не написано.
А что с инфой которая есть? она полная?
Где-то да, где-то нет))

Всем привет, как идет подготовка?)
говно
Настраивайтесь, что отлетаем на допку

А что по красным вопросам? есть у кого


Ответы

______________________Вопрос 1_____________________

Строки. Префиксы, суффиксы, подстроки. Формальные языки
Строка – это конечная последовательность символов а₁, а₂,…,а_n, каждый из которых принадлежит некоторому конечному алфавиту Σ, при этом символы в строке могут повторяться.

Пустой строкой называют ε-строку ее длина-ноль, т.е. без единого символа. (не=пробелу). |x|=m-длина строки, т.е. строка содержит m символов.

Пусть Σ(сигма)-некоторый алфавит, обозначим Σ^* множество определённых над этим алф-м строк. Для Σ={0,1}; Σ^*= {ε,0,1,01,11,10,101,…} видно, что н-во Σ^* - представляет собой бесконечное счетное мн-во элем-в, ε-строка всегда Σ^*

Пусть существует строка х Σ^* и |x|=m

Пусть существует строка y Σ^* и |y|=n, тогда объединение строк ху им.длину |xy|=m+n – конкатенация.

Если х= а₁, а₂,…,а_m; у= b₁, b₂,…,b_n то |xy|= а₁а₂…а_mb₁b₂...b_n

Если некоторая срока z м.б.представлена как объединение строк х и у: z=ху, то строку х наз-т префиксом строки z, а строку у-суффиксом. Если строка z т.ч.ее м/о представить как объединение 3-х строк z=xwy, то строка w н-ся подстрокой строки z.

//z = аcab

префиксы: ε,a,ac,aca,acab

суффиксы: ε,b,ab,cab,acab

подстроки: ε,a,b,c,ac,ca,ab,aca,cab,acab

Формальным языком L над алфавитом Σ н-ся произвольное подмн-во множества Σ^*.

Если L₁ и L₂ это 2а формальных языка, то их объединение есть нов.форм.язык, т.ч.L= L₁L₂{xy| хL₁,уL₂ }

// L₁={0,01} и L₂={ε,0,10}значит L= L₁L₂={0,01,00,010,010,0110}

L⁰= ε, L¹=L, L²=L*L -объединение формального языка L с самим собой:

Замыкание Клини формального языка L н-ся .Тогда , тогда L^*=L⁺U{ε}, аналогично, можно записать замыкание Клини для мн-ва строк.

______________________Вопрос 2_____________________

Дерево вывода. Синтаксическое и семантическое деревья. Примеры

Правила, определяющие мн-ва текстов образ-т синтаксис языка, а описание мн-ва смыслов и соответствий м/у текстами и смыслами – семантику языка. Если в ест.языке допуск-ся некорректности в синтаксисе и м.б.понятен смысл предложения, то в формальных языках предложение в первую очередь должно быть правильным синтаксически.

Ф-ла Бэкуса-Наура(БНФ) исп-ся для описания синтаксиса языков прогр-ия, она использует след-щие 4 символа:

1) ::= присвоить; 2) < - открыть; 3) > - закрыть; 4) | - или

//пр-р: The man drives a car.

<прост. предложение>::=<подфраза сущ.><глагол><подфр.сущ.>; <подфраза сущ-го>::=<артикль><имя сущ-ое>;

<имя сущ-ое>::= man,

<имя сущ-ое>::=car,

<артикль>::=the,

<артикль>::=a,

<глагол>::=drives

Связи, задаваемые ф-лой Б-Н м.б.представлены и графически в виде дерева-вывода:

м/о построить мн-во простых предложений, удовлетворяющих дан.структуре и синтаксически правильных, но не все они буд.им.смысл.( The car drives a man).Таким образом, в зависимости от способа грамматического разбора изменяется смысл предложения. Этот пример показывает то важное для формальных языков обстоятельство, что грамматический разбор исходного текста программы, есть важнейший шаг на пути компиляции программы.



______________________Вопрос 3_____________________

Контекстная грамматика. Контекстно-свободная грамматика

Прописные буквы нетерминальные символы языка, строчные-терминальные,

- определяется как.

Всякое дерево вывода начинается с корня S в соответствии с правилами

вывода происходит дв-е по ветвям строющегося дерева до тех пор, пока все

нетерм-е символы не буд.раскрыты ч/з терм-е.

Контексная гр-ка(К/Г) – это совокуп-ть 4х объектов: G=(N,T,P,S), где

N-конеч.мн-во нетерм.симв-в, T-кон.мн-во терм.симв, P-кон.мн-во продук-й вида α→β, где a- строка в левой части продукции, такая что α (NUT)⁺-без пустой строки, β- строка в правой части, β (NUT)*т.е. м/о получить и пуст.строку, S-начальный символ.

Если строка α (NUT)* за 1н или неск-ко шагов выводится из начального сим-ла S , то такую строку наз-т сентенциальной формой К/Г-ки G. ( - обозначает транзитивное замыкание отношения , - рефлексивное замыкание отношения)Сентенцией гр-ки G наз-т произ-ю сентенциальную форму, составл-ю из симв-в мн-ва Т*, т.е.произ.строку терм.сим-в, кот-я м.б.получена из нач-го сим-ла S. Тогда мн-во всех сентенций гр-ки G наз-т языком, пораждаемым гр-кой G и обоз-т L(G). L(G)={xТ* | }.

Если две грамматики порождают один и тот же язык, те , то гр-ки G и G^, эквивалентные. Язык грамматики- это все цепочки из терм-в, такое исп. Наз-ют выведением или порождением.

В форм. языках чаще всего в левой части продукции испол-ся 1н нетерм-й симв-л, кот-й явл-ся единс-м симв-м слева. К/Г-ка, удовл-щая этому требованию наз-ся КС/Г-ой. Строгое опред-е КС/Г-ки : гр-ка G=(N,T,P,S), в кот-й мн-во P содержит продук-ии вида α→β, где αN, β (NUT)*. Термин КС возник, т.к. люб. симв-л αN в сентанц. форме гр-ки G м.б.раскрыт согласно продукции из α→β,независимо от того, какими строками он окружен внутри самой сент. формы.

КС/Г-ку м/о представить виде дерева вывода. Корнем кот-го явл-ся нач.символ S, строка терм-х симв-в, или сентенция – последов-ть висячих вершин, читаемых в порядке слева направо. Промеж-е узлы дерева– нетерм-е верш-ны. Если для люб. строки хL(G) все возможные схемы вывода имеют одно и тоже дерево вывода, то гр-ка наз. однозначная КС/Г-кой. (S→AB; A→aA|a; B→bB|b –строка а³b²). Если одной и той же строке соотв-т разл. деревья, то гр-ка наз. неоднозна-й (S→SbS|ScS|a-строка abaca). В дан.опред-ии КС/Г-ки ее продукции им.вид: α→β, где αN, β (NUT)*. Значит корректна запись А→ε, где ε-терм. символ.

Гр-ка не им-щая ε-прод-ции наз. ε-своб-й. Было бы идеально раб-ть т/о с ε-своб-ми гр-ми. Для преобр-ия гр-ки G в гр-ку G’, кот-я ε-своб-на н/о:

1. объединить все имеющиеся в Р ε-продукции в мн-во Р’.

2. все нетерм.сим-лы, т.ч. ε. Каж.прод-ции из Р’поставим в соотв-ие такую прод-цию, что в ее прав.части, посрав-ию с исход-й прод-ей Р опущены неск-ко нетермин-х сим-в.




______________________Вопрос 4_____________________

Регулярные грамматики и конечный автомат
Регулярная грамматика — формальная грамматика типа 3 по иерархии Хомского. Регулярные грамматики определяют в точности все регулярные языки, и поэтому эквивалентны конечным автоматам и регулярным выражениям. Регулярные грамматики являются подмножеством контекстно-свободных.

Регулярная грамматика может быть задана набором правил как левая или правая регулярная грамматика.

правая регулярная грамматика - все правила могут быть в одной из следующих форм:

A → a

A → aB

A → ε

левая регулярная грамматика - все правила могут быть в одной из следующих форм:

A → a

A → Ba

A → ε

Любая регулярная грамматика G=(N,T,P,S) может быть представлена направленным графом с конечными узлами и дугами. Конечный узел помечен символом из нетерм. мн-ва N, кроме конечного #(диес)

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

______________________Вопрос 5_____________________

Эквивалентность автоматов
Две булевы функции F1 и F2 эквивалентны, если на всех возможных наборах входных переменных они принимают одинаковые значения. Поскольку число наборов у булевых функций конечно, то, перебрав их все, можно проверить, эквивалентны ли F1 и F2. Можно также привести F1 и F2 к совершенной нормальной форме и сравнить их представления.
Иная ситуация с конечными автоматами. Два конечных автомата эквивалентны, если реализуемые ими отображения вход-выход эквивалентны. Конечный автомат реализует отображение бесконечного множества входных последовательностей сигналов в бесконечное множество выходных последовательностей сигналов. Поэтому автоматные отображения нельзя сравнить простым перечислением их значений на всех возможных аргументах.
Конечные автоматы А = {XА, YА, QА, δА, λА} и В = {XВ, YВ, QВ, δВ, λВ} называются эквивалентными, если выполняются два условия:
а) их входные алфавиты совпадают: XА = XВ = X;
б) реализуемые ими автоматные отображения совпадают.

______________________Вопрос 6_____________________

Аксиомы и основные теоремы булевой алгебры

Аксиомы:

1. Аксиомы конъюнкции 0·* 0 = 0 ; 1·* 1 = 1 ; 0·* 1 = 1·* 0 = 0 ;

2. Аксиомы дизъюнкции 0 v 0 = 0 ; 1 v 1 = 1 ; 0 v 1 = 1 v 0 = 1 ;

3. Аксиомы отрицания Если x = 0 , то ˆх = 1 ;

Если x = 1 , то ˆх = 0 ;

Теоремы:
4. Операции с константами:



5. Идемпотентность (тавтология, повторение):



Для n переменных:



6. Противоречие :



7. Правило "исключенного третьего":



8. Двойное отрицание (инволюция):



Законы (тождества):

9. Ассоциативность (ассоциативный закон) :



10. Коммутативность (коммутативный закон) :



11. Дистрибутивность (дистрибутивный закон) :

конъюнкции относительно дизъюнкции:



дизъюнкции относительно конъюнкции:



12. Законы де Моргана (законы инверсии или отрицания) :



13. Поглощение :



14. Закон Блейка-Порецкого :



15. Склеивание (объединение) :



______________________Вопрос 7_____________________

Теорема о структурной полноте В.М.Глушкова

Теорема о структурной полноте Глушкова: для того, чтобы система элементарных автоматов была структурно полной необходимо и достаточно, чтобы она содержала хотя бы один автомат мура с полной системой переходов и полной системой выходов, а также функционально полную систему логических элементов. Существует приём, называемый каноническим методом структурного синтеза, который позволяет свести синтез автомата к синтезу комбинационных схем.вход

Автомат мура обладает полной системой переходов, если для любой пары состояний (ai,aj) найдётся входной сигнал, переводящий один элемент пары в другой, включая случай, когда i=j.

Если каждое состояние автомата отмечено выходным сигналом, отличным от сигналов, отмечающих остальные состояния, то автомат мура обладает полной системой выходов. Элементарным автоматом называется автомат с двумя состояниями. Логический элемент - интегральная схема реализующая булеву функцию.

______________________Вопрос 8_____________________

Канонический метод структурного синтеза автоматов (Модель дискретного преобразователя В.М.Глушкова)

Комбинационная схема (КС) может иметь несколько выходов. При каноническом методе предполагается, что каждая выходная функция реализуется своей схемой, совокупность которых и даёт требуемую КС. Поэтому синтез сложной КС с n выходами заменяется синтезом n схем с одним выходом.

Согласно каноническому методу синтез КС включает в себя ряд этапов.

1.Подлежащая реализации булева функция (или её отрицание) представляется в виде СДНФ.

2.С использованием методов минимизации определяется минимальная ДНФ (МДНФ) или минимальная КНФ (МКНФ). Из полученных двух минимальных форм выбирается более простая.

3.Булеву функцию в минимальной форме согласно п.2 представляют в заданном (или выбранном разработчиком) базисе .

4.По представлению функции в заданном базисе строят комбинационную схему.

Необходимо отметить, что подлежащая реализации булева функция F(X₁,X₂,...,X_m)может быть задана не на всех возможных наборах аргументов X₁, X₂, ..., X_m. На тех наборах, где функция неопределенна, её доопределяют так, чтобы в результате минимизации получить более простую МДНФ или МКНФ. При этом упростится и сама КС. Кроме того, довольно часто с целью получения ещё более простого представления функции МДНФ, полученная в п.2, представляется в так называемой скобочной форме, т.е. выносятся за скобки общие части импликант МДНФ.

Авт-т любой сложности представл в виде структуры,сост из 2-х частей: РИСУНОК!

В схеме след обозначения:

X₁-X_L– множ-во входных сигналов структурного авт-та

Y₁-Y_N– множ-во выходных сигналов

U₁-U_R– множ-во сигналов возбуждения ЭП

V₁-V_R– множ-во сигналов обратной связи

Теорема Глушкова(Система элементарных автоматов является структурно полной тогда и только тогда,когда содержит:1)авт-ты Мура,облад полнотой переходов и выходов. 2).комбинацион схему, построенную на функционал полной системе логических элементов. В этом случае задача структурного синтеза произвольных автоматов сводится к задаче структурного синтеза комбинационных схем).

В соответ-ии с теоремой Глушкова задача синтеза структурного автомата состоит в построении комбинаций части. Математически это записыв-ся так:

y₁ = y₁(x₁,x₂,…,x_L,V₁,V₂,…,V_R)…

y_N = y_N(x₁,x₂,…,x_L,V₁,V₂,…V_R)

U₁ = U₁(x₁,x₂,…,x_L,V₁,V₂,…V_R)…

U_R = U_R(x₁,x₂,…,x_L,V₁,V₂,…V_R).

Т.о., задача синтеза структурного авт-та сводится к составлению и решению этой системы логических уравнений.

______________________Вопрос 9_____________________

СДНФ и СКНФ

Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ, в которой нет одинаковых элементарных конъюнкций и все конъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно, с отрицанием).

Совершенной конъюнктивной нормальной формой (СКНФ) называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все дизъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно, с отрицанием).

Алгоритм приведения к СДНФ и СКНФ:

Рассмотрим логическую функцию в виде таблицы истинности.



Алгоритм построения СДНФ по таблице истинности выглядит следующим образом:

1. 
   Отметить наборы переменных, значение функции F на которых равно
   
2. 
   Записать для всех отмеченных наборов конъюнкцию всех переменных так: если значение некоторой переменной в этом наборе равняется 1, в конъюнкцию включается сама переменная. В случае противного результата, в конъюнкцию включается ее отрицание.
   
3. 
   Связать полученные конъюнкции операциями дизъюнкции.
   

Построим СДНФ:



И как результат получим следующую СДНФ:





_____________________Вопрос 10_____________________

Синтез автомата на D- и RS-триггерах


_____________________Вопрос 11_____________________

СНФ в базисе «Стрелка Пирса» и «Штрих Шеффера»





отрицаем, где 0

Для обозначения логических принципиальных схемах используют спец изображения



_____________________Вопрос 12_____________________

Графический метод структурного синтеза автоматов