Как построить автоматы выталкивания для L= { w ∈ {a, b}* | w не равно xx^R для некоторого x ∈ {a, b}* }
0
Я предполагаю, что вам нужен недетерминированный нажимной автомат. Я не думаю, что это выполнимо с детерминированным КПК.
Это звучит как проблема с домашним заданием, поэтому я собираюсь дать только общие наброски:
Вы, по сути, догадываетесь, где находится центр строки. Вы помещаете элементы в стек, пока в какой-то момент не догадаетесь, что достигли центра строки. Затем вы начинаете сравнивать свои входные данные с элементами, которые вы извлекаете из стека. Вы потерпите неудачу, если они не совпадут. Вы добьетесь успеха, если дойдете до конца ввода точно в тот момент, когда стек опустеет.