Cтраница 1
Односторонняя магазинная машина - это односторонняя машина Тьюринга с тем ограничением, что машина печатает пустой символ перед каждым правым продвижением своей рабочей ленты. [1]
Предположим, что односторонняя магазинная машина действует на ленте L ( n) и разрешает нерегулярное множество. [2]
Если нерегулярный язык разрешим на односторонней магазинной машине, то существуют слова, требующие довольно большой магазинной ленты. [3]
Поэтому класс языков, разрешимых односторонними магазинными машинами, образует собственное подмножество класса контекстно-свободных языков. Как показано в [1], существует единственный класс сложности, содержащий нерегулярные множества, а именно класс ( L ( n) n) - разрешимых множеств. [4]
Эта теорема полностью решает проблему для односторонней магазинной машины. Иерархия состоит из двух классов: С и СЛ. Эти классы различны, потому что некоторые магазинные машины разрешают нерегулярные множества. [5]
Наиболее удивительный результат подобного рода относится к односторонним магазинным машинам и двусторонним машинам Тьюринга. Любой нерегулярный контекстно-свободный язык, который можно вообще разрешить на односторонней магазинной машине, требует по крайней мере L ( n) ogn на двусторонней машине Тьюринга. [6]
Все нерегулярные контекстно-свободные языки, которые можно разрешить на односторонней магазинной машине, требуют по крайней мере L ( n) ogn для своего разрешения на двусторонней машине Тьюринга. [7]
Чтобы показать, например, что L5 можно разрешить односторонней магазинной машиной, рассмотрим следующее неформальное описание разрешающей процедуры. [8]
Мы покажем, что L4 и L5 суть контекстно-свободные языки, разрешимые односторонней магазинной машиной. [9]
Множество предложений является контекстно-свободным языком тогда и только тогда, когда его можно разрешить недетерминированной односторонней магазинной машиной. [10]
Теорема б гласит, что требуется по крайней мере L ( ri) Mogn квадратов ленты на двусторонней машине Тьюринга, чтобы промоделировать одностороннюю магазинную машину, производящую нерегулярное разрешение. Теорема 5 гласит, что для этого требуется самое большее L ( n) ( log n) 2, даже если магазинная машина недетерминирована. Ранее было замечено, что вопрос, действительно ли требуется ( logrc) 2, остается открытым. Мы предполагаем, что это так даже для детерминированных магазинных машин. [11]
В этом разделе мы покажем, что двусторонние и односторонние машины Тьюринга и двусторонние магазинные машины определяют бесконечные иерархии контекстно-свободных языков. Как обсуждалось выше, односторонняя магазинная машина обладает только одним классом сложности L ( n) n и потому не определяет иерархию. Уже было показано, что машины Тьюринга включают все контекстно-свободные языки в свои иерархии. [12]
Наиболее удивительный результат подобного рода относится к односторонним магазинным машинам и двусторонним машинам Тьюринга. Любой нерегулярный контекстно-свободный язык, который можно вообще разрешить на односторонней магазинной машине, требует по крайней мере L ( n) ogn на двусторонней машине Тьюринга. [13]
Основная идея доказательства состоит в следующем. Мы сначала покажем, что если нерегулярный язык разрешим на односторонней магазинной машине, то существуют слова, требующие для своей записи довольно длинной магазинной ленты, которая в дальнейшем должна быть прочитана. [14]
Осталось только показать, что все семь языков действительно разрешимы односторонней магазинной машиной. [15]