Контекстная грамматика для КЛЛ

Question

enter code hereПривет, это мой вопрос

Дайте контекстно-свободную грамматику для КЛЛL = {a^nb^mc^n | m, n ∈ N0}

Мой ответ S-> ASC| B A-> aA| a B-> bB| b C-> cC| c

Будь мой ответ или нет? Я не уверен в этом. Нужна помощь. заранее спасибо

Answer 1

Ваша грамматика порождает язык

L = {a^n b^m c^k | m, n, k ∈ N0}

потому что количество раз, когда применяются правила A->aA и C->cC, являются независимыми. Если вы хотите n=k, то вы должны сгенерировать a и c в одном и том же правиле. Например, вот так:

S -> aSc | B .

На втором этапе вы генерируете произвольное число b в середине:

B -> bB | <empty string> .