Как я могу построить грамматику, которая генерирует этот язык?

Question

Я готовлюсь к тесту на конечные автоматы и грамматики, и у меня застрял этот вопрос:

Construct a grammar that generates L:
L = {a^n b^m c^m+n|n>=0, m>=0}

Я считаю, что мои постановки должны идти по следующему пути:

    S->aA | aB
    B->bB | bC
    C->cC | c Here's where I have doubts

Как моя продукция для C может запомнить числа m и n?Я предполагаю, что это скорее контекстно-свободная грамматика, и если да, то какой она должна быть?

Answer 1

Похоже, что должно быть так:

A->aAc | aBc | ac | epsilon
B->bBc | bc | epsilon

Вы должны заставить C'c быть посчитанным во время процесса строительства. Чтобы показать, что это не зависит от контекста, я хотел бы использовать Лемму насоса .

Answer 2

Да, это похоже на домашнюю работу, но намек:

Каждый раз, когда вы соответствуете «а», вы должны соответствовать «с». То же самое для соответствия 'b'.

Answer 3

S -> X
X -> aXc | Y
Y -> bYc | e

где e == epsilon и X не нужны, но добавлено для ясности

Answer 4

S-> asc | a a-> bac | λ

Это означает, что когда вы получаете a, по крайней мере, у вас есть 1 c, а если вы получаете a и b, у вас должно быть 2 c.надеюсь, это было полезно

Answer 5

Ну, ребята, вот как я это сделаю:

P={S::=X|epsilon,
   X::=aXc|M|epsilon,
   M::=bMc|epsilon}