Turmas - 2º Semestre de 2025
Turmas
2º Semestre de 2025

1. Ybadoo
2. Turmas
3. 2º Semestre de 2025
4. Linguagens Formais e Autômatos
5. Segunda Avaliação
6. Questão 03

Questão 03

Uma gramática livre de contexto é dita normalizada em relação a um certo padrão quando todas as suas produções seguem as restrições impostas pelo padrão em questão. É comum designar tais padrões como formas normais. Por exemplo, diz-se que uma gramática G = (V, Σ, P, S) obedece à Forma Normal de Chomsky se todas as produções p ∈ P forem de uma das duas formas seguintes:

A → BC, ou

A → a

Conforme exposto, converta a gramática livre de contexto apresentada a seguir na Forma Normal de Chomsky.

G = ({E, T, F}, {x, y}, P, E)
P = {E → TFx
     T → yyF
     F → T | ε}

Solução da Questão 03

1. Simplificação da gramática livre do contexto

1.1. Exclusão de Produções Vazias

1.1.1. Identificação das variáveis que constituem produções vazias

1.1.2. Exclusão das produções vazias da gramática

G = ({E, T, F}, {x, y}, P, E)
P = {E → TFx | Tx
     T → yyF | yy
     F → T}

1.1.3. Inclusão da palavra vazia, caso pertença a linguagem gerada pela gramática

G = ({E, T, F}, {x, y}, P, E)
P = {E → TFx | Tx
     T → yyF | yy
     F → T}

1.2. Exclusão de Produções da Forma A → B

1.2.1. Construção dos fechos das variáveis

Fecho(E) = ∅
Fecho(T) = ∅
Fecho(F) = {T}

1.2.2. Exclusão das produções da forma A → B

G = ({E, T, F}, {x, y}, P, E)
P = {E → TFx | Tx
     T → yyF | yy
     F → yyF | yy}

1.3. Exclusão de Símbolos Inúteis

1.3.1. Identificação das variáveis que constituem terminais

G = ({E, T, F}, {x, y}, P, E)
P = {E → TFx | Tx
     T → yyF | yy
     F → yyF | yy}

1.3.2. Identificação dos símbolos alcançáveis a partir do símbolo inicial

G = ({E, T, F}, {x, y}, P, E)
P = {E → TFx | Tx
     T → yyF | yy
     F → yyF | yy}

2. Conversão das produções contendo terminais para a forma A → a

G = ({E, T, F, X0, X1, Y0, Y1, Y2, Y3, Y4, Y5, Y6, Y7}, {x, y}, P, E)
P = {E  → TFX0 | TX1
     T  → Y0Y1F | Y2Y3
     F  → Y4Y5F | Y6Y7
     X0 → x
     X1 → x
     Y0 → y
     Y1 → y
     Y2 → y
     Y3 → y
     Y4 → y
     Y5 → y
     Y6 → y
     Y7 → y}

3. Conversão das produções contendo variáveis para a forma A → BC

G = ({E, E0, T, T0, F, F0, X0, X1, Y0, Y1, Y2, Y3, Y4, Y5, Y6, Y7}, {x, y}, P, E)
P = {E  → TE0 | TX1
     E0 → FX0
     T  → Y0T0 | Y2Y3
     T0 → Y1F
     F  → Y4F0 | Y6Y7
     F0 → Y5F
     X0 → x
     X1 → x
     Y0 → y
     Y1 → y
     Y2 → y
     Y3 → y
     Y4 → y
     Y5 → y
     Y6 → y
     Y7 → y}