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

Я ищу контекстно-зависимую грамматику, которая описывает следующий язык:

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

У меня есть проблемы с тем фактом, что никакие правила, такие как X -> ε, не допускаются, и поэтому я не могу поместить нетерминал, указывающий "середину" слова. Есть ли уловка в проблеме?
Если вы знаете ответ, пожалуйста, помогите.

Источник

1 ответ

Конечно, это на самом деле просто. В контекстно-зависимой грамматике у вас могут быть строки на LHS; это контекст. Допустим, вы получили строку, подобную этой:

abababWababab

Хорошо, так что вы не хотите, чтобы такое правило

W := -empty-

Отлично. Как насчет этих правил?

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

Конечно, это означает, что вы должны избегать W если вы не уверены, что у вас будет непустая строка.

Источник
Другие вопросы по тегам