[anterior] [seguinte]

Pergunta

a) represente sob a forma gramatical o conjunto:

L = { aⁿ b^m cⁿ⁺¹ d^m+1 | m, n >= 0 }

b) Apresente uma sequência de derivações a realizar, par a obter a expressão abbccddd

Resposta

a) A gramática indicada não é do tipo 3 porque possui autocontenção. Também não é do tipo 2 porque a condição imposta só pode ser satisfeita com dependência de contexto. Por estes motivos a gramática é de tipo 1 (a gramática abaixo por motivos de simplificação é do tipo 0).

  S' → aSC' |  BC'
  S → aSc | Bc
  B → bBD | D
  Dc → cD
  DC' → C'D
  C'D → cd
  dD → dd

b) S' ⇒¹ aSC' ⇒² aBcC' ⇒³ abBDcC' ⇒⁴ abbBDDcC' ⇒⁵ aabbDDDcC' ⇒⁶ aabbDDcDC' ⇒⁷ aabbDcDDC' ⇒⁸ aabbcDDDC' ⇒⁹ aabbcDDC'D ⇒¹⁰ aabbcDC'DD ⇒¹¹ aabbcC'DDD ⇒¹² aabbccdDD ⇒¹³ aabbccddD ⇒¹⁴ aabbccddd

[anterior] [seguinte]

Ultima alteração: quinta-feira, 28 de Dezembro de 2000 às 19:13