问题标签 [context-free-language]

我想知道是否有人可以帮助我设计上下文无关语法

对于一种语言，其中 { w | |w|a=2|w|b }

例如 w=aab , aaaabb , aaaaaabbb ,baa , aba , aabbaaaba ...

S-> aab | 咩| 阿巴 | 不锈钢 | 抗体 | 巴萨 | aaSb | bSaa 不会生成 aaabba。

所以我的下一个问题是，有一个看起来像这样的语法是不是太模棱两可了->

**

**

先感谢您

在一个作业中，我被要求为以下功能编写一个 CFG：

def f(x, y): 返回 x + y

def g(x, y): 返回 x – y

def h(x, y, z): 返回 x + y % z

def w(x, y, z): 返回 x * y – z

和

def h1(x, y, z): 返回 (x + y) % z

def h2(x, y, z): 返回 x + y % z

我试图将其作为普通 CFG 进行处理，但是对于函数定义和函数体，我无法做到这一点。我不太确定如何从这种 CFG 开始。

这是我的作业。

练习 3：找出语言 L = { |的正则文法 n + m 是奇数}。展示你获得它的方式。

问题要求显示我获得答案的方式。所以这是我的解释。

我们从 DFA 构造DFA，我们得到S -> aA | bA A -> aS | BS | null因此，正则文法为 G = {V , T , S, P}其中V = {S, A} T = {a, b} P = {S -> aA | bA, A -> aS | BS | 无效的}

然而，下一个问题是：

构造一个接受由练习 3 中的语法生成的语言的 DFA。如果可能，简化构造的 DFA。

所以我认为绘制DFA并不是练习3的预期解释。也许还有另一种方法可以在不绘制DFA的情况下获得正则语言。请告诉我。

谢谢你。

考虑语言，为这种语言创建一个 CFG。 我从 开始，但不确定我应该如何定义 A 或 B。“OR”似乎很难融入语言的定义，因为似乎没有必要同时跟踪 n 和 m 并将它们与 p 进行比较，但我不知道我要跟踪哪一个 {anbmcp | n <= p OR m <= p}
S -> aA | aB

给出下列语言的语法{0^n w 1^n | n>=0 w is in {0,1}* and |w|=n}

尝试解决方案：

不确定如何保证 r 的长度与 0 或 1 的数量相同。

所以我发现这个 PDA 可以接受语言为 {0,1}* 的回文。

但是，我无法理解它如何接受“1”或“0”。

在B其中可以读取 1 或 0 并将相同的符号推入堆栈，然后转到C. 但是，一旦它进入C，它就无处可去，因为要到达堆栈中的 $ 另一个符号需要被读取。

有人可以解释它是如何工作的吗？

我在想，为了接受单个符号，我们需要从Bto D=>转换1,$->ε | 0,$->ε。

我会是正确的吗？

谢谢 ：）

我阅读了多个答案，说明如果一种语言不是上下文无关的，那么它的补语是上下文无关的（如果我错了，请纠正我）。反之亦然吗？上下文无关语言的补语是上下文无关的吗？

我需要一个算法来检查 G1 的语言是否是 G2 语言的子集。（假设 G1 和 G2 是两个具有相同字母表的 LL(1) 语法，其产生规则是 A-->aB 或 A-->a 形式，并且“a”是非 epsilon。我有一个解析算法根据字符串检查语法但不检查另一种语言。有没有人有解决方案。

您好我想知道是否有一个正则表达式可以执行以下操作：

从一个字符串中选择所有子字符串：

• 从&和开始
• 在( n >= 0)之后有n个字符&

并且那些子字符串不是

• &
• '
• <
• >或者
• "

例如，给定字符串

是否有一个只返回子字符串的正则表达式 &partners？

我的直觉说不，因为我需要一个上下文无关的语法，但我怎样才能证明呢？是否有正则表达式可以用泵引理对其进行测试？

或者一个正则表达式实际上存在而我的直觉是错误的？

谢谢

我知道如何构造一个具有相同数量的两个给定元素的上下文无关语法，即。如果我们使用 {0,1}

然而，我正在努力寻找一种方法来构建一种语法，该语法具有给定数量的一个元素而不是另一个元素。IE。始终比 1 多两个 0。有人对如何构建这样的语法有任何想法吗？