Ftc Lista2

1
Pós-Graduação em Ciência da Computação
Teoria de Linguagens
Professor: Newton José Vieira
Aluno: Vilar Fiuza da Camara Neto
Data: 10 de junho de 2002
Segunda Lista de Exercícios
Observação: A definição de “estado útil” de um AFD é utilizada na resolução de alguns problemas: um estado e é dito útil se, e somente se, existem palavras x, y ∈ Σ∗
ˆ x) = e e δ(e,
ˆ y) ∈ F . tais que δ(i,
1. Prove que os seguintes conjuntos não são linguagens regulares, utilizando o lema do bombeamento:
(Considerando que cada conjunto será chamado de L no desenvolvimento de cada questão, e que k, z, u, v e w possuem as definições apresentadas nas notas de aula, ou seja: k é uma constante > 0, z ∈ L e |z| ≥ k, z = uvw e |uv| ≤ k.)
a) {xcx | x ∈ {a, b}∗ }
Resposta: Sendo z = ak cak (z ∈ L). Como |uv| ≤ k, portanto u e v contém somente a’s. Mas uv 0 w = ak−|v| cak . Como v = λ, então uv 0 w ∈
/ L, de onde se conclui que L não é linguagem regular.
b) {xcy | x, y ∈ {a, b}∗ e na (x) = nb (y)}
Resposta: Sendo z = ak cbk (z ∈ L). Como |uv| ≤ k, portanto u e v contém somente a’s. Mas uv 0 w = ak−|v| cbk . Como v = λ, então uv 0 w ∈
/ L, de onde se conclui que L não é linguagem regular.
2

c) {0n | n ≥ 0}
2
Resposta: Sendo z = 0k (z ∈ L). Portanto, é sempre possível obter u e v tais que |uv| ≤ k, e u e v contém somente 0’s. Também se observa que a palavra pertencente a L de tamanho imediatamente superior a z é
2
2 z ′ = 0(k+1) = 0k +2k+1 .
2
Entretanto, uv 2 w = 0k +|v| . Como |uv 2 w| > |z| (pois k2 + |v| > k2 ) e
|uv 2 w| < |z ′ | (pois k2 + |v| < k2 + 2k + 1, já que |v| ≤ k), temos que
/ L, o que prova que L não é linguagem regular. uv 2 w ∈
2. Prove que os seguintes conjuntos são ou não são linguagens regulares, utilizando propriedades de fechamento:
(Considerando que cada conjunto será chamado de L no desenvolvimento de cada questão) a) {0m 1n | m < n} ∪ {0m 1n | m > n}
Resposta: Não regular. Esta linguagem também pode ser descrita da seguinte maneira: L = {0m 1n | m = n}. Supondo que L é