Cтраница 2
Управляющее устройство всегда находится в одном из состояний, принадлежащих конечному множеству S. U Z0 указывает действие машины в случае, когда управляющее устройство находится в состоянии s, входная головка обозревает символ айв вершине магазина расположен символ А. [16]
Понятие детерминированного конечного автомата было введено в гл. Детерминированный конечный автомат выполняет шаги, определяемые текущим состоянием его блока управления и входным символом, обозреваемым входной головкой. Каждый шаг состоит из перехода в новое состояние и сдвига входной головки на одну клетку вправо. Оказывается, что язык представим регулярным выражением тогда и только тогда, когда он допускается некоторым конечным автоматом. [17]
Символ в вершине магазина не совпадает с текущим входным символом. Поскольку цепочка у и магазинный список совпадали до сих пор, Р может восстановить магазинный список, сдвигая входную головку влево и переписывая вход в магазин, пока не встретит с. Если in, то Р останавливается в незаключительном состоянии. Затем Р возвращается к шагу 4, пытаясь установить, не является ли у префиксом цепочки ai i. [18]
Автомат может иметь не более одного допустимого элементарного шага в каждой ситуации, тогда он является детерминированным. Он может иметь в некоторых ситуациях произвольное конечное множество допустимых шагов, тогда он является недетерминированным. Если нет ограничений на движение входной головки, то автомат называется двусторонним. Если головке позволяется передвигаться только в одном направлении, то автомат будет односторонним. [19]
Важным обобщением рассматриваемого понятия является недетерминированный конечный автомат. Для каждого состояния и каждого входного символа недетерминированный автомат имеет нуль или более вариантов выбора следующего шага. Он может также выбирать, сдвигать ему входную головку при изменении состояния или нет. [20]
Понятие детерминированного конечного автомата было введено в гл. Детерминированный конечный автомат выполняет шаги, определяемые текущим состоянием его блока управления и входным символом, обозреваемым входной головкой. Каждый шаг состоит из перехода в новое состояние и сдвига входной головки на одну клетку вправо. Оказывается, что язык представим регулярным выражением тогда и только тогда, когда он допускается некоторым конечным автоматом. [21]
Представим шаги НКА бинарным отношением ( - на множестве мгновенных описаний. Если ае, то состояние изменяется независимо от обозреваемого входного символа. Если а &, то символ а должен стоять в очередной клетке входной ленты, а входная головка сдвигается на одну клетку вправо. [22]
Слабость результата Кобэма состоит в том, что, хотя off-line машина Тьюринга разумна для измерения времени вычислений и памяти в отдельности, эта модель слишком ограничительна, когда память и время рассматриваются вместе. Например, ясно, что палиндромы могут быть распознаны за 2п шагов с постоянной зоной, если две головки осуществляют совместный просмотр входной ленты. Доказательство применимо к любой последовательной машине общего вида, что включает off-line машину Тьюринга со многими входными головками или даже с произвольным доступом к входной ленте. К сожалению, в нашем доказательстве очень важный момент состоит в том, что сортировка требует много выходных битов, и остается открытым вопрос: можно ли подобную нижнюю оценку получить для какой-нибудь задачи распознавания множества, такой, как распознавание того, все ли п входных чисел различны. [23]
Символ в вершине магазина не совпадает с текущим входным символом. В этом случае Р сдвигает входную головку влево, переписывая вход в магазин, пока головка не достигнет левого концевого маркера. Если i2, то Р останавливается и отвергает вход. В противном случае Р удаляет аг из магазина и сдвигает входную головку на одну клетку вправо - к символу, стоящему непосредственно справа от левого концевого маркера. [24]
Он содержит входную ленту с отметками концов, на которой записана строка. Входная головка считывает по одному входному символу. Имеется конечное управление, которое может находиться в конечном числе состояний. Имеется конечная память, возможно, с некоторой структурой. Автомат делает элементарные шаги, зависящие от состояния конечного управления, символа, считываемого входной головкой, и конечного объема информации из бесконечной памяти. [25]