slide6_LFA

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
Linguagens Formais e Autômatos
Exclusão de produções da forma A → B 
O algoritmo é dividido em 2 etapas (Menezes, 1998):
a) Construção do fecho de cada variável. Entende-se por fecho de uma variável o conjunto de variáveis que podem substituí-la transitivamente. Ou seja, se A → B e B → C, então B e C pertencem ao fecho de A; 
b) Exclusão de produções da forma A → B. Substitui as produções da forma A → B por produções da forma A→α, onde α é atingível a partir de A através de seu fecho.
 
*
*
Linguagens Formais e Autômatos
Definição 1.25 Algoritmo para Exclusão das Produções da Forma A → B.
Considere uma GLC G = (VN,T, P, S). O Algoritmo para Exclusão das Produções da Forma A → B é composto por 2 etapas:
a) Construção do fecho de cada variável.
para toda A  VN
faça FECHO-A={B / A ≠ B e A +B
		usando exclusivamente produções da forma X→Y};
b) Exclusão das produções da forma A → B. A gramática resultante desta etapa é G1=(VN,T, P1, S) onde P1 é construído:
 P1={A → α / α  VN} 
para toda A  VN e B  FECHO-A
faça se B → α  P e α  VN então P1= P1  {A→ α}
*
*
Linguagens Formais e Autômatos
EXEMPLO 1.22 Exclusão das Produções da Forma A→B
Considere a seguinte GLC:
G = ({S,X},{a,b},P,S), onde:
P = {S → aXa / bXb, X → a / b / S / }
A exclusão da produção X → S é como segue:
a) Construção do fecho de cada variável.
FECHO-S=		FECHO-X={S}
b)Exclusão das produções da forma A→B.Construção do conjunto de produções (a coluna iteração representa a execução do algoritmo para a variável referenciada):
 
*
*
Linguagens Formais e Autômatos
A gramática resultante é a seguinte:
G = (S,X},{a,b},P,S), onde:
P = {S → aXa / bXb, X → a / b / ε / aXa / bXb}