理论计算机科学-上下文敏感语法？

Question

为什么"Aa -> aA“的规则是上下文敏感的呢？根据定义，对上下文敏感的规则必须类似于以下形式：

αAβ → αγβ

哪里

A ∈ N,  α,β ∈ (N∪Σ)*   and γ ∈ (N∪Σ)+

谢谢。

Answer 1

这取决于你的意思。如果你向下滚动维基百科条目，你可以在形式上看见，

cB→Bc

不适合该方案，但可以通过适合该方案的4条规则来模拟：

1. C B→W B
2. W B→W X
3. W X→B X
4. B→B

因此Aa aA本身并不是CSG规则，但它生成的语言是。也许不管是谁告诉你的，都是用它作为速记(您可以扩展CSG规则的定义，将这些类型的东西包括为“宏”)。