slide7_LFA

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

*
*
Linguagens Formais e Autômatos
Definição 1.26 Forma Normal de Chomsky. Qualquer LLC pode ser gerada por uma gramática na qual todas produções são da forma A → BC ou A → a; A, B, C  VN e a  VT
(1)GLC qualquer → (2) GLC λ-livre → (3) GLC-FNC
1º) Sempre é possível passar de (1) para (3)?
a) Para garantir o resultado acima é necessário responder: sempre é possível passar (1) para (2).
Lema 1: (1) → (2), o qual diz existe um Algoritmo que transforma qualquer GLC em outra equivalente λ-livre e sem produções da forma A → B (produção inútil). (Hopcroft, 1969) 
2º) Sempre é possível passar de (2) para (3)?
Lema 2: (2) → (3). Por fim, Teorema: (1) → (3) 
*
*
Linguagens Formais e Autômatos
Definição 1.27 Forma Normal de Chomsky. O algoritmo a seguir transforma GLC , cuja L não possui a palavra vazia, em uma FNC.
O algoritmo é dividido em três etapas, como segue (Menezes, 1998):
a) Simplificação da Gramática. Simplifica a gramática excluindo as produções vazias (como a linguagem não possui a palavra vazia, todas produções da forma A → ε podem ser excluídas), produções da forma A → B (se o lado direito de alguma produção tiver somente um símbolo, este será terminal) e, opcionalmente, os símbolos inúteis; 
*
*
Linguagens Formais e Autômatos
b) Transformação do lado direito das produções de comprimento maior ou igual a dois. Garante que o lado direito das produções de comprimento ≥ 2 é composto exclusivamente por variáveis (ou seja, não-terminais). A exclusão de um terminal a pode ser realizada substituindo-o por uma variável intermediária Ca e incluindo a produção Ca → a;
*
*
Linguagens Formais e Autômatos
c) Transformação do lado direito das produções de comprimento maior ou igual a três, em produções com exatamente duas variáveis. Garante que o lado direito das produções de comprimento > 1 é composto exatamente por 2 variáveis. Após a execução da etapa acima, o lado direito de P são da forma A→ B1B2…Bn (n ≥ 2) é composto exclusivamente por variáveis. Portanto, para concluir a transformação, é suficiente garantir que o lado direito é composto por exatamente por 2 variáveis. Isto é possível gerando B1B2…Bn em diversas etapas, usando variáveis intermediárias. 
 
*
*
Linguagens Formais e Autômatos
Definição 1.28 Algoritmo p/ transformar GLC na FNC
Considere uma GLC G = (VN, T, P, S), tal que ε  L(G). O algoritmo é o seguinte:
a) Etapa 1: Simplificação da Gramática. As seguintes simplificações nesta seqüência é recomendada:
 exclusão das produções vazias;
 exclusão de produções da forma A → B;
 exclusão de símbolos inúteis (opcional);
devem ser realizadas usando algoritmos de simplificações (Menezes, 1998) resultante na gramática 				G1 = (V1, T1, P1, S)
  
*
*
Linguagens Formais e Autômatos
b) Etapa 2: Transformação do lado direito das produções de comprimento maior ou igual a dois. A gramática resultante desta etapa é:
			G2 = (V2, T1, P2, S)
onde V2 e P2 são construídos como segue:
V2 = V1;
P2 = P1;
para toda A → X1X2...Xn  P2 tal que n ≥ 2
faça se para r  {1,2,...,n}, Xr é um símbolo terminal
 		então (suponha Xr = a)	
		 V2 = V2  {Ca};
		substitui a pela variável Ca em A → X1X2...Xn  P2; 	 P2 = P2  {Ca → a};
*
*
Linguagens Formais e Autômatos
c) Etapa 3: Transformação do lado direito das produções de comprimento maior ou igual a três em produções com exatamente duas variáveis. A gramática resultante desta etapa é
			G3 = (V3, T1, P3, S)
onde V3 e P3 são construídos como segue:
V3 = V2;
P3 = P2;
para toda A → B1B2...Bn  P3 tal que n ≥ 3
faça P3 = P3 - {A → B1B2...Bn};
 		V3 = V3  {D1,...,.Dn-2};
		P3 = P3  {A→ B1D1, D1→B2D2 ,...
				Dn-3→Bn-2Dn-2, Dn-2→Bn-1Bn};