контекстно-зависимая грамматика

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, если вы не уверены, что вы будете иметь непустой строки.