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 Extra

Questão Extra

As formas normais estabelecem restrições rígidas na definição das produções, sem reduzir o poder de geração das Gramáticas Livres de Contexto, sendo usadas principalmente no desenvolvimento de algoritmos (com destaque para reconhecedores de linguagens) e na prova de teoremas. Por exemplo, diz-se que uma Gramática Livre de Contexto G = (V, Σ, P, S) obedece à Forma Normal de Greibach se todas as suas produções p ∈ P forem da forma:

A → σα, σ ∈ Σ, α ∈ N*

Conforme exposto, apresente a Forma Normal de Greibach da gramática livre de contexto a seguir.

G = ({S, W, A}, {x, y, z}, P, S)
P = {S → WA | z
     W → WAy | y
     A → SxW}

Solução da Questão Extra

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

A gramática livre do contexto já está simplificada.

G = ({S, W, A}, {x, y, z}, P, S)
P = {S → WA | z
     W → WAy | y
     A → SxW}

2. Renomeação das variáveis em uma ordem crescente qualquer

G = ({A, B, C}, {x, y, z}, P, A)
P = {A → BC | z
     B → BCy | y
     C → AxB}

4. Exclusão das recursões da forma A_r → A_rα

G = ({A, B, B0, C}, {x, y, z}, P, A)
P = {A → BC | z
     B → yB0 | y
     B0 → CyB0 | Cy
     C → AxB}

3. Transformação de produções para a forma A_r → A_sα, onde r ≤ s

G = ({A, B, B0, C}, {x, y, z}, P, A)
P = {A → BC | z
     B → yB0 | y
     B0 → CyB0 | Cy
     C → yB0CxB | yCxB | zxB}

5. Um terminal no início do lado direito de cada produção

G = ({A, B, B0, C}, {x, y, z}, P, A)
P = {A → yB0C | yC | z
     B → yB0 | y
     B0 → yB0CxByB0 | yCxByB0 | zxByB0 | yB0CxBy | yCxBy | zxBy
     C → yB0CxB | yCxB | zxB}

6. Produções da forma A → aα onde α é composto por variáveis

G = ({A, B, B0, C, X0, X1, X2, X3, X4, X5, X6, X7, X8, Y0, Y1, Y2, Y3, Y4, Y5}, {x, y, z}, P, A)
P = {A → yB0C | yC | z
     B → yB0 | y
     B0 → yB0CX0BY0B0 | yCX1BY1B0 | zX2BY2B0 | yB0CX3BY3 | yCX4BY4 | zX5BY5
     C → yB0CX6B | yCX7B | zX8B
     X0 → x
     X1 → x
     X2 → x
     X3 → x
     X4 → x
     X5 → x
     X6 → x
     X7 → x
     X8 → x
     Y0 → y
     Y1 → y
     Y2 → y
     Y3 → y
     Y4 → y
     Y5 → y}