上下文敏感語法

Question

我找描述以下語言的上下文敏感語法：

L = { ww | w ∈ {a,b}*, |w| ≥ 1} <br> 

我有這樣一個事實的問題，沒有規則，如X - >ε是允許的，因此我不能放置任何表示單詞「中間」的非終結符。 這個問題有什麼竅門嗎？
如果你碰巧知道答案，請幫忙。

Answer 1

當然，這其實很簡單。在上下文敏感的語法中，你可以在LHS上有字符串;這是上下文。所以我們可以說你最終像這樣的字符串：

abababWababab 

好了，所以你不希望像

W := -empty- 

優秀的規則。這些規則如何？

aWa := aa 
aWb := ab 
bWa := ba 
bWb := bb 

當然，這意味着你應該避免引入W，除非你確信你將有一個非空字符串。