Turmas - 2º Semestre de 2014
Turmas
2º Semestre de 2014

Apresente uma derivação à extrema esquerda (DEE) da sentença A := A * (B + C) sobre a gramática a seguir:

G = ({atr, exp, ter, fat, id, A, B, C, :, =, +, *, (, )}, {A, B, C, :, =, +, *, (, )}, P, atr)
P = { < atr > ::= < id > := < exp >
      < exp > ::= < exp > + < ter > | < ter >
      < ter > ::= < ter > * < fat > | < fat >
      < fat > ::= ( < exp > ) | < id >
      < id >  ::= A | B | C }

Dada a expressão regular a(a + b)*b:

1. Construa, usando o algoritmo de Thompson, o autômato finito não-determinístico com movimentos vazios para reconhecer sentenças dessa linguagem.
2. Converta, usando o método da construção de subconjuntos, o autômato do item a para um autômato finito determinístico.
3. Minimize, se possível, o número de estados do autômato do item b.

Simplifique por meio do algoritmo de Exclusão de Produções Vazias a gramática a seguir.

G = ({A, B, C, D, E, F, G, H, x, y, z}, {x, y, z}, P, A)
P = { < A > ::= < F > | z < B > < C >
      < B > ::= < G > x | y < A > < D > z
      < C > ::= < A > < D > | y z | < B > < H >
      < D > ::= < C > x y | ε | < A > z
      < E > ::= < C > < D > < A > | y
      < F > ::= < D > | < A > x < C > < D > y < A >
      < G > ::= < E > < A > | x y < E >
      < H > ::= < A > y < C > | < D > < C > z }

Simplifique por meio do algoritmo de Exclusão de Símbolos Inúteis a gramática a seguir.

G = ({S, A, B, C, D, F, H, a, b, c, d}, {a, b, c, d}, P, S)
P = { < S > ::= < A > < C > < H > | < B > < B >
      < A > ::= a < A > | a < F >
      < B > ::= < C > < F > < H > | b
      < C > ::= a < C > | < D > < H >
      < D > ::= a < D > | < B > < D > | < C > a
      < F > ::= b < B > | b
      < H > ::= d < H > | d }

Converta para a Forma Normal de Chomsky a gramática a seguir.

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