Lista 1 Aut Matos

Pessoal, quem tiver alguma dúvida ou achar que algo que alguém escreveu está errado, por favor marque as linhas e marque como um comentário e então as pessoas vão receber um e­mail sabendo, assim todo mundo aprende um com o outro! Outra coisa: quando alguém resolver uma questão coloca o seu nome para sabermos melhor quem fez o que..

Lista 1 1. (questões do livro) 1.8.1
Qual a linguagem é representada pela expressão regular (((a*a)b)Ub) ?
L(((a*a)b) U b)
L((a*a)b) U L(b)
L(a*a)L(b) U L(b)
L(a*)L(a)L(b) U L(b)
L(a)*L(a)L(b) U L(b)
{a}*{a}{b} U {b}
{
ε, a, aa, aaa...}{a}{b} U {b}
{ab, aab, aaab...} U {b}

L1 = {w E {a,b}* | toda palavra em w é b ou possui um numero de a’s precedendo b}
[Jessica]

1.8.1. [Airton e Victor Farias]

L={w E {a,b}* | w começa com 0 ou mais a’s seguido por um b}
Queremos provar que L(
(((a*a)b)Ub)=L

Definição indutiva de L(
(((a*a)b)Ub)=
L(
((a*(ab))Ub):
m*U{b}, onde m0={ab} mi={a}mi­1 m*=Umi

IDA: L(
(((a*a)b)Ub) ⊆ L
Por indução provaremos que m*U{b}
⊆ L, em cima do número de a’s que antecede b.
Base: Para i=0 m0U{b}={ab,b} Como ab e contém um a e é seguido por um b, então ab E L
Como b contém 0 a seguido por um b, então b E L
OK

H.I: i=n
Assumimos que mnU{b}
⊆ L. P.I: i = n+1
Queremos prova que Mn+1U{b}
⊆ L
Como Mn+1={a}Mn
Seja w E {a}MnU{b}
Assim temos duas possbilidades:
­w E {a}Mn: logo w = aw’, por H.I. sabemos que w’ é uma palavra que começa com 0 ou mais as seguidos seguido por um b, assim adicionando um a no começo da palavra, w terá 1 ou mais as seguidos de um b. Logo w E L OK ­w E {b}:
Logo w=b, como b tem 0 as seguido por um b, logo w E L .Ok

Definição indutiva de L:
L0={b}
Li={a}Li­1
L=Uli

VOLTA:
L

⊆
L(
((a*a)b)Ub) =
L(
(a*a)b) U L(b) =
L(
(a*a)b) U {b}
Por indução, queremos prova que
L

⊆
L
((a*a)b) U {b}, em cima do número de a’s que antecede b.
Base:i=0
L0={b},como L0 ⊂
{b}, temos que L0 ⊂