Теорія автоматів

🎯 Вступ до теорії автоматів

Теорія автоматів - це галузь теоретичної інформатики, що вивчає абстрактні машини (автомати) та проблеми, які вони можуть розв'язувати. Вона є основою для розуміння обчислювальних можливостей різних моделей обчислень та формальних мов.

🔑 Основні концепції:

Скінченні автомати: Прості моделі обчислень з обмеженою пам'яттю

Регулярні мови: Найпростіший клас формальних мов

Контекстно-вільні граматики: Граматики для структурованих мов

Машини Тьюринга: Універсальні моделі обчислень

⚙️ Скінченні автомати (FA)

🔧 Визначення скінченного автомата

Формальне визначення

Скінченний автомат M = (Q, Σ, δ, q₀, F), де:

Q: Кінцева множина станів

Σ: Кінцевий алфавіт (вхідні символи)

δ: Функція переходів (Q × Σ → Q)

q₀: Початковий стан

F: Множина приймаючих станів

📊 Типи скінченних автоматів

Для кожного стану та вхідного символу існує рівно один наступний стан

Для стану та вхідного символу може існувати кілька наступних станів або жодного

// NFA для мови, що закінчується на 01 Q = {q0, q1, q2} Σ = {0, 1} δ(q0, 0) = {q0, q1}, δ(q0, 1) = {q0} δ(q1, 1) = {q2} q0 - початковий стан F = {q2}

🔄 Еквівалентність DFA та NFA

Теорема еквівалентності

Для кожного NFA існує еквівалентний DFA, що розпізнає ту саму мову.

Алгоритм побудови DFA з NFA:

Стан DFA - це підмножина станів NFA

Початковий стан - ε-замикання початкового стану NFA

Функція переходів: δ'(P, a) = ε-замикання(∪{δ(q, a) | q ∈ P})

Приймаючі стани - ті, що містять приймаючі стани NFA

// DFA для мови з парною кількістю 0 Q = {q0, q1} Σ = {0, 1} δ(q0, 0) = q1, δ(q0, 1) = q0 δ(q1, 0) = q0, δ(q1, 1) = q1 q0 - початковий стан F = {q0} - приймаючий стан

📝 Регулярні мови

🔤 Властивості регулярних мов

Визначення регулярної мови

Мова L є регулярною, якщо існує скінченний автомат, що розпізнає L.

Розпізнається DFA

Розпізнається NFA

Описується регулярним виразом

Генерується право-лінійною граматикою

🔧 Операції над регулярними мовами

L₁ ∪ L₂ - об'єднання двох регулярних мов

Доказ: Побудувати NFA з двома початковими станами

L₁L₂ - конкатенація двох регулярних мов

Доказ: З'єднати приймаючі стани L₁ з початковими L₂

L* - повторення мови L нуль або більше разів

Доказ: Додати ε-переходи від приймаючих до початкових станів

🚫 Лема про накачування

Лема про накачування для регулярних мов

Якщо L - регулярна мова, то існує константа n така, що для будь-якого рядка w ∈ L з |w| ≥ n, w можна розбити на w = xyz, де:

|xy| ≤ n

|y| ≥ 1

xyⁱz ∈ L для всіх i ≥ 0

// Приклад: Довести, що L = {0ⁿ1ⁿ | n ≥ 0} не регулярна // Припустимо, що L регулярна // Виберемо w = 0ⁿ1ⁿ // Розіб'ємо w = xyz, де |xy| ≤ n, |y| ≥ 1 // Тоді y складається тільки з 0 // xy²z = 0^(n+|y|)1ⁿ ∉ L // Протиріччя!

🌳 Контекстно-вільні граматики (CFG)

📝 Визначення CFG

Формальне визначення

Контекстно-вільна граматика G = (V, T, P, S), де:

V: Множина змінних (нетерміналів)

T: Множина терміналів

P: Множина продукцій (правил)

S: Початковий символ

📚 Приклади CFG

G = ({E, T, F}, {+, *, (, ), id}, P, E) P: E → E + T | T T → T * F | F F → (E) | id // Генерує вирази: id, id+id, id*id, (id+id)*id

🔄 Еквівалентні форми

Нормальна форма Чомскі

КОЖНА продукція має вигляд A → BC або A → a, де A, B, C - нетермінали, a - термінал.

Видалити ε-продукції

Видалити одиничні продукції

Перетворити на НФЧ

Нормальна форма Грейбах

КОЖНА продукція має вигляд A → aα, де a - термінал, α - рядок нетерміналів.

🚫 Лема про накачування для CFG

Лема про накачування для контекстно-вільних мов

Якщо L - контекстно-вільна мова, то існує константа n така, що для будь-якого рядка z ∈ L з |z| ≥ n, z можна розбити на z = uvwxy, де:

|vwx| ≤ n

|vx| ≥ 1

uvⁱwxⁱy ∈ L для всіх i ≥ 0

G = ({S}, {(, )}, P, S) P: S → (S) S → SS S → ε // Генерує правильно розставлені дужки: // (), (()), ((())), ()()(), ...

🖥️ Машини Тьюринга (TM)

🎯 Визначення машини Тьюринга

Формальне визначення

Машина Тьюринга M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject), де:

Q: Кінцева множина станів

Σ: Вхідний алфавіт

Γ: Алфавіт стрічки (Σ ⊆ Γ)

δ: Функція переходів

q₀: Початковий стан

q_accept: Приймаючий стан

q_reject: Відхиляючий стан

🔧 Варіанти машин Тьюринга

Одна стрічка, одна головка

Кілька стрічок, кожна з власною головкою

Теорема: Еквівалентна стандартній TM

Може мати кілька можливих переходів

Теорема: Еквівалентна детермінованій TM

🌐 Універсальна машина Тьюринга

Концепція універсальності

Універсальна машина Тьюринга U може симулювати будь-яку іншу машину Тьюринга M.

Вхід для U: ⟨M, w⟩ - код машини M та вхідний рядок w

Поведінка U: U(⟨M, w⟩) = M(w)

🔄 Тези Чорча-Тьюринга

Теза Чорча-Тьюринга

Кожна інтуїтивно обчислювана функція може бути обчислена машиною Тьюринга.

Машини Тьюринга

Лямбда-числення

Рекурсивні функції

Машини з регістрами

📊 Ієрархія Чомскі

🏗️ Класифікація формальних мов

🎯 Практичні застосування

💻 Компілятори

Лексичний аналіз (DFA), синтаксичний аналіз (CFG), кодогенерація

🔍 Пошук у текстах

Регулярні вирази, скінченні автомати для пошуку патернів

🎮 Теорія ігор

Моделювання поведінки гравців, автомати для штучного інтелекту

🔐 Криптографія

Генерація псевдовипадкових послідовностей, аналіз стійкості

📚 Рекомендована література

"Introduction to the Theory of Computation" - Michael Sipser

"Elements of the Theory of Computation" - Harry Lewis, Christos Papadimitriou

"Automata Theory, Languages, and Computation" - Hopcroft, Motwani, Ullman

"Computability and Complexity" - Neil Jones

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Spirograph і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.