问题标签 [formal-languages]

制作 PDA 以识别以下语言：a 多于 b 的字符串语言

我已经为这个问题苦苦挣扎了好几天了，我似乎已经完全陷入了精神障碍。任何人都可以为我如何解决这个问题提供一些指导或指导吗？

上下文无关语言集合的联合总是上下文无关的吗？证明你的答案......

我知道答案是肯定的，但我该如何证明呢？

如果我们主要使用上下文无关语言进行编码，我真的无法理解如何模拟图灵机（它接受递归可枚举语言）的输出。

我希望有人可以帮助我解决以下问题，答案将是最好的，但如果你能指出我正确的方向，那也会有所帮助。我是大学最后一年的学生，这些问题来自之前的形式方法考试，我可以知道为今年论文准备的答案。我们的讲师似乎不是最好的，并且没有涵盖很多内容，因此事实证明不可能找到确切的答案。谷歌并没有太大的帮助，也没有推荐的书籍。

1 - 假设 ∃x • P (x) 在逻辑上等价于 ¬∀x • ¬P (x) 并且 ∀x ∈ S • P (x) 意味着 ∀x • x ∈ S ⇒ P (x)，推导出∃x ∈ S • P (x) 表示 ∃x • x ∈ S ∧ P (x)

2 - 描述必须证明的两个陈述以表明定义：

是规范的正确实现：

如何L={w|#a(w)=#b(w)=#c(w)}使用闭包证明该语言不是上下文无关的？

谢谢

编辑 ：

我知道该语言L1 = {a^i b^i c^i | i>=0}不是上下文无关语言。现在我正在尝试寻找另一种语言L2，其中L2将是常规语言，以产生矛盾，因为如果L1是上下文无关的并且L2是常规语言，那么L1∩L2也是上下文无关的。

我试图L={y#x|(y is a substring of x) ∧x,y∈{a,b}^* }使用抽水引理证明这不是上下文无关的，但我似乎无法做到这一点。如果

然后要么vxy两者兼有a，b要么只有，b要么只有a。

我怎样才能抽它来显示呢？

给定 L={a^nb^nc^n}，我怎么能直接说这种语言不规则而不看生产规则？我可以使用抽引引理，但有些人说只是看语法，这不是常规的。这怎么可能？

在这里，人们有时会说“你不能用正则表达式解析 X，因为 X 不是正则语言”。然而，据我了解，现代正则表达式引擎可以匹配的不仅仅是乔姆斯基意义上的正则语言。我的问题：

给定一个支持的正则表达式引擎

• 反向引用
• 无限宽度的环视断言
• 递归，比如(?R)

它可以解析什么样的语言？它可以解析任何上下文无关的语言吗？如果不能，反例是什么？

（准确地说，“解析”的意思是“构建一个单一的正则表达式，它将接受由语法 X 生成的所有字符串并拒绝所有其他字符串”）。

补充：我特别有兴趣看到现代正则表达式引擎（Perl、Net、python 正则表达式模块）无法解析的上下文无关语言的示例。

我有一个环境，其中包含一组我已经遇到过的令牌；当我查看一个新令牌时，我想将该令牌添加到当前环境中。基本上我想在我执行解析的环境上表达一个集合联合操作。

像Γ' = {Γ, x}

如果我想删除变量“x”（从环境中删除 x）

Γ' = Γ - x 如果 x ∈ Γ 。

写这两种形式的正确方法是什么。谢谢。

如果我有Σ={a}，有什么话Σ*？

Σ*= {a,aa,aaa,aaaa.....}?

谢谢