Пам'ять автомата

Па́м'ять автома́та — кількість станів автомату; іноді під терміном «пам'ять автомату» розуміють логарифм від цієї кількості.

Наприклад комп'ютер з розміром RAM в n біт, можна моделювати скінченним автоматом з $2^n+n$ станами ($2^n$ станів RAM і додатково n станів індексного регістра), тому розмір RAM в бітах приблизно дорівнює логарифму від числа станів.

Різні типи автоматів що виконують еквівалентні функції потребують різної пам'яті. Наприклад детермінований скінченний автомат в найгіршому випадку матиме $2^n$ станів, а еквівалентний йому недетермінований - лише n. Це пояснюється тим, що будь-якому стану детермінованого автомата відповідатиме підмножина станів недетермінованого, а їх кількість - булеан. Детальніше дивіться Детермінізація НДСкА.

Джерела

• Шаблон:ЕК, с. 27.
• Шаблон:Cinderella Book
• Шаблон:Роджерс.Теорія рекурсивних функцій