Questão 01

Quando se consideram linguagens especificadas por meio de gramáticas livres de contexto, deve-se também considerar de que forma é feita a aceitação sintática de suas sentenças para fins de compilação e/ou interpretação. Quando se trata de efetuar o reconhecimento de sentenças, o que se busca, na verdade, é localizar uma sequência de produções que, quando aplicada à raiz da gramática, forneça como resultado, por meio da série correspondente de derivações, a sentença fornecida para análise. Sendo possível completar a derivação, diz-se que a sentença pertence à linguagem; caso contrário, que ela não pertence à linguagem.

Por exemplo, a derivação da sentença a + a sobre a gramática livre de contexto G₁ pode produzir a sequência de derivação E ⇒ T + E ⇒ F + E ⇒ F + T ⇒ a + T ⇒ a + F ⇒ a + a, na qual foram aplicadas seis produções, sendo elas (1), (4), (2), (6), (4), (6).

G₁ = ({E, T, F}, {a, +, *, (, )}, P₁, E)
P₁ = {E → T + E  (1)
     E → T      (2)
     T → F * T  (3)
     T → F      (4)
     F → ( E )  (5)
     F → A }    (6)

Conforme exposto, para o reconhecimento da sentença x = w + x * y - z / w sobre a gramática livre de contexto G₂, é necessária a aplicação de quantas produções?

G₂ = ({A, B, C, D}, {w, x, y, z, =, +, -, *, /}, P₂, A)
P₂ = {A → D = B
     B → C + B | C - B | C
     C → D * C | D / C | D
     D → w | x | y | z}

a. 14 produções.

b. 15 produções.

c. 16 produções.

d. 17 produções.

e. 18 produções.

Para se descobrir a solução da questão, é necessário realizar a derivação (à extrema esquerda ou à extrema direita) da sentença x = w + x * y - z / w sobre a gramática livre de contexto G₂.

Derivação à extrema esquerda da sentença x = w + x * y - z / w sobre a gramática livre de contexto G₂.

A → D = B     (01) A
D → x         (02) D = B
B → C + B     (03) x = B
C → D         (04) x = C + B
D → w         (05) x = D + B
B → C - B     (06) x = w + B
C → D * C     (07) x = w + C - B
D → x         (08) x = w + D * C - B
C → D         (09) x = w + x * C - B
D → y         (10) x = w + x * D - B
B → C         (11) x = w + x * y - B
C → D / C     (12) x = w + x * y - C
D → z         (13) x = w + x * y - D / C
C → D         (14) x = w + x * y - z / C
D → w         (15) x = w + x * y - z / D
                   x = w + x * y - z / w

Derivação à extrema direita da sentença x = w + x * y - z / w sobre a gramática livre de contexto G₂.

A → D = B     (01) A
B → C + B     (02) D = B
B → C - B     (03) D = C + B
B → C         (04) D = C + C - B
C → D / C     (05) D = C + C - C
C → D         (06) D = C + C - D / C
D → w         (07) D = C + C - D / D
D → z         (08) D = C + C - D / w
C → D * C     (09) D = C + C - z / w
C → D         (10) D = C + D * C - z / w
D → y         (11) D = C + D * D - z / w
D → x         (12) D = C + D * y - z / w
C → D         (13) D = C + x * y - z / w
D → w         (14) D = D + x * y - z / w
D → x         (15) D = w + x * y - z / w
                   x = w + x * y - z / w

Como pode ser observado, para o reconhecimento da sentença x = w + x * y - z / w sobre a gramática livre de contexto G₂, foram necessárias a aplicação de quinze produções.