Linguagens formais e automatos

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (503 palavras )
  • Download(s) : 0
  • Publicado : 2 de dezembro de 2012
Ler documento completo
Amostra do texto
Lista 4: Linguagens Sensíveis ao contexto Data de entrega (individual) : 03/12/2012 1) Construa uma máq. Turing que aceite a linguagem (a+b)*, na qual há menos as do que bs. 2) Escreva uma máq.Turing que aceite a linguagem (a+b)*, na qual há mais as do que bs. 3) Construa uma máquina de Turing que aceite o conjunto de todas as sentenças que contenham dois 0s consecutivos ou dois 1s consecutivos.4) Para cada uma das linguagens abaixo, desenvolva uma máquina de Turing que a aceite e que sempre pare para qualquer entrada a. {ai bj ck / i = j ou j = k} b. {anbncn+1/n>=0} 5) Relativamente àclasse das linguagens recursivas e à classe das linguagens recursivamente enumeráveis, qual a diferença fundamental entre as duas classes? 6) Para cada uma das linguagens abaixo, desenvolva uma máquina deTuring com fita limitada que a aceite e que sempre pare para qualquer entrada: a. {w ∈ {a,b}* / o quinto símbolo da direita para a esquerda de w é a} b. {w / e possui o mesmo número de símbolos a, be c} c. {anbman+m/ n>=0 e m>=0} 7) Qual o tipo de menor complexidade de cada uma das linguagens abaixo. De acordo com o tipo, construa uma gramática equivalente: a. {w ∈ {a,b}* / o quinto símbolo dadireita para a esquerda de w é a} b. {anbman+m/ n>=0 e m>=0} 8) Por que nem toda gramática livre de contexto é sensível ao contexto, embora toda linguagem livre de contexto seja sensível ao contexto?Há alguma solução para este problema? 9) Considere a linguagem: L = {w / w ∈ (a+b)* com número par de as}. Por exemplo, a cadeia abbabaa seria aceita, enquanto a cadeia baabba não. a. Se possível,escreva uma máquina de Turing limitada linearmente que processe L. Caso não seja possível, explique o porquê. b. Se possível, escreva um autômato a pilha que processe L. Caso não seja possível, explique oporquê. c. Qual o tipo e menor complexidade de L? Por quê? 10) Seja o seguinte conjunto de produções de uma gramática livre de contexto G: P = {S→AB , A → 0, A→1, A →ε, B→1} a. L(G) é sensível ao...
tracking img