0

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

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

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

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

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

**

S-> aab | baa | aba | aSab | aSba | aaSb |abSa |aabS | abaS | Saab | Saba | Sbaa | SS | bSaa | baSa | baaS ?

**

先感谢您

4

2 回答 2

1

您发布的所有语法都不能 product aaabba，您需要这样的东西：

S-> 哈萨 | aHSa | 阿沙 | aSaH | HSaa | 沙阿 | 萨哈 | 萨哈 | 哈斯 | 啊哈斯 | aaHS | aaSH | ε

H -> b

它可能可以用更短的语法来完成，但我认为这样就可以了。

于 2015-10-26T06:05:20.383 回答
1

试试这个：

S  -> ε | S1 S
S1 -> ε | aaS1bS1 | bS1aaS1 | aS1bS1a
于 2018-06-14T14:19:23.360 回答