0

我正在处理以下语法：

G = ( {S, A}, {a, b}, P, S ) 
P = { S -> aAb, S -> bAa, 
A -> aSa, 
A -> S, 
A -> epsilon}

我需要找出 L(G)。问题是，我发现语法中的单词是这样的：以 a 开头并以 b 结尾，或者以 b 开头并以 a 结尾，并且在这些字母之间有一种组合：ab、ba、aaba，阿巴；然后通过在中间的 a 和 b 之间插入这 4 个组合中的一个来形成下一个单词。但是我该如何正式表达呢？我的意思是，据我所知，L(A) = a^n S a^n 如果 w 属于 L(G)，那么 w 反转也属于 L(G)。我试图将其表达为正则表达式但失败了......有人可以帮忙吗？

谢谢你。

4

4 回答 4

1

你看到 L 不是正则，证明你可以使用Pumping lemma或Myhill-Nerode theorem，所以正则表达式不能讨论

您可以注意到，由于 L 仅由 {a,b} 组成，因此您可以使用它的幂 我们看到语言是 aAb 或 bAa 或 aAa 的形式，但 aAa 不能位于单词的开头

所以让我们使用它，我们唯一错过的是 bAb A 的组合可以生成几乎所有内容（单词 |w| = 2k 和 |w|>=2）但是 b 的位置与 b 的位置相反的单词

正式地 在此处输入图像描述

对不起我的 tex 技能和我的正式表达

一定有什么错误，因为我没有太多时间去想这个，但它可以是一些方法如何继续，这是作业所以没关系，想想吧！:)

于 2011-11-14T20:21:48.127 回答
0

生成的语言是： (a) n (b) m 是 n>=m

于 2014-11-02T20:44:49.253 回答
0

我试图将其表达为正则表达式但失败了

这种语言“可能”不规则。上下文无关语言比正则表达式更复杂/更强大。

试着生成几个词，看看你是否能想出一个名字，语言的属性。或者尝试查找该语言中没有的单词。

一些提示，一些你可以很容易看到的属性：

  1. 最小的字符串至少大小为 2。

  2. 字符串的大小是偶数。

  3. b 的计数 <= 比 a 的计数。

如果您取出A -> aSa，并将一个单词与其反转版本进行比较，则应该可以看到一个模式。如果您包含遗漏规则，则模式会略有变化......

于 2011-11-14T16:05:53.707 回答
0

你被要求找到由语法G生成的语言和产生式

S → aAb | bAa
A → aSa | S | λ

首先，考虑从起始符号S开始的小推导

S ⇒1 aAb ⇒1 aaSab | aSb | ab

S ⇒1 bAa ⇒1 baSaa | bSa | ba

困难的一步是处理由规则A → aSa、S → aAb和S → bAa生成的递归。通过考虑G生成的语言的归纳定义，揭示了处理这个困难的线索：

1. ab ∈ L4
2. ba ∈ L4
3. w ∈ L4 → awb ∈ L4
4. w ∈ L4 → bwa ∈ L4
5. w ∈ L4 → awa ∈ L4

规则 (3)-(5) 对应于G中的规则A → aAa、S → aAb和S → bAa。不难看出，归纳定义和G的规则定义了同一种语言。归纳定义表明G的语言可以逐步构建。从G中可生成的最小字符串开始，我们构建了与有问题的规则相对应的越来越大的字符串集：

L(1)     = {ab, ba}
L(n + 1) = {awb, bwa, awa : w ∈ L(n)}

集合L (1) 包含G中可生成的最小字符串。对于每个字符串w ∈ L (n) ，集合L (n + 1) 包含字符串awb、bwa和awa 。即，L (n+1)中的字符串对应于通过将规则S → aAb、S → bAa和A → aAa一次应用于L (n)中的字符串而获得的字符串。剩下的就是构造L (n) 的并集，它是一个集合：

L = ⋃ {L(n) : n ∈ ℕ}

要看到L等价于语法G生成的语言，您可以通过归纳来争论G中的推导长度。从G中可流派的最小字符串（即ab和ba）开始，使用适当的归纳假设向后工作。

于 2011-11-22T16:33:14.603 回答