Блог

Итак, недавно мы обсуждали тему линейных ограниченных автоматов в классе, но мы не совсем точно определили их формально. После просмотра определений в Интернете я все еще не понимаю, как расположены маркеры. Всегда ли они должны находиться на обоих концах входной строки? Могут ли они быть дальше влево/вправо, если их расстояние составляет не более некоторого постоянного кратного длине входного сигнала? Если да, то можем ли мы выбрать их положение для каждой входной строки отдельно (например, убедившись, что левый маркер всегда находится прямо перед входной строкой)?

Линейный ограниченный автомат является ограниченной формой недетерминированной машины Тьюринга. Ограничение заключается в том, что лента конечна. Это обеспечивается за счет ограничения ленты на обоих ее концах маркерами. Вот и все об этом.

Теперь то, как вы выбираете эти маркеры, не имеет значения для автомата, поскольку расстояние от левого и правого маркеров (т. Е. Длина ленты) является линейной функцией длины входного сигнала.

Машина Тьюринга начинается с ленты, на которой «где-то» записан ввод, и головка ленты указывает на ее первый символ. LBA не добавляет новых ограничений на это, поэтому оно остается: ввод где-то есть. Это означает (из-за маркеров ограничений), что ввод находится между двумя маркерами, вы можете разместить первый символ ввода сразу после левого маркера или разместить последний символ ввода непосредственно перед правым маркером. Оба случая не запрещены определением LBA.

Как другое положение ввода на ленте будет использоваться автоматом с его состояниями-это другая тема. Другими словами, вам может потребоваться конкретное размещение входных данных на ленте, которое зависит от состояний автомата и перехода, иначе вы не получите подтверждения.