鉴于 L1 是确定性上下文无关语言，而 L2 是常规语言。L1 U L2 结果 DCFL 还是正则？
请举例说明上下文
问问题
1374 次
2 回答
3
生成的语言必须是 DCFL。直观地说，您可以通过获取 DCFL 的 DPDA 和常规语言的 DFA 来检查字符串是否在 DCFL 和常规语言的联合中，然后并行运行两者并查看是否接受。您可以通过使用产品构造的变体来模拟该过程，该变体显示常规语言在联合下是封闭的：为 DFA 状态和 DPDA 状态的每个组合构建一个具有一个状态的 DPDA，然后构建转换以便它们模拟在从 DPDA 和 DFA 并行过渡之后。为此，您只需要一个堆栈，因此构造应该可以正常工作。
希望这可以帮助！
于 2015-01-16T00:38:12.450 回答
1
l2=sigma* and L1=a^nb^n l1 is dcfl and l2 is regular.but L1 union l2=l1 is dcfl but not regular
于 2016-01-21T09:09:48.050 回答