Линейно-ограниченный автомат - Большая Энциклопедия Нефти и Газа, статья, страница 1
Легче изменить постановку задачи так, чтобы она совпадала с программой, чем наоборот. Законы Мерфи (еще...)

Линейно-ограниченный автомат

Cтраница 1


Линейно-ограниченный автомат подобен машине Тьюринга. Он имеет конечное множество состояний, головку чтения / записи и ( бесконечную в обе стороны) ленту. Ограничением, отличающим его от машины Тьюринга, служит то, что длина участка ленты, который можно использовать, ограничивается линейной функцией от длины входной строки. В этом смысле он подобен автомату с магазинной памятью, порождающему контекстно-свободный язык ( поскольку максимальный размер магазина ограничен линейной функцией от входной строки), за исключением того, что линейно-ограниченный автомат имеет произвольный доступ к своей памяти, тогда как магазинный автомат имеет доступ к памяти только с одного конца.  [1]

Формальный язык, генерируемый контекстно-зависимой грамматикой или распознаваемый линейно-ограниченным автоматом.  [2]

Отсюда вытекает, что любой язык из R определяется детерминированным линейно-ограниченным автоматом ( Курода [6]) и что R есть подкласс класса контекстных языков.  [3]

4 Взаимосвязь языков сетей Петри с традиционными классами языков. [4]

Число фишек, а следовательно, и объем памяти, необходимый для запоминания их, ограничены линейной функцией от длины входной строки. Поэтому языки сетей Петри могут порождаться линейно-ограниченными автоматами.  [5]

Доказательство того, что все языки сетей Петри являются контекстно-связанными, довольно сложно. Существуют два способа показать, что язык контекстно-связанный: построить контекстно-связанную грамматику, порождающую его, или определить недетерминированный линейно-ограниченный автомат, порождающий этот язык. Питерсон [236] показал, как определяется контекстно-связанная грамматика, порождающая язык сети Петри. Здесь мы показываем как линейно-ограниченный автомат может породить язык сети Петри.  [6]

Ограничения, накладываемые на вид машин или грамматик, порождающих языки, определяют классы языков. Традиционными классами языков являются: регулярный, контекстно-свободный, контекстно-связанный и языки типа 0, соответствующие конечным автоматам, магазинным автоматам, линейно-ограниченным автоматам и машинам Тьюринга. Каждый из классов языков порождается соответствующим классом автоматов. Это дает прекрасные средства для установления связи теории сетей Петри с теорией формальных языков: мы определяем класс языков сетей Петри как класс языков, порождаемых сетями Петри. Детали этого определения аналогичны деталям определения любого другого класса языков.  [7]

Доказательство того, что все языки сетей Петри являются контекстно-связанными, довольно сложно. Существуют два способа показать, что язык контекстно-связанный: построить контекстно-связанную грамматику, порождающую его, или определить недетерминированный линейно-ограниченный автомат, порождающий этот язык. Питерсон [236] показал, как определяется контекстно-связанная грамматика, порождающая язык сети Петри. Здесь мы показываем как линейно-ограниченный автомат может породить язык сети Петри.  [8]

Линейно-ограниченный автомат подобен машине Тьюринга. Он имеет конечное множество состояний, головку чтения / записи и ( бесконечную в обе стороны) ленту. Ограничением, отличающим его от машины Тьюринга, служит то, что длина участка ленты, который можно использовать, ограничивается линейной функцией от длины входной строки. В этом смысле он подобен автомату с магазинной памятью, порождающему контекстно-свободный язык ( поскольку максимальный размер магазина ограничен линейной функцией от входной строки), за исключением того, что линейно-ограниченный автомат имеет произвольный доступ к своей памяти, тогда как магазинный автомат имеет доступ к памяти только с одного конца.  [9]



Страницы:      1