设计一种上下文无关语法语言，其中 a 的长度 = b 的两倍长度

Question

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

for a language where { 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 ?

**

提前致谢

Answer 1

None 您发布的语法可以产品 aaabba，您需要这样的东西：

S-> HaSa | aHSa | aSHa | aSaH | HSaa | SHaa | SaHa | SaaH | HaaS | aHaS | aaHS | aaSH | epsilon

H -> b

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

Answer 2

试试这个：

S  -> ε | S1 S
S1 -> ε | aaS1bS1 | bS1aaS1 | aS1bS1a