我被要求生成一个下推自动机 (PDA) 以确保 01 子串的数量与 10 个子串的数量相同,同样,00 子串的数量与 11 个子串的数量相同。
继承人的问题:
令 L1 ⊆ {0, 1}* 为 01 子串数量与 10 个子串相同,00 子串数量与 11 个子串相同的字符串语言。(注意:000 有两个 00 子串)产生一个下推自动机,它可以识别语言 L1。
到目前为止,我已经尝试过制作 CFG,以后可以将其转换为 PDA。那里没有运气,因为我似乎无法生成 CFG 来确保满足这两个条件。
我尝试了许多 CFG 语法规则的变体,类似于:
S -> 00S11S | 11S00S | 01S10S | 10S01S | 010S | 101S | 00110S | ϵ
我还尝试将每次出现的 01、10、00、11 分别存储为 PDA 堆栈中的 A、B、C、D。我天真地以为我可以匹配并弹出 A 与 B 和 C 与 D 的匹配和弹出,任何剩余的字符都会提醒我不满足条件。
任何人都可以提供一个提示来引导我朝着正确的方向前进吗?