Exercício 08.49

Converta para a Forma Normal de Greibach a gramática:

G = ({S, A, B, C}, {a, b, c}, P, S)
P = {< S >  ->  < B > < A >
     < A >  ->  < A > < A > < C >
            |   a
     < B >  ->  < A > < A > < B >
            |   < C > b
     < C >  ->  < S > < C >
            |   c }

Resposta

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

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

G = ({S, A, B, C}, {a, b, c}, P, S)
P = {< S >  ->  < B > < A >
     < A >  ->  < A > < A > < C >
            |   a
     < B >  ->  < A > < A > < B >
            |   < C > b
     < C >  ->  < S > < C >
            |   c }

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

G = ({A, B, C, D}, {a, b, c}, P, A)
P = {< A >  ->  < C > < B >
     < B >  ->  < B > < B > < D >
            |   a
     < C >  ->  < B > < B > < C >
            |   < D > b
     < D >  ->  < A > < D >
            |   c }

4. Exclusão das recursões da forma < Ar > -> < Ar > α

G = ({A, B, B₀, C, D}, {a, b, c}, P, A)
P = {< A >  ->  < C > < B >
     < B >  ->  a < B₀ >
            |   a
     < B₀ > ->  < B > < D > < B₀ >
            |   < B > < D >
     < C >  ->  < B > < B > < C >
            |   < D > b
     < D >  ->  < A > < D >
            |   c }

3. Transformação de produções para a forma < Ar > -> < As > α, onde r ≤ s

G = ({A, B, B₀, C, D}, {a, b, c}, P, A)
P = {< A >  ->  < C > < B >
     < B >  ->  a < B₀ >
            |   a
     < B₀ > ->  < B > < D > < B₀ >
            |   < B > < D >
     < C >  ->  a < B₀ > < B > < C >
            |   a < B > < C >
            |   < D > b
     < D >  ->  a < B₀ > < B > < C > < B > < D >
            |   a < B > < C > < B > < D >
            |   < D > b < B > < D >
            |   c }

4. Exclusão das recursões da forma < Ar > -> < Ar > α

G = ({A, B, B₀, C, D, D₀}, {a, b, c}, P, A)
P = {< A >  ->  < C > < B >
     < B >  ->  a < B₀ >
            |   a
     < B₀ > ->  < B > < D > < B₀ >
            |   < B > < D >
     < C >  ->  a < B₀ > < B > < C >
            |   a < B > < C >
            |   < D > b
     < D >  ->  a < B₀ > < B > < C > < B > < D > < D₀ >
            |   a < B > < C > < B > < D > < D₀ >
            |   c < D₀ >
            |   a < B₀ > < B > < C > < B > < D >
            |   a < B > < C > < B > < D >
            |   c
     < D₀ > ->  b < B > < D > < D₀ >
            |   b < B > < D > }

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

G = ({A, B, B₀, C, D, D₀}, {a, b, c}, P, A)
P = {< A >  ->  a < B₀ > < B > < C > < B >
            |   a < B > < C > < B >
            |   a < B₀ > < B > < C > < B > < D > < D₀ > b < B >
            |   a < B > < C > < B > < D > < D₀ > b < B >
            |   c < D₀ > b < B >
            |   a < B₀ > < B > < C > < B > < D > b < B >
            |   a < B > < C > < B > < D > b < B >
            |   c b < B >
     < B >  ->  a < B₀ >
            |   a
     < B₀ > ->  a < B₀ > < D > < B₀ >
            |   a < D > < B₀ >
            |   a < B₀ > < D >
            |   a < D >
     < C >  ->  a < B₀ > < B > < C >
            |   a < B > < C >
            |   a < B₀ > < B > < C > < B > < D > < D₀ > b
            |   a < B > < C > < B > < D > < D₀ > b
            |   c < D₀ > b
            |   a < B₀ > < B > < C > < B > < D > b
            |   a < B > < C > < B > < D > b
            |   c b
     < D >  ->  a < B₀ > < B > < C > < B > < D > < D₀ >
            |   a < B > < C > < B > < D > < D₀ >
            |   c < D₀ >
            |   a < B₀ > < B > < C > < B > < D >
            |   a < B > < C > < B > < D >
            |   c
     < D₀ > ->  b < B > < D > < D₀ >
            |   b < B > < D > }

6. Produções da forma < Ar > -> a α onde α é composto por variáveis

G = ({A, B, B₀, C, D, D₀, X₀, X₁, X₂, X₃, X₄, X₅, X₆, X₇, X₈, X₉, X₁₀, X₁₁}, {a, b, c}, P, A)
P = {< A >  ->  a < B₀ > < B > < C > < B >
            |   a < B > < C > < B >
            |   a < B₀ > < B > < C > < B > < D > < D₀ > < X₀ > < B >
            |   a < B > < C > < B > < D > < D₀ > < X₁ > < B >
            |   c < D₀ > < X₂ > < B >
            |   a < B₀ > < B > < C > < B > < D > < X₃ > < B >
            |   a < B > < C > < B > < D > < X₄ > < B >
            |   c < X₅ > < B >
     < B >  ->  a < B₀ >
            |   a
     < B₀ > ->  a < B₀ > < D > < B₀ >
            |   a < D > < B₀ >
            |   a < B₀ > < D >
            |   a < D >
     < C >  ->  a < B₀ > < B > < C >
            |   a < B > < C >
            |   a < B₀ > < B > < C > < B > < D > < D₀ > < X₆ >
            |   a < B > < C > < B > < D > < D₀ > < X₇ >
            |   c < D₀ > < X₈ >
            |   a < B₀ > < B > < C > < B > < D > < X₉ >
            |   a < B > < C > < B > < D > < X₁₀ >
            |   c < X₁₁ >
     < D >  ->  a < B₀ > < B > < C > < B > < D > < D₀ >
            |   a < B > < C > < B > < D > < D₀ >
            |   c < D₀ >
            |   a < B₀ > < B > < C > < B > < D >
            |   a < B > < C > < B > < D >
            |   c
     < D₀ > ->  b < B > < D > < D₀ >
            |   b < B > < D >
     < X₀ > ->  b
     < X₁ > ->  b
     < X₂ > ->  b
     < X₃ > ->  b
     < X₄ > ->  b
     < X₅ > ->  b
     < X₆ > ->  b
     < X₇ > ->  b
     < X₈ > ->  b
     < X₉ > ->  b
     < X₁₀ > ->  b
     < X₁₁ > ->  b }

Recomendamos

Revista LibreOffice Magazine Clique Alimentos Clickarvore