Линейно-ограниченный автомат
Cтраница 1
Линейно-ограниченный автомат подобен машине Тьюринга. Он имеет конечное множество состояний, головку чтения / записи и ( бесконечную в обе стороны) ленту. Ограничением, отличающим его от машины Тьюринга, служит то, что длина участка ленты, который можно использовать, ограничивается линейной функцией от длины входной строки. В этом смысле он подобен автомату с магазинной памятью, порождающему контекстно-свободный язык ( поскольку максимальный размер магазина ограничен линейной функцией от входной строки), за исключением того, что линейно-ограниченный автомат имеет произвольный доступ к своей памяти, тогда как магазинный автомат имеет доступ к памяти только с одного конца. [1]
Формальный язык, генерируемый контекстно-зависимой грамматикой или распознаваемый линейно-ограниченным автоматом. [2]
Отсюда вытекает, что любой язык из R определяется детерминированным линейно-ограниченным автоматом ( Курода [6]) и что R есть подкласс класса контекстных языков. [3]
 |
Взаимосвязь языков сетей Петри с традиционными классами языков. [4] |
Число фишек, а следовательно, и объем памяти, необходимый для запоминания их, ограничены линейной функцией от длины входной строки. Поэтому языки сетей Петри могут порождаться линейно-ограниченными автоматами. [5]
Доказательство того, что все языки сетей Петри являются контекстно-связанными, довольно сложно. Существуют два способа показать, что язык контекстно-связанный: построить контекстно-связанную грамматику, порождающую его, или определить недетерминированный линейно-ограниченный автомат, порождающий этот язык. Питерсон [236] показал, как определяется контекстно-связанная грамматика, порождающая язык сети Петри. Здесь мы показываем как линейно-ограниченный автомат может породить язык сети Петри. [6]
Ограничения, накладываемые на вид машин или грамматик, порождающих языки, определяют классы языков. Традиционными классами языков являются: регулярный, контекстно-свободный, контекстно-связанный и языки типа 0, соответствующие конечным автоматам, магазинным автоматам, линейно-ограниченным автоматам и машинам Тьюринга. Каждый из классов языков порождается соответствующим классом автоматов. Это дает прекрасные средства для установления связи теории сетей Петри с теорией формальных языков: мы определяем класс языков сетей Петри как класс языков, порождаемых сетями Петри. Детали этого определения аналогичны деталям определения любого другого класса языков. [7]
Доказательство того, что все языки сетей Петри являются контекстно-связанными, довольно сложно. Существуют два способа показать, что язык контекстно-связанный: построить контекстно-связанную грамматику, порождающую его, или определить недетерминированный линейно-ограниченный автомат, порождающий этот язык. Питерсон [236] показал, как определяется контекстно-связанная грамматика, порождающая язык сети Петри. Здесь мы показываем как линейно-ограниченный автомат может породить язык сети Петри. [8]
Линейно-ограниченный автомат подобен машине Тьюринга. Он имеет конечное множество состояний, головку чтения / записи и ( бесконечную в обе стороны) ленту. Ограничением, отличающим его от машины Тьюринга, служит то, что длина участка ленты, который можно использовать, ограничивается линейной функцией от длины входной строки. В этом смысле он подобен автомату с магазинной памятью, порождающему контекстно-свободный язык ( поскольку максимальный размер магазина ограничен линейной функцией от входной строки), за исключением того, что линейно-ограниченный автомат имеет произвольный доступ к своей памяти, тогда как магазинный автомат имеет доступ к памяти только с одного конца. [9]
Страницы: 1