Вопрос 1. Автомат. Подходы к определению и изучению автоматов. Концепция порождения и распознавания. Применение теории автоматов.
Теория автоматов специальный раздел дискретной математики изучающий математические модели преобразователей дискретной информации (данных).
Неформальное определение автоматов: Автоматом называется формальная система (гипотетическое устройство) имеющее входной и выходной каналы данных и находящийся в каждый из дискретный момент времени в одном из состояний.
Потребуем, чтобы множество входных сигналов, выходных сигналов и внутренних состояний было конечным.
Предмет “Теория автоматов”. Предметом является 2 типа объектов: 1) реальные устройства; 2) математические модели (это математические машины, алгоритмические теории).
Подходы — методы к изучению автоматов. 1) Микроподход — изучается внешнее поведение автоматов (внешнее функционирование). Рассматривается как автомат перерабатывающий входные сигналы в выходные и в каких состояниях он при этом находится, отвлекаясь от внутреннего его строения. (абстрактный автомат). 2) Макроподход — учитывается структура автомата, их функционирование и связь между собой. Автомат при таком подходе будем называть структурным автоматом (автоматная схема и сеть из автоматов). I. Структурный автомат задается конечным множеством абстрактных автоматов; II. конечной схемой их соединения и указанием влияния частей схемы друг на друга. 3) Практический подход — учитывается не только внешнее поведение элементарных автоматов входящих в структурный автомат (устройство), но и особенности реализации этого автомата в виде реального дискретного устройства.
Концепция порождения и распознавания.
Автомат-акцептор — абстракция автомат при которой он рассматривает как устройство при котором он может отличать конечные последовательности входных данных с помощью выходных данных (концепция распознавания).
Автомат-преобразователь — это абстрактный автомат, при котором он рассматривает как устройство преобразующее последовательность входных последовательностью выходных данных.
Пример: компилятор.

Вопрос 2. Знак. Символ. Алфавит. Множество универсум. Слово. Строка. Конкатенация. Формальный язык. Операции над формальными языками. Итерация и зацикливание формального языка.
Символ — знак вместе с сопоставленной ему информацией (смыслом). Алфавит — упорядоченное множество знаков. Множество универсум (А*)- множество всех конечных строк в алфавите А в объединении с пустой строкой (е). A={a,b} A*={e,a,b,aa,ab,ba,bb,…}. Множество универсум без пустой строки — A+={a,b,aa,ab,ba,bb,…}. Слово — строка вместе с сопоставленной ей информацией (смыслом). Строка (цепочка).
Конкатенация — ?x,y ? A* ?z ? A*;
z=xy , x=x1x2…xn xi?A , y=y1y2…yn yi?A
z=x1x2…xny1y2…ym=z1z2…zn+m; zi?A
Свойства конкатенации:
1. Единица алгебры строк: ex=xe=x , x?A* ; 2. Ассоциативность: (xy)z = x(yz) , ?xyz ?A* ; 3. Не коммутативность: xy ? yx, если x ? y , xy ? e , xy ?A* ;
4. Строка как конкатенация знаков: ?x ?A* , x=x1x2…xn; xi?A
Префикс — суффикс
?xy ?A* , x?A* , y?A*; x — префикс, y — суффикс.
Пример: abcc A={a,b,c}
Префикс : e, a, ab, abc, abcc ; Суффикс: e, c, cc, bcc, abcc
Подстрока ?x ? ??? , где ?, ?, ? ? A* , ? — подстрока.
Формальный язык — любое подмножество множества универсум.
Формальный язык L над алфавитом A — это произвольное подмножество множества A*; L ? A*. Пример: Язык трехразрядный двоичных чисел. A = {0, 1}
L = {000, 001, 010, … , 111}
Операции над формальными языками.
1. Конкатенация: L = L1L2 = {xy | x ? L1 , y ? L2}; L1 , L2 ? A* 2. Объединение: {e}L = L{e} = L 3. Ассоциативность: (L1L2) L3 = L1 (L2L3) 4. Не коммутативность: L1L2 ? L2L1 , если L1 ? L2 , L1 , L2 ? {e} , L1 , L2 ? A* 5. 0L = L0 = 0