resoluo_letra_d

Prévia do material em texto

Teorema 1. Sejam L = {w | w não contém a cadeia 101 como subcadeia} uma linguagem
sobre Σ = {0, 1} e R = (0 ∪ ε)(1 ∪ 00+)∗(0 ∪ ε). Temos então que L(R) = L.
Demonstração. Prova da ida (x ∈ L(R) =⇒ x ∈ L): Seja x ∈ L(R). Logo, temos que
x = w1w2w3, onde w1, w3 ∈ L(0∪ ε) e w2 ∈ L((1∪ 00+)∗). Temos ainda que w2 = y1y2 . . . yk,
onde cada yi = 1 ou yi ∈ L(00+). Se houvesse uma cadeia 101 em x, ela certamente estaria
em w2, pois w1, w3 ou são a cadeia vazia ou são o símbolo 0. Adicionalmente, se houvesse a
cadeia 101 em w2, então existiria um i tal que yi = 1 yi+2 = 1, o que implica que yi+1 = 0.
No entanto, yi+1 não pode ser 0, pois ou ele é 1 ou ele é uma sequência de dois ou mais
símbolos 0. Com isso, podemos então concluir que 101 não é subcadeia de x, ou seja, x ∈ L.
Prova da volta (x ∈ L =⇒ x ∈ L(R)): Vamos provar essa implicação por indução em |x|.
Caso base (|x| = 0): para |x| = 0, temos que x = ε. De fato, temos que x ∈ L. Temos então
que mostrar que x ∈ L(R), o que de fato é verdade, pois ε ∈ L(0 ∪ ε) e ε ∈ L((1 ∪ 00+)∗), o
que implica que
x = ε = ε ◦ ε ◦ ε ∈ L((0 ∪ ε) ◦ (1 ∪ 00+)∗ ◦ (0 ∪ ε)) = L(R)
Passo indutivo: Seja k ≥ 1 um natural arbitrário. Suponha que a implicação x ∈ L =⇒
x ∈ L(R) é válida para toda cadeia x de tamanho menor do que k. Vamos provar que ela
também é válida para toda cadeia x de tamanho igual a k. Seja então x uma cadeia de
tamanho k. Se x /∈ L, temos que a implicação é verdadeira porque a sua premissa é falsa.
Suponha então que x ∈ L. Temos então que x não contém 101 como subcadeia. Seja x = wa,
onde a ∈ Σ e seja y o maior prefixo de w que termina com o símbolo 1, ou seja, w = y0n
para algum n ≥ 0 e y termina com o símbolo 1. Note que, se o último símbolo de w for 1,
temos que y = w e n = 0.
Como |y| ≤ |w| < |x|, então |y| < |x| = k. Adicionalmente, como não há ocorrências de 101
em x, também não há ocorrências de 101 em y. Logo, |y| < k e y ∈ L. Assim, pela hipótese
indutiva, y ∈ L(R). Com isso, visto que y termina com o símbolo 1, na verdade podemos
afirmar que y ∈ L((0 ∪ ε)(1 ∪ 00+)∗).
A partir daqui, temos dois casos dependendo do símbolo a. Se a = 0, temos que x =
y0n0 = y0n+1 e, se a = 1, temos que x = y0n1. Primeiro, suponha que x = y0n+1 para
algum n ≥ 0. Se n = 0, temos que x = y0 e, como 0 ∈ L(0 ∪ ε), então x = y0 ∈
L((0 ∪ ε)(1 ∪ 00+)∗ ◦ (0 ∪ ε)) = L(R). Se n ≥ 1, então x termina com dois ou mais símbolos
0, ou seja, 0n+1 ∈ L(00+). Logo, y ∈ L((0 ∪ ε)(1 ∪ 00+)∗) e 0n+1 ∈ L((1 ∪ 00+)∗), o que
implica que x = y0n+1 ∈ L((0 ∪ ε)(1 ∪ 00+)∗ ◦ (1 ∪ 00+)∗) = L((0 ∪ ε)(1 ∪ 00+)∗) ⊆ L(R).
Agora, suponha que x = y0n1. Nesse caso, temos que n ̸= 1, pois, se n = 1, x teria
101 como subcadeia visto que y termina com o símbolo 1. Assim, como n ̸= 1, temos que
0n1 ∈ L((1∪00+)∗). Isso implica que x = y0n1 ∈ L((0∪ε)◦(1∪00+)∗)◦L((1∪00+)∗) ⊆ L(R).
0-1