Контекстно-свободная грамматика для CFL

enter code hereЗдравствуйте, это мой вопрос

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

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

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


regex finite-automata context-free-grammar chomsky-normal-form context-free-language
person Ejaz Ahamed    schedule 20.06.2017    source источник
comment
Что такое N0 в вашем вопросе?   -  person Ray Toal    schedule 20.06.2017
comment
Также это не вопрос программирования. Я думаю, вам больше повезет на компьютерахcience.stackexchange.com или cstheory.stackexchange.com.   -  person Ray Toal    schedule 20.06.2017
comment
@ray: cstheory.se предназначен для вопросов исследовательского уровня в теоретической информатике. Этот вопрос не подходит. Cs.se подходит для простых вопросов о CFG, но проверьте, что мои домашние задания не рекомендуются, даже в большей степени, чем здесь. Предложение перенести вопрос на сайт, для которого он не подходит, никому не приносит пользы.   -  person rici    schedule 20.06.2017
comment
@ejaz: сгенерируйте первые несколько предложений из вашей грамматики. Являются ли они частью языка? Если нет, то вы знаете, что грамматика неверна.   -  person rici    schedule 20.06.2017

Ответы (1)


arrow_upward
3
arrow_downward

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

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> .
person Peter Leupold    schedule 22.06.2017