Questão 3 - (8 pontos) - Dada a gramática:
S a lambda lambda
A A 14 / b B
B b R 1 S
C c C l c
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:
S & a lambda lambda A & A,14 mid b,B B & b,R,1,S C & c,C,l,c
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:
A1
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:
A a,alpha
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:
  1. Criar uma nova variável $ A’ $.
  2. Reescrever as produções sem a recursão à esquerda.
Então, temos:
A A,A4 mid b,B

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:
S a,lambda,lambda
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:
B b,R1,S
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’ $:
B b,R1,S

Passo 7

Agora, reunindo todas as produções ajustadas, a gramática na Forma Normal de Greibach fica:
S & a A & b,B,A' A' & A4,A' mid lambda B & b,R1,S C & c,C' C' & C,l,c

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 é:
S & a A & b,B,A' A' & A4,A' mid lambda B & b,R1,S C & c,C' C' & C,l,c

Exercícios relacionados