Como posso construir uma gramática que gera essa linguagem?
-
06-07-2019 - |
Pergunta
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?
Solução
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 .
Outras dicas
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'.
S -> X
X -> aXc | Y
Y -> bYc | e
onde e == epsilon
e X
é desnecessário, mas
adicionados para maior clareza
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
caras bem, é assim que eu vou fazê-lo:
P={S::=X|epsilon,
X::=aXc|M|epsilon,
M::=bMc|epsilon}