Questão 3 - (8 pontos) - Dada a gramática:
B) Coloque a gramática na Forma Normal de Greibach e efetue a fatoração à esquerda na mesma. ( 6 pontos)
B) Coloque a gramática na Forma Normal de Greibach e efetue a fatoração à esquerda na mesma. ( 6 pontos)
Passo 1
Beleza, vamos entender o que a questão está pedindo. Temos uma gramática definida por algumas regras de produção e precisamos transformá-la na Forma Normal de Greibach (FNG). Além disso, precisamos fatorar à esquerda essa gramática. Para fazer isso, vamos precisar conhecer alguns conceitos básicos de gramáticas formais, como eliminação de recursão à esquerda e a própria definição da FNG.
Passo 2
Primeiro, vamos analisar a gramática dada:
Parece que há alguns símbolos estranhos como “14” e “1”. Vou assumir que há um pequeno erro de digitação e interpretar os números como parte de variáveis (por exemplo, $ A1 $, $ R1 $). Então, reescrevendo a gramática:
Aqui, $ \lambda $ representa a cadeia vazia.
Passo 3
Agora, para colocar a gramática na Forma Normal de Greibach (FNG), precisamos garantir que todas as produções estejam no formato:
onde $ a $ é um terminal e $ \alpha $ é uma cadeia de variáveis.
Primeiro, vamos eliminar as produções onde a variável à esquerda está na forma recursiva à esquerda, como $ A \rightarrow A,A_4 $.
Passo 4
Eliminando Recursão à Esquerda:
A produção $ A \rightarrow A,A_4 \mid b,B $ é recursiva à esquerda. Para eliminar essa recursão, seguimos os seguintes passos:
- Criar uma nova variável $ A’ $.
- Reescrever as produções sem a recursão à esquerda.
Então, temos:
Passo 5
Agora, ajustamos as outras produções para se adequarem à FNG.
Para $ S \rightarrow a,\lambda,\lambda $, como $ \lambda $ é a cadeia vazia, podemos simplificar para:
Já a produção $ B \rightarrow b,R_1,S $ está quase na FNG, mas temos duas variáveis $ R_1 $ e $ S $ após o terminal $ b $. A FNG permite apenas uma sequência de variáveis após o terminal, então precisamos garantir que isso seja válido ou ajustar conforme necessário.
A produção $ C \rightarrow c,C,l,c $ também precisa ser ajustada para a FNG, pois temos mais de uma variável após o terminal $ c $.
Passo 6
Ajustando as Produções para a FNG:
Para $ B \rightarrow b,R_1,S $, já está no formato da FNG:
Para $ C \rightarrow c,C,l,c $, precisamos ajustar para ter apenas uma variável após o terminal. Podemos introduzir uma nova variável $ C’ $:
Passo 7
Agora, reunindo todas as produções ajustadas, a gramática na Forma Normal de Greibach fica:
Passo 8
Fatoração à Esquerda:
Vamos verificar se há produções que podem ser fatoradas à esquerda. Observando as produções:
- $ A \rightarrow b,B,A’ $
- $ A’ \rightarrow A_4,A’ \mid \lambda $
- $ B \rightarrow b,R_1,S $
- $ C \rightarrow c,C’ $
- $ C’ \rightarrow C,l,c $
Não há produções que começam com o mesmo prefixo que precisem de fatoração à esquerda.
Resposta
A gramática na Forma Normal de Greibach e já com a fatoração à esquerda efetuada é: