Па́м'ять автома́та — кількість станів автомату; іноді під терміном «пам'ять автомату» розуміють логарифм від цієї кількості.
Наприклад комп'ютер з розміром RAM в n біт, можна моделювати скінченним автоматом з станами ( станів RAM і додатково n станів індексного регістра), тому розмір RAM в бітах приблизно дорівнює логарифму від числа станів.
Різні типи автоматів що виконують еквівалентні функції потребують різної пам'яті. Наприклад детермінований скінченний автомат в найгіршому випадку матиме станів, а еквівалентний йому недетермінований - лише n. Це пояснюється тим, що будь-якому стану детермінованого автомата відповідатиме підмножина станів недетермінованого, а їх кількість - булеан. Детальніше дивіться Детермінізація НДСкА.
Зноски ред.
Література ред.
- Енциклопедія кібернетики, т. 1, с. 27.
| Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |
| Ця стаття не має інтервікі-посилань. |
- Пам'ять автомата у Google