Exercício 07.66

Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {0, 1}, que reconheça a linguagem L = {w | w ??0??1??, podendo ? ser 0 ou 1}.


Resposta

G = ({D0, D1, D2, D3, D4, D5, D6, D7}, {0, 1}, P, D7)
P = {< D7 > -> < D0 > < D6 >
     < D6 > -> < D0 > < D5 >
     < D5 > -> 0 < D4 >
     < D4 > -> < D0 > < D3 >
     < D3 > -> < D0 > < D2 >
     < D2 > -> 1 < D1 >
     < D1 > -> < D0 > < D0 >
     < D0 > -> 0  |  1  }

Recomendamos

cert.br Kinghost Java Magazine