Линейный ограниченный автомат
-
Определение линейного ограниченного автомата (LBA)
- LBA — это ограниченная форма машины Тьюринга с двумя конечными маркерами и ограниченной областью вычислений.
- Лента LBA ограничена входной строкой и двумя квадратами для конечных меток.
-
Альтернативное определение и вычислительные возможности
- LBA обладает теми же свойствами, что и машина Тьюринга, но ограничена линейной длиной ленты.
- LBA и машина Тьюринга имеют одинаковые вычислительные возможности.
-
Связь с контекстно-зависимыми языками
- LBA подходят для распознавания контекстно-зависимых языков, где длина строки не может превышать длину строки.
- Существует взаимно однозначное соответствие между LBA и контекстно-зависимыми грамматиками.
-
История и проблемы LBA
- Джон Майхилл представил LBA в 1960 году, Питер Ландвебер доказал контекстную зависимость в 1963 году.
- С.-Ю. Курода представил общую модель LBA и доказал контекстную зависимость в 1964 году.
- Курода сформулировал две проблемы LBA, первая из которых остается открытой.
-
Теорема Савича и рекомендации
- Теорема Савича связывает NSPACE(O(n)) с DSPACE(O(n2)).
- Статья содержит рекомендации по форматированию и использованию LBA в HTML.
Полный текст статьи: