Автомата пам'ять

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

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

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

Примітки

1. https://cs.stackexchange.com/questions/42552/ram-machine-and-fsm

Джерела

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