J.L.Rangel - 1
Linguagens Formais: Lista 2
Rangel 5/7/99
1. Mostre que a linguagem { a2n bn cn | n>0 } é sensível ao contexto, construindo um all
que reconheça a linguagem.
2. Mostre que o conjunto Int2 = Int × Int de pares de inteiros é recursivamente
enumerável, construindo uma mT que justifique a afirmativa.
3. Construa um autômato de pilha A que aceita { ai bi | i ≥ 1 } simultaneamente, por
pilha vazia e por estado final.
4. Classifique a linguagem { ambncmdn | m, n ≥ 0 }, dizendo se ela é ou não
recursivamente enumerável, recursiva, tipo 0, tipo 1, tipo 2, tipo 3.
5. Mostre que a classe das linguagens sensíveis ao contexto é fechada para a interseção.
6. Mostre que a concatenação de dois conjuntos recursivamente enumeráveis é sempre
recursivamente enumerável, mostrando como é possível construir uma mT que aceita a
concatenação das linguagens de duas mT’s dadas.
7. Definição: a reversão da linguagem L é a linguagem LR = { x | xR ∈ L }. Prove ou desprove:
(a)
(b)
(c)
(d)
(e)
(f)
A classe das linguagens regulares é fechada para a reversão.
idem, livres de contexto.
idem, determinísticas
idem, sensíveis ao contexto.
idem, recursivas.
idem, recursivamente enumeráveis.
8. Construa uma máquina de Turing determinística que aceite a linguagem
{xx | x ∈{ a, b }* }.
Mostre a sequência de configurações da máquina que levam à aceitação da cadeia
aaabaaab.
9. Mostre que a linguagem { ai bj | i≠j } é determinística.
10. Prove ou des-prove: A interseção de uma linguagem livre de contexto e uma
linguagem regular é livre de contexto.
11. Mostre que a linguagem { xi $ xj | Mi aceita xj } é recursivamente enumerável,
descrevendo uma máquina de Turing que enumera os elementos da linguagem.
12. Prove ou desprove: as linguagens L = { x xR | x ∈ { 0, 1 }* } e seu complemento são
não determinísticas.
J.L.Rangel - 2
13. (*) Usando o fato de que todo subconjunto de um conjunto enumerável é enumerável,
mostre que todo subconjunto de um conjunto recursivamente enumerável é
recursivamente enumerável.
14. Mostre que, se A e B são conjuntos recursivamente enumeráveis, então A×B também
é recursivamente enumerável.
15. Construa um all que reconheça a linguagem da gramática G
S → aSa | bSb | T
T → cT | c
simulando derivações em G.
16. Mostre que a linguagem { an bn cn dn | n>0 }é sensível ao contexto, construindo um
all que reconheça a linguagem.
17. Classifique a linguagem L={ ai bj | i é múltiplo de j }, dizendo se L é recursivamente
enumerável, recursiva, regular, sensível ao contexto, livre de contexto, tipo 0.
18. Justifique a afirmação “A classe dos conjuntos recursivos é fechada para a operação de
complemento.” usando uma definição de algoritmo baseada em máquinas de Turing.
19. Prove ou desprove: a linguagem { x c y | x, y ∈ {a, b}* e |x| > |y| } é determinística.
20. Mostre como construir uma mT que aceite a união de duas linguagens reconhecidas
por mT’s.
21. Seja x0, x1, x2,... uma enumeração das cadeias em um alfabeto S; seja M0, M1, M2,...
uma enumeração das máquinas de Turing.
Mostre que a linguagem { i#j | Mi aceita xj } (no alfabeto S = {0, 1, # } ) é recursivamente
enumerável. Os números i e j são representados em notação binária.
22. Construa um automato de pilha não determinístico que aceite por pilha vazia a
linguagem { ai bj ck | j=i+k }
23. Construa um automato de pilha não determinístico que aceite por estado final a
linguagem
{ a2n+1 bn | n > 0 }
24. Mostre que a linguagem { x c y | x, y ∈ {a, b}* e |x| > |y| } é livre de contexto,
construindo um apnd que reconheça a linguagem.
25. Construa uma máquina de Turing que aceite a linguagem
{x#y#z | x,y,z∈{0,1}*, e z é a representação em binário da soma dos
J.L.Rangel - 3
naturais representados por x e y}
26. Seja Σ = { 0, 1, c }. Construa uma máquina de Turing determinística que aceita a
linguagem { xcy | x, y ∈ {0, 1}*, e |x| ≠ |y| }.
27. Idem, não determinística.
28. Construa uma máquina de Turing universal. Defina cuidadosamente as codificações
envolvidas.
29. Defina um a2pnd (autômato de duas pilhas, não determinístico) da seguinte maneira:
Um a2pnd é uma construção A = < K, Σ, Γ1, Γ2, δ, i, I1, I2 > onde
K é um conjunto finito de estados
Σ é o alfabeto de entrada
Γ1 e Γ2 são os alfabetos das duas pilhas
δ:K×(Σ∪{ε})×Γ1×Γ2 → P( K×Γ1*×Γ2*)
i é o estado inicial
I1 e I2 são os símbolos iniciais das duas pilhas.
Adicionalmente, duas restrições se aplicam:
• se (p, α, β) ∈ δ(q, a, X, Y), então |α| = |β|.
• δ(q, a, X, Y) é sempre um conjunto finito
Uma configuração de um a2pnd é um elemento de K×Σ*×Γ1*×Γ2*. A configuração inicial
para a entrada x ∈ Σ* é ( i, x, I1, I2 ). Uma configuração é final se pertence a
K×{ε}×{ε}×{ε}, ou seja, a aceitação do a2pnd é por “pilhas vazias”. A relação mudança
de configuração | é dada por:
( q, ay, X1α1, X2α2 ) | ( p, y, γ1α1, γ2α2 ) se ( p, γ1, γ2 ) ∈ δ( q, a, X1, X2 )
e a linguagem do a2pnd A é
L(A) = { x ∈ Σ* | ( i, x, I1, I2 ) |* (p, ε, ε, ε ), para algum p∈K.
Caracterize precisamente a classe das linguagens aceitas por um a2pnd.
Justifique seus resultados.
30. Construa (mesmo) uma máquina de Turing determinística que aceite a linguagem L2 =
{ x ∈ {a,b}* | número de a’s em x = número de b’s em x }.