Questão 3 (valor = 45 pontos). Classifique as seguintes linguagens em (1) regular,
(2) livre do contexto e (3) nem regular, nem livre do contexto, dando uma justificativa
para cada uma de suas afirmações.
ATENÇÃO : RESPOSTAS SEM JUSTIFICATIVAS NÃO SERÃO CONSIDERADAS
Se você responder (1), é preciso dar um autômato que reconheça exatamente a linguagem. Se você responder (2), é preciso dar uma gramática livre do contexto que gere
exatamente a linguagem E provar, usando o pumping lemma para linguagens regulares,
que a linguagem não é regular. Se você responder (3), é preciso provar, usando o pumping
lemma para linguagens livres do contexto, que a linguagem não é livre do contexto.
1. L = {0n 1m 2m | n ≥ 1, m ≥ 1}
Solução
(a) A linguagem é livre do contexto. Uma gramática que a gera é a seguinte :
S
S
B
B
A
A
→
→
→
→
→
→
A12
A1B2
1B2
12
0A
0
(b) A linguagem não é regular. Vamos usar o Pumping Lemma para linguagens
regulares, sob a forma do jogo, para mostrar isto:
• Jogador 1 : Fornece um número n > 0 qualquer;
• Jogador 2 : Responde, fornecendo a palavra 01n 0n . É claro que esta
palavra está na linguagem.
• Jogador 1 : Quebra a palavra 01n 0n em 3 partes : xyz, onde y não é a
palavra vazia e | xy |≤ n;
• Jogador 2 : Analisa as possibilidades da jogada anterior :
i. x = ² : Neste caso, o primeiro simbolo 0 está contido na parte replicante
y. O jogador 2 responde com i = 0. A palavra obtida é : y 0 z que com
certeza começa com 1. Logo, não pode estar em L, pois toda palavra
de L começa com zero.
ii. x 6= ² : Neste caso, o primeiro simbolo 0 está contido na parte x, isto
é, não está na parte replicante. Como o tamanho de xy é ≤ n então
com certeza, a parte replicante só contém 1. O jogador 2 responde
com i = 2. É claro que xy 2 z contém mais 1’s do que 2’s. Portanto, a
palavra xy 2 z não está em L.
Acabamos de mostrar assim que o jogador 2 tem uma estratégia para
ganhar o jogo, portanto, a linguagem L não é regular.
2. L = {0m 1m 2m | m ≥ 1}
Solução
(a) A linguagem não é livre do contexto e não é regular. É claro que basta mostrar
que a linguagem não é livre do contexto, automaticamente ela não poderá ser
regular. Vamos utilizar o Pumping Lemma para linguagens livres do contexto,
sob a forma do jogo, para mostrar isto:
• Jogador 1 : Fornece um número n > 0 qualquer;
• Jogador 2 : Responde, fornecendo a palavra 0n 1n 2n . É claro que esta
palavra está na linguagem.
• Jogador 1 : Quebra a palavra 0n 1n 2n em 5 partes : uvwxy, onde v e x
não são iguais à palavra vazia simultaneamente e | vwx |≤ n;
• Jogador 2 : Analisa as possibilidades da jogada anterior :
i. vwx está contida no primeiro bloco de 0’s. Neste caso, quando v e
x são replicados, por exemplo, escolhendo-se i = 2 e considerando a
palavra uvvwxxy, esta palavra conterá mais zeros do que 1’s e do que
2’s. Portanto, não estará na linguagem.
ii. vwx está na parte que contém 0’s e 1’s. Pelo fato do comprimento ser
≤ n, vwx não conterá 2. Neste caso, quando v e x são replicados, por
exemplo, escolhendo-se i = 2 e considerando a palavra uvvwxxy, esta
palavra conterá mais zeros e uns do que 2’s. Portanto, não estará na
linguagem.
iii. vwx está na parte que contém 1’s e 2’s. Pelo fato do comprimento ser
≤ n, vwx não conterá 0. Neste caso, quando v e x são replicados, por
exemplo, escolhendo-se i = 2 e considerando a palavra uvvwxxy, esta
palavra conterá mais uns e dois do que zeros. Portanto, não estará na
linguagem.
iv. vwx está totalmente contida no bloco final de 2’s. Neste caso, quando
v e x são replicados, por exemplo, escolhendo-se i = 2 e considerando
a palavra uvvwxxy, esta palavra conterá mais 2 do que zeros e uns.
Portanto, não estará na linguagem.
Acabamos de mostrar assim que o jogador 2 tem uma estratégia para
ganhar o jogo, portanto, a linguagem L não é livre do contexto.
3. L = {w1 xw2 yw3 | x, y ∈ {0, 1}, w1 , w2 , w3 são palavras quaisquer com 0’s e 1’s tais
que | w1 | = | w2 | + | w3 |}
Solução
Esta linguagem é regular. De fato, L é o conjunto das palavras sobre o alfabeto
{0,1} que têm comprimento 2n+2 para n ≥ 0. Um autômato que reconhece esta
linguagem é o seguinte:
0
0
0
1
q0
1
q1
q2
1
0
q3
1
O estado q0 é o estado inicial do autômato e q2 é o único estado final.