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

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

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

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

Джерела

• Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973., с. 27.
• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
• Роджерс Х.. Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)