Linguagens formais e automatos

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 de Turing 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, b e 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 da direita 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 o porquê. 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