context-free-grammar - 语言不规则的半规则语法示例

Question

“半正则”文法是一种只允许以下形式的规则的文法：

X → y
X → y Y
X → Y y

其中 X 和 Y 是任何单个非终结符，x 和 y 是任何单个终结符。

例如，这是语言 a+ b+ 的半正则文法

S → a S
S → a A
A → A b
A → b

举一个语言不是正则语言的半正则语法的例子。一定要说明语言是什么以及为什么它不规则。

Answer 1

关于什么

S := aT | -
T := Sb

注意-表示空字符串；如果您愿意，可以用单个终端符号替换它，而不改变规律性。这就产生了语言a^n b^n，规范的非常规语言。您可以使用常规语言的抽水引理或 Myhill-Nerode 定理轻松证明这一点。