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

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

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

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

Примітки

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

Джерела

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

Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.

[1] ttps://cs.stackexchange.com/questions/42552/ram-machine-and-fsm

[1]