Търся чувствителна към контекста граматика, която описва следния език:
L = { ww | w ∈ {a,b}*, |w| ≥ 1} <br>
Имам проблеми с факта, че не са разрешени правила като X -> ε и следователно не мога да поставя никакъв нетерминал, указващ "средата" на думата. Има ли някакъв трик за проблема?
Ако случайно знаете отговора, моля помогнете.
Разбира се, това всъщност е лесно. В чувствителна към контекста граматика можете да имате низове в LHS; това е контекста. Да кажем, че в крайна сметка имате низ като този:
abababWababab
Добре, значи не искате правило като
W := -empty-
Отлично. Какво ще кажете за тези правила?
aWa := aa
aWb := ab
bWa := ba
bWb := bb
Разбира се, това означава, че трябва да избягвате въвеждането на W, освен ако не сте сигурни, че ще имате непразен низ.
