Как я могу построить грамматику, которая генерирует этот язык?
-
06-07-2019 - |
Вопрос
Я готовлюсь к тесту на конечные автоматы и грамматики, и у меня застрял этот вопрос:
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?Я предполагаю, что это скорее контекстно-свободная грамматика, и если да, то какой она должна быть?
Решение
Похоже, что должно быть так:
A->aAc | aBc | ac | epsilon
B->bBc | bc | epsilon
Вы должны заставить C'c быть посчитанным во время процесса строительства. Чтобы показать, что это не зависит от контекста, я хотел бы использовать Лемму насоса . р>
Другие советы
Да, это похоже на домашнюю работу, но намек:
Каждый раз, когда вы соответствуете «а», вы должны соответствовать «с». То же самое для соответствия 'b'.
S -> X
X -> aXc | Y
Y -> bYc | e
где e == epsilon
и X
не нужны, но
добавлено для ясности
S-> asc | a a-> bac | λ
Это означает, что когда вы получаете a, по крайней мере, у вас есть 1 c, а если вы получаете a и b, у вас должно быть 2 c.надеюсь, это было полезно
Ну, ребята, вот как я это сделаю:
P={S::=X|epsilon,
X::=aXc|M|epsilon,
M::=bMc|epsilon}