Теорія автоматів — теоретичний розділ інформатики та математики. Це вивчення абстрактних машин і обчислювальних проблем, які можна вирішити за допомогою цих машин. Абстрактна машина називається автоматом. Основною мотивацією розробки теорії автоматів була розробка методів опису та аналізу динамічної поведінки дискретних систем.
Цей автомат складається зі станів і переходів. The Держава представлений колах , і Переходи представлений стрілки .
Автомати - це тип машини, яка приймає деякий рядок як вхідні дані, і цей вхідний сигнал проходить через кінцеву кількість станів і може увійти в кінцевий стан.
Існує основна термінологія, яка є важливою та часто використовується в автоматах:
Символи:
Символи - це сутність або окремі об'єкти, які можуть бути будь-якою буквою, алфавітом або будь-яким малюнком.
приклад:
1, а, б, #
Алфавіти:
Алфавіти — це кінцевий набір символів. Його позначають ∑.
Приклади:
∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} Рядок:
Це кінцевий набір символів алфавіту. Рядок позначається w.
приклад 1:
Якщо ∑ = {a, b}, різними рядками, які можуть бути згенеровані з ∑, є {ab, aa, aaa, bb, bbb, ba, aba.....}.
- Рядок із нульовим входженням символів називається порожнім рядком. Він представлений ε.
- Кількість символів у рядку w називається довжиною рядка. Його позначають |w|.
приклад 2:
w = 010 Number of Sting |w| = 3
Мова:
Мова - це набір відповідних рядків. Мова, яка формується над Σ, може бути Кінцевий або Нескінченна .
Приклад: 1
L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> Приклад: 2
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>