INF1626 Linguagens Formais e Autômatos ((2013‐2) Informática
PUC-Rio
Exercícios Resolvidos das Aulas 12 e 13 (18-23/09/2013)
O exercício pede para dizer se as 5 linguagens L, propostas, são regulares. Se
forem devem passar pelos dois passos a seguir:
Passo 1: O lema do bombeamento se aplica.
Passo 2: Existe um Autômato Finito que aceita todas e somente as cadeias de L.
I.
L= (ab)2n para n>0
1. Existe p inteiro tal que para toda cadeia w  L e |w| ≥ p
2. w = xyz, |xy|≤p, |y|>0
3. xy*z  L
O valor de p é associado à quantidade de estados do autômato finito AF que
supostamente aceita todas e somente as cadeias de L.
Na cadeia mínima (ab)2n para n>0 n=1; cadeia mínima min=(ab)2; |min|=4.
Número mínimo de estados necessários para aceitar min = |min|+1 = 5
Se estipulamos p = 5 então o bombeamento da cadeia mínima tem de pertencer a
L (y = min; y* = min*). Ora,   L. Logo, p tem de ser maior do que 5.
Qual a menor cadeia w  L tal que |w| ≥ 6?
 |(ab)2n| ≥ 6
 |(abab)n| ≥ 6
 n=1 < 6
-- w=abab
 n=2 > 6
-- w=abababab
Teste das condições do Lema para w = abababab:
p=6
|w| ≥ 6
x = abab
|x| = 4
y = abab
|y| = 4
|xy| ≤ p
-- FALSO
x=
|x| = 0
y = abab
|y| = 4
|xy| ≤ p
-- VERDADEIRO
z = abab
-- cadeia mínima de L
xy*z  L
.(abab)*abab  L
Passo 1: O LEMA DO BOMBEAMENTO SE APLICA EM L
Passo 2: AF que aceita todas e somente as cadeias de L (com 6 estados, pelas razões
expostas no passo anterior)
1
Informática
PUC-Rio
INF1626 Linguagens Formais e Autômatos ((2013‐2) Passo 2: O AUTÔMATO FINITO AF ACIMA ACEITA TODAS E SOMENTE AS
CADEIAS QUE PERTENCEM A L
L = an.bk para n ímpar OU k par
II.
Tabela Verdade para n ímpar OU k par
Caso a) N Ímpar (aa)*a b) c) Par (aa)+ Par K Ímpar (bb)*b Par (bb)+ Par (bb)+ Ímpar Condição V V F Cadeia mínima para dar conta do caso (a) é
min=(aa)*a(bb)*b, |min|=2; neste caso p=|min|+1 = 3
Cadeia mínima do caso (b) é min=(aa)+(bb)+, |min|=4, p=|min|+1 = 5
O maior p é “5”. Tomemos este valor. (p = 5  |w| ≥ 5)
Caso (a) |w| ≥ 5 Condições N,K N ímpar K par ou ímpar (b) |w| ≥ 5 N par K par Padrões a testar w = ab a) w = ab+ ‐ (w=abbbb) b) w = (aa)*ab ‐ (w= aaaaab) c) w = (aa)*ab+ ‐ (w=aaabb) Bombeamento |w|≥ 5; |xy|≤p;|y|>0 ; xy*z  L ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ a) x=a; y=b; z=bbb(b)* xy*z  L OK b) x=a; y=aa; z=aa(aa)*b. xy*z  L OK c) x=; y=aa; z=(aa)*abb(b)* xy*z  L OK |w|≥ 5; |xy|≤p;|y|>0 ; xy*z  L a) w = (aa)*aabb(bb)* ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ ‐ (w=aaaabb) a) x=aa; y=aa; z=(aa)*bb(bb)* b) w = (aa)*aabb(bb)* b) x=aa; y=bb; z=bb(bb)* ‐ (w=aabbbb) xy*z  L OK Passo 1: O LEMA DO BOMBEAMENTO SE APLICA EM L
A construção do AF que aceita as cadeias de L será mostrada incrementalmente,
salientando o fato de que os casos (a) e (b) são disjuntos, o que inicialmente leva à
construção de dois circuitos separados de aceitação, um para cada caso, o que torna o AF
naturalmente não determinístico.
2
INF1626 Linguagens Formais e Autômatos ((2013‐2) Informática
PUC-Rio
Figura 1: Circuitos separados para N (circuito único para K)
Figura 2: Melhor autômato para o Caso (a)
Figura 3: AFND que aceita todas as cadeias de L
Passo 2: O AUTÔMATO FINITO NÃO DETERMINÍSTICO DA FIGURA 3
ACEITA TODAS E SOMENTE AS CADEIAS QUE PERTENCEM A L
Na aula 13 é apresentado um método que transforma sistematicamente AFND em AFD.
O resultado da transformação de AFND em autômato determinístico AFD é apresentado
na Figura 4.
3
INF1626 Linguagens Formais e Autômatos ((2013‐2) Informática
PUC-Rio
Figura 4: AFD que aceita todas as cadeias de L
Podemos fazer uma observação sobre o valor de p=5 na demonstração do Lema do
Bombeamento e do AFD da Figura 4 ter 6 estados (sugerindo que p deveria ter sido “6”
ao invés de “5”). Notem que quando precisamos demonstrar o caso (b), a menor cadeia
possível (para números pares de a’s e b’s) tinha tamanho “6” (que era maior que 5; se
fosse igual a 5, a condição de teste não se verificaria). Portanto, a equiparação de “p” ao
número de estados necessários para aceitar as cadeias de L é uma diretriz segura para
escolher o “inteiro p” na demonstração do Lema do Bombeamento.
Os demais exercícios da aula 12 podem ser resolvidos seguindo o raciocínio ilustrado
nas questões acima. São eles:
3) L = an para n>0 e n par
4) L = w.wrev
5) L = an.bn
4