1. Инцидентность вершин и ребер
2. Смежность вершин и ребер
3. Ребро, ориентированное ребро, петля, кратное ребро
4. Изолированная вершина, висячая вершина и висячее ребро
5. Простой граф, ориентированный граф
6. Мультиграф, псевдограф
7. Взвешенный, направленный граф
8. Нуль граф, пустой граф, тривиальный граф
9. Изоморфизм графов. Помеченный граф
10. Способы представления графа.
11. Описание кратных ребер и петель в матрице смежности
12. Описание кратных ребер и петель в матрице инцидентности
13. Степень вершины в графе (ориентированный и неориентированный графы)
14. Лемма о рукопожатиях для неориентированного графа
15. Лемма о рукопожатиях для ориентированного графа
16. Подграф
17. Надграф
18. Собственный подграф, Несобственный подграф
19. Частичный граф.
20. Регулярный (однородный) граф, полный граф
21. Дополнение, объединение, пересечение графов
22. Путь. Цепь. Простая цепь
23. Замкнутый путь, цикл и простой цикл
24. Двудольный граф. Критерий двудольности
25. Вершинно простой путь, Реберно простой путь
26. Лемма о простом пути
27. Связность в неориентированном графе, компоненты связности. Связный граф
28. Слабая связность, компоненты слабой связности. Слабо связный граф
29. Сильная связность, компоненты сильной связности. Сильно связный граф
30. Реберная двусвязность. Компоненты реберной двусвязности. Минимальная компонента
31. Разрезающее множество. Разрез
32. Мост определение + 2 эквивалентных определения на выбор
33. Лемма о цикле и мосте
34. Лемма про удаление моста
35. Вершинная двусвязность. Компоненты вершинной двусвязности. Минимальная компонента
36. Блок определение (через неразделимый подграф) + 1 из эквивалентных определения на выбор
37. Точка сочленения: 2 эквивалентных определения
38. Лемму о точке сочленения на выбор любая
39. Эксцентриситет
40. Радиус, Диаметр и центр
41. Планарный граф
42. Грань планарного графа
43. Формула Эйлера
44. Необходимые условия планарности
45. Критерий планарности
46. Дерево ( 2 определения)
47. Граф блоков и точек сочленения
48. Граф компонент реберной двусвязности
49. Остов графа
50. Цикломатическое число
51. Цикл, ассоциированный с остовом
52. Фундаментальная система циклов
53. Минимальное остовное дерево
54. Безопасное ребро
55. Разрез
56. Ребро пересекающее разрез
57. Лемма о безопасном ребре
58. Расстояние между двумя вершинами графа
59. Кратчайший путь между двумя вершинами
60. Лемма о белых путях
61. Эйлеров путь
62. Отличие эйлерова и полуэйлерова графов
63. Эквивалентные определения эйлерова графа
64. Теорема о покрытии ребер графа путями
65. Критерий эйлеровости
66. Произвольно вычерчиваемый граф
67. Теорема о произвольно вычерчиваемом графе
68. Принцип построения Произвольно вычерчиваемого графа
69. Гамильтонов путь, полугамильтонов граф
70. Гамильтонов граф, гамильтонов цикл
71. Теорема Оре
72. Теорема Дирака
73. Теорема Гуйя-Ури
74. Для любого ли гамильтонова графа будут выполняться условия теорем о гамильтоновости и почему?

1. Метод математической индукции
2. Определение сочетания (не формулой)
3. Формулы для сочетаний без повторений
4. Формулы для сочетаний с повторениями
5. Определение размещения (не формулой)
6. Формулы для размещений без повторений
7. Формулы для размещений с повторениями
8. Определение перестановки (не формулой)
9. Формула перестановок без повторениями
10. Формула перестановок с повторениями
11. Отличие перестановок и размещений
12. Принцип Дирихле
13. Принцип сложения
14. Принцип умножения
15. Принцип включения-исключения - формула
16. Лексикографический порядок на строках
17. Формирование следующей в лексикографическом порядке перестановки
18. Формирование следующего в лексикографическом порядке сочетания той же длины
19. Теорема об эквивалентности формул задающих сочетания (правило симметрии)
20. Теорема Вандермонда
21. Следствие из теоремы Вандермонда
22. Биномиальная теорема
23. Теорема о сумме сочетаний (следствие из биномиальной)
24. Теорема о коэффициентах биномиального треугольника
25. Алфавит, символ
26. Слово / цепочка
27. Длина цепочки
28. Пустая цепочка
29. Степень алфавита
30. Степень языка
31. Конкатенация цепочек
32. Конкатенация языков
33. Замыкание Клини
34. Формальный язык
35. Множество регулярных языков
36. Регулярное выражение
37. Регулярный язык
38. Детерминированный конечный автомат
39. Недетерминированный конечный автомат
40. Язык автомата
41. Теорема Клини

x — ребро с концами u и v, {u, v}, тогда x инцидентно u и v, u и v инцидентны x

вершины u и v называются смежными, если являются концами одного ребра

ребра x и y называются смежными, если имеют общую вершину

Ребро - неупорядоченная пара {u, v}, где u, v принадлежат V - множеству вершин графа

Ориентированное ребро - упорядоченная пара {u, v}, где u, v принадлежат V - множеству вершин графа

Петля - ребро, соединяющее вершину с самой собой

Кратное ребро: ребро a - кратно ребру b, если a и b соединяют однии те же вершины

Изолированная вершина — вершина без петель также не являющаяся концом ни одного из ребер

Висячая вершина — вершина, в которую вдет только одно ребро, которое в свою очередь также называется висячим

Висячее ребро - ребро, инцидентное висячей вершине

Простой граф - граф, не содержащий кратных ребер и петель

Ориентированный граф - множество вершин V и ориентированных ребер E

Мультиграф — граф с параллельными ребрами

Псевдограф — граф, который может содержать:

• петли
• и/или параллельные ребра

Взвешенный граф — граф, в котором каждое ребро имеет вес.

Направленный граф — граф без симметричных ориентированных ребер (дуг).

Нуль граф - граф без ребер

Пустой граф - граф без вершин

Тривиальный граф - граф из одной вершины

Графы G и G' изоморфны — между их множествами вершин существует взаимно-однозначное соответствие с сохранением смежности

Помеченный граф - граф, в котором вершины отличаются друг от друга пометками

1. Диаграмма

2. Список смежности

3. Матрица смежности — матрица A [V x V] , в которой в ячейке a_ij записано:

• (неориентир.): число ребер, соединяющих вершины V_i и V_j.
• (ориентир.): a_ij = 1, если из V_i в V_j идет дуга, иначе 0

4. Матрица инцидентности

• для неориентированного графа — матрица A размера |V|x|E|, для которой a_ij = 1, если вершина v_i инцидентна ребру e_j, иначе a_ij = 0
• Матрица инцидентности (для ориентированного графа) — матрица A размера |V|x|E|, для которой a_ij = 1, если > вершина v_i начало дуги e_j, a_ij = -1, если вершина v_i конец дуги e_j, иначе a_ij = 0

Матрица смежности:

В неориентированном графе кратные ребра кратно увеличивают значения в симметричных ячейках (i, j) и (j, i).

Если i = j, то в неориентированном графе петля учитывается дважды.

В ориентированном графе кратные дуги кратно увеличивают значение в ячейке (i, j).

Если i = j, то в ориентированном графе петля учитывается единожды.

очев. (см. определение)

в неориентированном: число ребер, инцидентных этой вершине

в ориентированном:

• степень входа (deg_+) - число входящих ребер
• степень выхода (deg_-) - число исходящих ребер

Сумма степеней всех вершин графа — четное число, равное удвоенному числу ребер графа.

Следствие: произвольный граф содержит четное число вершин нечетной степени.

Сумма входящих и исходящих степеней всех вершин графа — четное число, равно удвоенному числу дуг графа.

Граф G'(V', E') является подграфом G(V, E), если V' ⊆ V, E' ⊆ E. Таким образом каждая вершина или ребро подграфа являются вершиной или ребром исходного графа.

Надграф — граф, полученный путем добавления новых ребер и/или вершин в исходный граф.

Собственный подграф - не пустой и не совпадающий с исходным подграф

пустой или совпадающий с исходным подграф

Частичный граф — состоящий из множества вершин исходного графа и подмножества множества ребер.

Каждый граф частичен сам себе.

Регулярный (однородный) граф — такой граф что степени всех его вершин равны.

• Cтепень регулярности — степень вершины регулярного графа.

Полный граф - простой граф с максимальной степенью вершин

Дополнение графа до полного — добавляет в исходный граф ребра до полного и удаляет ребра исходного.

Объединение графов G(V, E) и G'(V', E') — объединяет множества вершин и ребер этих графов

Пересечение графов G(V, E) и G'(V', E') — пересекает множества вершин и ребер этих графов

Подразбиение ребра — операция, состоящая из удаления ребра e_0 = (u, v) и добавления двух новых ребер e_1 = (u, q), e_2 = (q, v) где q — новая вершина степени 2.

Если v и v' — вершины различных компонент графа G, то мы можем создать новый граф G' путём отождествления v и v' в G в новую вершину v в G'. Ребро инцидентное v и v' переходит в петлю.

Путь — последовательность вида v_1, e_1, v_2, e_2, ... v_n, e_n, v_n+1 где e_i ∊ E, v_i ∊ V.

Цепь — путь без повторяющихся ребер.

Простая цепь — цепь без повторяющихся вершин (а следовательно и ребер).

Замкнутый путь — такой путь, что его конец и начало совпадают (v_1 = v_n+1).

Цикл — замкнутая цепь.

Простой цикл — замкнутая простая цепь n ≥ 3.

Двудольный граф — это граф, множество вершин которого можно так разбить на два непересекающихся подмножества (доли) V_1 и V_2, что никакие две вершины из одной доли не смежны.

Критерий двудольности: граф является двудольным тогда и только тогда, когда все циклы в графе имеют чётную длину.

Вершинно простой путь - путь, в котором каждая из вершин графа встречается не более одного раза

Реберно простой путь - путь, в котором каждое из ребер графа встречается не более одного раза

Если между двумя вершинами графа - u, v существует (u, v) - путь, то существует и простая (u, v) - цепь

Вершины u и v связаны, если в графе существует путь u --> v.

Компонента связности это максимальный по включению связный подграф.

Граф связен, если состоит из одной компоненты связности. В противном случае граф называется несвязным.

Связность — отношение эквивалентности.

Слабая связность пары вершин — вершины связаны в неориентированном варианте исходного графа

Компонента связности это максимальный по включению слабо связный подграф

Ориентированный граф G связен, если состоит из одной компоненты слабой связности

Сильная связность пары вершин — есть как путь u --> v, так и v --> u.

Компонента связности это максимальный по включению сильно связный подграф

Граф G сильно связен, если состоит из одной компоненты сильной связности

Минимальная компонента сильной связности – вершина!

Вершины u и v графа G называются реберно двусвязными, если между ними существует два реберно непересекающихся пути.

Компоненты - подграфы, множества вершин которых - классы эквивалентности реберно двусвязности, а множества ребер - множества ребер из соответствующих классов эквивалентности

Минимальная компонента - вершина

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

Разрез — минимальное по включению разрезающее множество графа.

Мост — ребро, при удалении которого, граф становится несвязным.

Эквивалентные определения

1. Мост — ребро, соединяющее две компоненты реберной двусвязности
2. Ребро x — мост в графе G, если существует разбиение множества вершин V на два подмножества U и W такие, что для любых u ∈ U и w ∈ W ребро x принадлежит любому простому пути (u, w)
3. Ребро x — мост в графе G, если существуют такие вершины u и w, что любой простой путь между этими вершинами проходит через x

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

При удалении моста число компоненты связности увеличивается на единицу

Ребра графа являются вершинно двусвязными, если существуют два вершинно непересекающиеся пути, соединяющие их концы.

Компоненты - блоки (подграфы, множества ребер которых - классы эквивалентности вершинной двусвязности, а множества вершин - множества концов ребер из соответствующих классов)

Минимальная компонента - ребро

Блок — максимальный неразделимый подграф (связный граф неразделим, если не содержит точек сочленения)

G — связный граф, содержащий не менее трех вершин Тогда эквивалентно:

1. G — блок
2. любые вершины u и v принадлежат некоторому общему циклу
3. в G любые вершина и ребро (не петля) принадлежат некоторому общему циклу
4. в G любые 2 ребра (не петли) принадлежат общему циклу
5. в G для любых 2 вершин и ребра (не петля) существует простая цепь, соединяющая эти вершины и проходящая через это ребро
6. в G для любых вершин u, v и w существует простая (u, w) -цепь, проходящая через v
7. в G для любых вершин u, v и w существует простая (u, w) -цепь, которая не проходит через v

1. Точка сочленения — вершина, при удалении которой, увеличивается число компонент связности.

2. Вершина, принадлежащая как минимум двум блокам

Лемма 1

Пусть v произвольная вершина связного не одноэлементного графа. Тогда эквивалентно:

1. v — точка сочленения
2. существуют различные u и w не равные v, т.ч. v принадлежит любой простой (u, w) −цепи
3. существует разбиение множества вершин G - v на два непустых подмножества U и W такое, что для любых u ∈ U и w ∈ W : v принадлежит любой простой (u, w) −цепи

Лемма 2

Любые 2 блока связного графа G имеют не более одной общей вершины

Лемма 3

Пусть G — блок, содержащий не менее трех вершин, тогда любые две его вершины принадлежат некоторому общему циклу

Лемма 4

Пусть G - блок, содержащий не менее трех вершин, тогда любые его вершина и ребро лежат на некотором общем цикле

Эксцентриситет v — расстояние до самой дальней от v вершины графа.

Радиусом графа называется минимальный эксцентриситет среди всех его вершин

Диаметром графа называется максимальный эксцентриситет среди всех вершин графа

Центр - вершина, эксцентриситет которой равен радиусу.

Планарным называется граф, который можно уложить на плоскости

граф укладывается на поверхности S, если его можно нарисовать на S, что никакие два его ребра не пересекаются

Грань планарного графа - максимальный участок плоскости, такой, что любые точки этого участка могут быть соединены кривой, не пересекающей ребро графа.

Харари: области, на которые граф разбивает плоскость, называются гранями. Неограниченная область называется Внешней гранью.

Для произвольного плоского связного графа G с V вершинами, E ребрами и F гранями справедливо следующее соотношение:

V − E + F = 2

1. Для любого простого связного планарного графа с V вершинами и E ребрами, где V ≥ 3, выполняется неравенство E ≤ 3V − 6
2. В любом планарном графе есть вершина, степень которой не превосходит 5
3. Для любого простого связного планарного двудольного графа с V вершинами и E ребрами, где V ≥ 3, выполняется неравенство E ≤ 2V − 4

Критерий планарности Понтрягина-Куратовского:

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных графам K_5 или K_3,3

Связный ациклический граф

Граф, в котором любые две вершины соединены единственным простым путем

Двудольный граф, где одна доля — точки сочленения, другая — блоки, сжатые в виде вершин.

Cвязный граф, где компоненты реберной двусвязности сжаты в виде вершин и соединяются мостами исходного графа.

Cвязный, ацикличный, частичный граф исходного графа.

Количество ребер, которые необходимо удалить, чтобы получить остов

Цикл, полученный добавлением к остову ребра исходного графа, не принадлежащего остову

Множество циклов графа, ассоциированное с остовом (полученное путем поочередного добавления каждого ребра из множества удаленных ребер к остову).

Минимальное остовное дерево графа G = (V, E) — это его ациклический связный подграф, в который входят все его вершины, обладающий минимальным суммарным весом ребер.

Пусть G' — подграф некоторого минимального остовного дерева графа G = (V, E).

Ребро (u, v) ∉ G' называется безопасным, если при добавлении его в G', G' ∪ {(u, v)} также является подграфом некоторого минимального остовного дерева графа G.

Разрезом неориентированного графа G = (V, E) называется разбиение V на два непересекающихся подмножества: S и T = V ∖ S. Обозначается как ⟨S, T⟩.

Ребро (u, v) ∈ E пересекает разрез ⟨S, T⟩, если один из его концов принадлежит множеству S, а другой — множеству T.

Рассмотрим произвольный разрез какого-либо подграфа минимального остова. Тогда ребро минимального веса, пересекающее этот разрез, является безопасным.

Расстояние между u и v - d(u, v) — длина минимального маршрута из u в v.

Путь с минимальным суммарным весом ребер

Не существует такого момента выполнения поиска в глубину, в который бы существовало ребро из черной вершины в белую.

• если вершина белая, значит, мы в ней еще не были, вершина не пройдена;
• серая — вершина проходится в текущей процедуре dfs
• черная — вершина пройдена, все итерации dfs от нее завершены.

Эйлеров путь - проходит через все ребра графа по одному разу

Эйлеров граф — содержит эйлеров цикл

Полуэйлеров граф — содержит эйлеров путь, но не содержит эйлеров цикл

Для не одноэлементного связного графа следующие условия эквивалентны:

1. 𝐺 − эйлеров;
2. все вершины имеют четную степень;
3. множество всех ребер 𝐺 можно разбить на циклы.

Если G − граф, в котором 2N вершин имеет нечетную степень, то G можно покрыть N реберно-простыми путями.

G(V, E) - эйлеров тогда и только тогда, когда:

• все вершины имеют четную степень;
• все компоненты связности кроме одной не содержат рёбер.

Следствие: если в графе только две вершины имеют нечетную степень, то в нем есть Эйлеров путь

G − произвольно вычерчиваемый из вершины v, если любая цепь с началом в v может быть продлена до эйлерова цикла графа G

G − не одноэлементный эйлеров граф произвольно вычерчиваем из v <=> v принадлежит любому циклу графа G

1. Произвольный лес + вершина 𝑣
2. Соединить все вершины с 𝑣

• нечетной степени - нечетным числом ребер

• четной степени - четным числом ребер

3. Можно добавить петель в 𝑣

Гамильтонов путь — проходит через все вершины графа по одному разу

Полугамильтонов граф - содержит гамильтонов путь

Гамильтонов цикл — замкнутый гамильтонов путь

Гамильтоов граф - содержит гамильтонов цикл

Если 𝑛 ≥ 3 и для любых несмежных вершин сумма степеней будет не менее числа вершин в неориентированном графе, то этот граф гамильтонов

Если в неориентированном графе 𝑛 ≥ 3 и минимальная степень вершины не менее половины от общего числа вершин, то этот граф гамильтонов

ориентированный граф:

Если G — сильно связный ориентированный граф c n вершинами и для каждой 𝑣 ∈ V(G) выполняется:

deg_+(v) >= n/2

deg_-(v) >= n/2

Нет. Теоремы Оре, Дирака и Гуйа-Ури - это достаточные условия гамильтоновости графа.

Дуги вида (u, v) и (v, u) в некотором графе.

u, v ∊ V(G)

(u, v), (v, u) ∊ E(G)

Ребро e удаляется, а две его инцидентные вершины, u и v, сливаются в новую вершину w, где рёбра, инцидентные w, соответствуют рёбрам, инцидентным либо u, либо v. Ребро инцидентное u и v НЕ переходит в петлю на w.

Частный случай отождествления вершин

Хроматическим числом графа называется минимальное число цветов, которыми можно раскрасить вершины графа так, что никакое ребро не будет иметь начало и конец одного цвета.

Кликой в неориентированном графе G = (V,E) называется подмножество вершин C ⊆ V, такое что для любых двух вершин в C существует ребро, их соединяющее. Эквивалентно утверждению, что подграф, порождённый C, является полным.

Кликовое число графа — это число вершин в наибольшей клике графа.

Графы G и G' изоморфны если изоморфны некоторый G_0, являющийся подразбиением G, и, некоторый G_0', являющийся подразбиением G'.

Метод доказательства утверждения, зависящих от натурального аргумента. P(n), зависящее от натурального числа n - справедливо для любого n, если:

• P(1) является истинным утверждением
• P остается истинным утверждением, если n увеличить на единицу: P(n + 1) является истинным утверждением

Неупорядоченный набор размера k из n элементов - C(n, k)

$$ \frac {n!}{(n-k)! \cdot k!} $$

$$ \frac {(n + k - 1)!}{(n - 1)! \cdot k!} $$

Упорядоченная последовательность длины k из n элементов - A(n, k)

$$ \frac {n!}{(n - k)!} $$

$$ n^k $$

Переупорядочение набора элементов - P(n)

$$ n! $$

$$ \frac {n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!} $$

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

Если поместить n + 1 объект в n контейнеров, то по крайней мере в одном контейнере будет более одного объекта.

Если m объектов помещены в n контейнеров, то по крайней мере в одном контейнере находятся не более m/n с округлением вверх объектов, а также по крайней мере в одном контейнере находятся не менее m/n с округлением вниз объектов

Пусть S_1, S_2, ..., S_m - попарно непересекающиеся множества. Пусть для каждого i, множество S_i содержит n_i элементов. Тогда выбрать один элемент из них можно n_1 + n_2 +...+ n_m способами.

Пусть задана последовательность событий E_1, E_2, ..., E_m таких, что E_1 осуществляется n_1 способами, E_2 - n_2 способами и т.д. Тогда вся эта последовательность (упорядоченная) может быть осуществлена n_1 * n_2 ... n_m способами.

Пусть S, T - любые множества. Тогда количество вариантов выбора одного элемента из них равно |S u T| = |S| + |T| - |S ^ T|

A = a_1 a_2 a_3 ... a_n B = b_1 b_2 b_3 ... b_m

A лексикографически меньше B, если выполняется одно из условий:

• a_i = b_i для всех 0 <= i <= n, при этом n < m
• (∃k <= min(n, m) : a_k < b_k) && (∀i, j < k : a_i = b_j)

Алфавит — конечное непустое множество символов. Условимся обозначать алфавит большой греческой буквой Σ

Символ — объект, имеющий собственное содержание и уникальную читаемую форму.

Слово или цепочка — конечная последовательность символов некоторого алфавита.

Длина цепочки — число символов в цепочке. Длину некоторой цепочки w обычно обозначают |w|.

Пустая цепочка — цепочка, не содержащая ни одного символа. Эту цепочку, обозначаемую ε, можно рассматривать как цепочку в любом алфавите. Для любой строки α∈Σk верно: αε = εα = α

Выражение множества всех цепочек определенной длины, состоящих из символов данного алфавита. Σ^k — множество всех цепочек длины k, состоящих из символов алфавита Σ

Σk — множество цепочек длины k над алфавитом Σ.

Σ∗ = ⋃(k=0, ∞) Σk — множество всех цепочек (объединение множеств цепочек длин k: от 0 до ∞) над алфавитом Σ.

Пусть α, β ∈ Σ∗. Тогда α⋅β или αβ обозначает их конкатенацию, то есть цепочку, в которой последовательно записаны цепочки α и β.

Язык, состоящий из конкатенации цепочек данных языков.

L* - множество всех строк конечной длины, порожденное элементами множества L

Формальный язык над алфавитом Σ - некоторое подмножество 𝛴∗

Множество регулярных языков REG над алфавитом Σ = {c1,c2,…,ck} — множество, которое может быть получено из языков, каждый из которых содержит единственное слово — c_i или ε, и пустого языка при помощи последовательных применений операций объединения, конкатенации или замыкания Клини и никаких других.

Регулярное выражение над алфавитом Σ={c1,c2,…,ck} — способ порождения языка над Σ. Определяется рекурсивно следующим образом:

• Для любого i слово c_i является регулярным выражением, задающим язык из одного слова c_i.
• ε является регулярным выражением, задающим язык из одной пустой строки, а ∅ — пустой язык.
• Если α1 и α2 являются регулярными выражениями, задающими языки L1 и L2 соответственно, то (α1)|(α2) — регулярное выражение, задающее L1 ⋃ L2
• Если α1 и α2 являются регулярными выражениями, задающими языки L1 и L2 соответственно, то (α1)(α2) — регулярное выражение, задающее L1L2
• Если α1 является регулярным выражением, задающим язык L1, то (α1)∗ — регулярное выражение, задающее L∗1
• Операции указаны в порядке возрастания приоритета, при этом скобки повышают приоритет аналогично арифметическим выражениям.

Утверждение: по построению очевидно, что множество языков, порождаемых регулярными выражениями, совпадает со множеством регулярных языков.

Множество слов, порождаемых некоторым регулярным выражением

набор из пяти элементов - Σ, 𝑄, 𝑠 ∈ 𝑄, 𝑇 ⊆ 𝑄, 𝛿: 𝑄 × Σ ⟶ 𝑄, где:

• Σ— алфавит
• 𝑄 — множество состояний
• 𝑠 — начальное (стартовое) состояние
• 𝑇 — множество допускающих состояний
• 𝛿 — функция переходов

набор из пяти элементов - Σ, 𝑄, 𝑠 ∈ 𝑄, 𝑇 ⊆ 𝑄, 𝛿: 𝑄 × Σ ⟶ 2^𝑄, где:

• Σ — алфавит
• 𝑄 — множество состояний
• 𝑠 — начальное (стартовое) состояние
• 𝑇 — множество допускающих состояний
• 𝛿 — функция переходов

L(A) - язык автомата А - множество всех принимаемых им слов. Произвольный язык является автоматным, если существует ДКА, допускающий те и только те слова, которые принадлежат языку.

Строка принимается автоматом, если последнее состояние принадлежит множеству F (терминальных) — иначе отвергается.

REG = AUT Классы регулярных и автоматных языков совпадают