Como posso construir uma gramática que gera essa linguagem?

Question

Eu estou estudando para um autômatos finitos e gramáticas teste e eu estou preso com esta pergunta:

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

Eu acredito que minhas produções deve ir junto estas linhas:

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

Como pode a minha produção para C lembrar os números de m e n? Estou descobrindo isso deve sim ser uma gramática livre de contexto, em caso afirmativo, como deve ser?

Answer 1

Parece que ele deve ser como:

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

Você precisa forçar C'C a ser contado durante o processo de construção. A fim de mostrar que é livre de contexto, eu consideraria usar Bomba Lema .

Answer 2

Sim, isso soa como lição de casa, mas uma dica:

Cada vez que você coincidir com um 'a', você deve coincidir com um 'c'. Mesmo para combinar um 'b'.

Answer 3

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

onde e == epsilon e X é desnecessário, mas adicionados para maior clareza

Answer 4

S-> aSc | A A-> BAC | ?

Isto significa que quando cada vez que você começa a pelo menos você tem um c ou se você receber um e b você deve ter 2 c. Espero que tenha sido útil

Answer 5

caras bem, é assim que eu vou fazê-lo:

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