union - 两种语言的并集和交集

Question

鉴于语言

大号₁ ={(i|l)p(f|g)n(f|h)m(f|i)r(l|m)p : n + m > r > 0, p >= 0}

和

大号₂ =(f|g)*(h|i)+

_{为 L 1} ∪ L ₂和（另一个） L ₁ ∩ L ₂制作一个自动机。

我知道 L ₁是 CFL 并且您需要 PDA 来解析它，我知道 L ₂是 RL 并且要使用 DFA。
我的问题是：你如何建立交叉点（和联合）？也就是说，你制作自动机的实际语言 L ₃ = L ₁ ∩ L ₂是什么，你如何计算它？

Answer 1

联合很容易——如果您有两种语言的 PDA，则可以通过引入一个新的初始状态来获得一个接受联合的非确定性 PDA，该初始状态带有 epsilon 转换到您的语言的自动机的每个初始状态。接受的语言将完全是任何一个（或两个）自动机接受的语言。

交叉点有点棘手。现在，你说你想要一个自动机——它可以指任何理论机器，包括图灵机或等效的两栈 PDA。如果您可以创建一个两层 PDA，那么您的任务就很简单了。使用笛卡尔积机器构造用于构造 A 和 B 的 DFA，给定 A 和 B 的 DFA，并让 ((a, b), w) -> (a', b') 形式的每个转换推动一个符号(x, y) 到堆栈上当且仅当 (a, w)->a' 将 x 压入 A 的堆栈并且 (b, w)->b' 将 y 压入 B 的堆栈。

当然，如果您从 RL 的 DFA 开始并执行上述构造，您只需要一个堆栈，生成的自动机是 PDA，而不是两个堆栈的 PDA。