Создание автомата нажатия для обеспечения двух одинаковых вхождений подстроки
Меня просят создать автомат сжатия (PDA), чтобы обеспечить наличие равного количества подстрок 01 как 10 подстрок, а также, что число подстрок, равное 00, равно 11 подстрокам.
Вот проблема:
Пусть L1 ⊆ {0, 1}* будет языком строк, которые имеют то же количество подстрок 01, что и 10 подстрок, и такое же количество подстрок 00, что и 11 подстрок. (Примечание: 000 имеет две подстроки 00) Создайте автомат с нажатием, который распознает язык L1.
До сих пор я пытался создать CFG, который впоследствии можно было бы преобразовать в КПК. Не повезло, так как я не могу произвести CFG, чтобы обеспечить выполнение обоих условий.
Я пробовал много вариантов грамматики CFG, похожих на:
S -> 00S11S | 11S00S | 01S10S | 10S01S | 010S | 101S | 00110S | ϵ
Я также попытался сохранить каждое вхождение 01,10,00,11 как A,B,C,D соответственно в стеке КПК. Я наивно думал, что смогу сопоставить и сложить буквы A с буквами B, а буквы C с буквами D, и любые оставшиеся символы предупредят меня о невыполнении условий.
Может ли кто-нибудь дать подсказку, чтобы направить меня в правильном направлении?
1 ответ
Пытались ли вы создать вместо этого NFA, а затем просто добавить операции push и pop для преобразования его в КПК?