Очередь автоматов может имитировать любые автоматы Pushdown?
Я работаю над теоретическим заданием, и этот вопрос действительно заставил меня задуматься. Вопрос звучит так: покажите, что любой автомат с нажатием кнопки может быть смоделирован с помощью автоматов очереди. Сначала я думал, что это будет просто, но потом я подумал о L = {WW^R | W = {a, b}*} (W^R - обратная W). Это просто создать в общем виде автомата, работающего по принципу сжатия, но я не могу придумать какой-либо способ сделать это в общем виде. автомат очереди. Я не думаю, что есть (конечный) общий случай, который мы можем разработать для этого. Я мог бы слишком подумать об этом, так как мог бы просто неправильно понять, что означает симуляция. В любом случае, я скорее ошибаюсь, чем вопрос, но как это работает в случае, о котором я говорил?
Спасибо за любую помощь, которую вы оказываете!
1 ответ
Есть способ сделать это довольно просто:
1) Покажите, что очередь может имитировать полную машину Тьюринга. Короче говоря, поместите ленту Тьюринга в очередь, обмотанную специальными маркерами для концов ленты и считывающей головки. (Если оттуда не ясно, посмотрите ссылку на вики или оставьте комментарий)
2) Обратите внимание, что машина Тьюринга строго более мощная, чем КПК, поэтому она должна иметь возможность имитировать КПК.