Linguagens Formais
Apêndice 1
José Lucas Rangel
Julho 01
Dois teoremas interessantes de fechamento de linguagens
Teorema 1: A classe das linguagens livres de contexto é fechada para interseção com
conjunto regular. Ou seja, se L é uma l.l.c., e R é uma linguagem regular, L∩R é l.c..
Dem. Vamos construir um autômato de pilha não determinístico (apnd) que reconhece
M=L∩R, a partir de um apnd que reconhece L e de um autômato finito determinístico
(afd) que reconhece R.
Sejam
A = < KA, Σ, Γ, δA ,iA, I, FA >
um apnd que reconhece L por estado final, e
B = < KB, Σ, δB ,iB, FB >
um afd que reconhece R. Seja
C = < KC, Σ, Γ, δC , iC, I, FC >
um apnd, sendo
KC = KA×KB
iC = ( iA, iB )
FC = FA×FB
e a função δC definida por
(caso a≠ε)
δC( (qA, qB), a, Z )={ ( (pA, pB), γ ) | (pA, γ)∈δA(qA, a, Z), pB=δB(qB, a) },
para todo qA∈KA, qB∈KB, a∈Σ, Z∈Γ.
(caso a=ε)
δC( (qA, qB), ε, Z )={ ( (pA, qB), γ ) | (pA, γ)∈δA(qA, ε, Z) },
para todo qA∈KA, qB∈KB, Z∈Γ.
A linguagem reconhecida por C é a interseção das linguagens reconhecidas por A e por
B, ou seja, M=L∩R. Para ver isto, basta observar que, se tivermos
( (iA, iB), x, I ) C ( (fA, fB), ε, α ), com fA∈FA e fB∈FB,
teremos também
( iA, x, I ) A ( fA, ε, α ), com fA∈FA
e
( iB, x ) B ( fB, ε ), com fB∈FB,
ou seja,
x∈L(C) implica x∈L(A) e x∈L(B).
As derivações em A e B podem ser construídas diretamente a partir da derivação em C.
No caso da derivação em B, alguns estados aparecerão repetidos, nos passos
correspondentes às transições em A com entrada ε.
Semelhantemente,
x∈L(A) e x∈L(B) implicam x∈L(C),
sendo necessário acrescentar passos sem que B não muda de estado, correspondendo à
transição com ε em A.
Exemplo:
Seja L = { xcy | |x|=|y|, x,y∈{a,b}* }; seja R = L(a*cb*). Neste caso, M = L∩R =
{ ancbn |n≥0}. Podemos ter
A = < { e, d, f }, { a, b, c }, { X, I }, δA, e, I, { f } >
com
δA(e, a, I) = { (e, XI) }
δA(e, b, I) = { (e, XI) }
δA(e, c, I) = { ( d, I ) }
δA(e, a, X) = { (e, XX) }
δA(e, b, X) = { (e, XX) }
δA(e, c, X) = { ( d, X ) }
δA(d, a, X) = { ( d, ε ) }
δA(d, b, X) = { ( d, ε ) }
δA(d, ε, I) = { ( f, I ) }
(e vazio nos demais casos)
e
B = < { r, s, t }, { a, b, c }, δB, r, { s } >
com
δB( r, a ) = r, δB( r, b ) = t, δB( r, c ) = s
δB( s, a) = t, δB( s, b ) = s, δB( s, c ) = t
δB( t, a) = t, δB( t, b ) = t, δB( t, c ) = t
Neste caso, C é
C = < { er, es, et, dr, ds, dt, fr, fs, ft }, { a, b, c }, { X, I }, δC, er, I, { fs } >
com δC dado por
δC(er, a, I) = { (er, XI) }
δC(er, b, I) = { (et, XI) }
δC(er, c, I) = { ( ds, I ) }
δC(er, a, X) = { (er, XX) }
δC(er, b, X) = { (et, XX) }
δC(er, c, X) = { ( ds, X ) }
δC(es, a, I) = { (et, XI) }
δC(es, b, I) = { (es, XI) }
δC(es, c, I) = { ( dt, I ) }
δC(es, a, X) = { (et, XX) }
δC(es, b, X) = { (es, XX) } δC(es, c, X) = { ( dt, X ) }
δC(et, a, I) = { (et, XI) }
δC(et, b, I) = { (et, XI) }
δC(et, c, I) = { ( dt, I ) }
δC(et, a, X) = { (et, XX) }
δC(et, b, X) = { (et, XX) }
δC(et, c, X) = { ( dt, X ) }
δC(dr, a, X) = { ( dr, ε ) }
δC(dr, b, X) = { ( dt, ε ) }
δC(dr, ε, I) = { ( fr, I ) }
δC(ds, a, X) = { ( dt, ε ) }
δC(ds, b, X) = { ( ds, ε ) }
δC(ds, ε, I) = { ( fs, I ) }
(dt,
a,
X)
=
{
(
dt,
)
}
δC
ε
δC(dt, b, X) = { ( dt, ε ) }
δC(dt, ε, I) = { ( ft, I ) }
(e vazio nos demais casos)
Note que os nomes dos estados de C foram abreviados: er em vez de (e, r), etc. Alguns
estados de C são inúteis, e poderiam ser retirados.
Como exemplo, as computações nas três máquinas, para aceitar aaacbbb:
(e, aaacbbb, I)
(e, aacbbb, XI)
(e, acbbb, XXI)
(e, cbbb, XXXI)
(d, bbb, XXXI)
(d, bb, XXI)
(d, b, XI)
(d, ε, I)
(f, ε, I)
(r, aaacbbb)
(r, aacbbb)
(r, acbbb)
(r, cbbb)
(s, bbb)
(s, bb)
(s, b)
(s, ε)
(er, aaacbbb, I)
(er, aacbbb, XI)
(er, acbbb, XXI)
(er, cbbb, XXXI)
(ds, bbb, XXXI)
(ds, bb, XXI)
(ds, b, XI)
(ds, ε, I)
(fs, ε, I)
Teorema 2: A classe das linguagens determinísticas é fechada para interseção com
conjunto regular. Ou seja, se L é determinística, e R é uma linguagem regular, L∩R
também é determinística.
Dem. Basta notar que se a construção acima for aplicada a um apd A ( e um afd B) leva a
um apd C.