Problema: Conversão ER para gramática regular

Olá Pessoal,




Surgiu um pequeno problema, no algoritmo de conversão de ER para gramática regular que mostrei na terça não tenho certeza de que ele não gera gramática recursiva pela direta. Caso a gramática seja recursiva pela direta, ao fazer o backtracking o algoritmo encontrará a recursão e nunca irá percorrer a árvore.

Não sei porque não consegui estudar gramática ainda, alguém sabe como verificar se uma gramática é recursiva pela diretia?



-Outra coisa, não ficou muito bem ainda definido como realizar as substituições nas cadeias a partir da árvore de análise sintática.



-Caso tenhamos que realizar alguma conversão na gramática não sei se podemos perder as sub-expressoes do operador {} da ER.



-Uma gramática ambígua pode ser utiliza no parsing LL?



Estou escrevendo os textos, caso alguém possa responder estas questões e/ou a solução ...