Página 1 de 1

Fundamentos teóricos da computação - dúvida

MensagemEnviado: 13 Jan 2016 10:59
por chrdcv
uma dúvida de uma prova de teoria da computação:

A -> A quadrado B | A estrela | B
B -> C gravata B
C -> c

quadrado, estrela e gravata são operadores entre não terminais A,B e C

A questão pede qual a associatividade dos operadores (direita, esquerda); bem como a precedência dos mesmos.

A minha dúvida já parte da questão mais básica para tentar resolver o que se pede. Fui tentar derivar a gramática dada com as regras de produção, mas então, vejo que há uma recursão infinita no símbolo não terminal B. Por exemplo:

Derivação mais à esquerda:
A => A quadrado B => B quadrado B => C gravata B quadrado B => c gravata C gravata B quadrado B => c gravata c gravata B quadrado B

Derivação mais à direita:
A => A quadrado B => A quadrado B gravata C => A quadrado B gravata c => A quadrado C gravata B gravata c

Como fica a derivação para o não terminal B?