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

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 быть посчитанным в процессе строительства. Чтобы показать, что это не зависит от контекста, я хотел бы использовать Pump Lemma .

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

S-> Asc | A-> BAC | λ

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