Lfa linguagens formais e automotas

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (284 palavras )
  • Download(s) : 0
  • Publicado : 9 de setembro de 2012
Ler documento completo
Amostra do texto
LFA - 3ª Lista Exercícios -Linguagens Livres Contexto – Data de entrega: 07/11/11





1- Verificar, usando o LEMA DO BOMBEAMENTO, se as linguagens abaixo são L.C.a) Linguagem onde tenho um ‘a’ à esquerda e ‘b’s à direita


b) { ai bj | j = i }


c) { ai bj | j = 2i }


d) { ai bj | j ≠ i}


e) {ai bi ci | i > 0}





2 - Converta a seguinte gramática à Forma Normal de Chomsky:


S ( 00A | B | 1


A ( 1AA | 2


B ( 0





3 - Dê um APN de umestado que aceite a linguagem { wewR | w ( (d, f)* }


4 - Dê um APN (autômato de pilha) que aceite a linguagem { wwR | w ( (0, 1)* }


6 - Considere a gramáticaG = ({0,1}, {S}, S, {S ( 0S1 | 01})


Escreva o APN que processa tal linguagem.


7 – Dê um APN que aceite a linguagem dos parênteses casados pelo estadofinal.


8 - Considere a seguinte linguagem livre de contexto L = {0n1n / n>=1}. Escreva um APN M que processe essa linguagem. Verifique como M age com as entradas 01 e 011.9 - Seja o seguinte conjunto de produções da gramática livre de contexto G:


S → aaZcc


Z → aZc


Z → b


a) Qual é a linguagemque esta gramática gera?


b) L(G) é regular?


Observe agora o seguinte conjunto de produções da gramática linear à direita G’:


S → aA


A→ aBB → aB / bC


C →cC / cD


D →c


c) Qual é a relação entre G e G’? São equivalentes? Por que?


d) Escreva o autômato de pilha queprocessa L(G).






10 - Escreva a gramática para a linguagem com cadeias que contenham um único a à esquerda e n b´s à direita: abn, n>0. Qual o tipo desta linguagem?
tracking img