Autmatos finitos e expresses regulares

  • Published on
    19-Jun-2015

  • View
    1.668

  • Download
    2

DESCRIPTION

Material de estudo de linguagens formais e automatos deterministicos

Transcript

Linguagens Formais Captulo 4: Autmatos finitos e expresses regulares com Luiz Carlos Castro Guedes 4.1 - Introduo Neste captulo estudaremos uma mquina (um procedimento aceitador, ou reconhecedor), chamada autmato finito (af). A palavra finito includa no nome para ressaltar que um af s pode conter uma quantidade finita e limitada de informao, a qualquer momento. Essa informao representada por um estado da mquina, e s existe um nmero finito de estados. Essa restrio faz com que o af seja severamente limitado na classe de linguagens que pode reconhecer, composta apenas pelas linguagens regulares, como mostraremos neste captulo. Duas verses do af so estudadas aqui: o af determinstico (afd) e o af no determinstico (afnd). Este captulo mostra que uma linguagem regular pode ser definida de quatro formas:

atravs de uma gramtica regular (definio); atravs de um afd que reconhece a linguagem; idem, atravs de um afnd; atravs de uma expresso regular, um mecanismo a ser introduzido com essa expressa finalidade.

4.2 - Autmato finito determinstico Como observado acima, a informao que um af guarda sobre a entrada (mais precisamente sobre a parte da entrada j lida) representada por um estado, escolhido em um conjunto finito de estados. A definio formal de automato finito, na sua verso determinstica dada a seguir. Definio. Um Autmato Finito Determinstico (afd) M, sobre um alfabeto um sistema (K, , , i, F), onde K um conjunto de estados finito, no vazio; um alfabeto de entrada (finito) : K K a funo de transio iK o estado inicial FK o conjunto de estados finais. O nome determinstico faz referncia ao fato de que uma funo (tambm chamada funo prximo-estado), que determina precisamente o prximo estado a ser assumido quando a mquina M se encontra no estado q e l da entrada o smbolo a: o estado (q, a).

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-1

De forma simplificada, podemos dizer que um afd aceita uma cadeia se, partindo do estado inicial, e mudando de estado de acordo com a funo de transio, o afd atinge um estado final ao terminar de ler a cadeia. Uma das maneiras de visualizar o funcionamento de um afd atravs de um controle finito que l smbolos de uma fita de entrada (onde se encontra a cadeia de entrada), sequencialmente, da esquerda para a direita. Os elementos do conjunto de estados K representam os estados possveis do controle finito. A operao se inicia no estado inicial i, lendo o primeiro smbolo da fita de entrada. Por convenincia, considera-se que a cabea de leitura se move sobre a fita, ao contrrio do que seria de se esperar. A Figura 4.1 representa um afd cujo controle est no estado q, e que est lendo o quarto smbolo da cadeia de entrada, um b.

Fig. 4.1 - Autmato Finito Exemplo 1: Considere o afd M = (K, , , i, F), onde temos K = { q0, q1, q2, q3 } = { a, b } i = q0 F = { q3 } e onde a funo de transio : { q0, q1, q2, q3 } { a, b } { q0, q1, q2, q3 } dada pela tabela abaixo q0 q1 q2 q3 a q1 q0 q3 q2 b q2 q3 q0 q1

Alternativamente, podemos representar o afd M por um diagrama de transies, ou diagrama de estados, como o da Fig. 4.2. Note que o diagrama de transies determina completamente o automato M, atravs de algumas convenes: os estados so os ns do grafo, ou seja, K = { q0, q1, q2, q3 }; o estado inicial indicado pela seta, ou seja, i = q0; os estado finais so indicados pelo crculo duplo: q3 o nico estado final, ou

seja, F = { q3 };J. L. Rangel, L. C. Guedes - Ling. Formais - 4-2

as transies so as indicadas pelas arestas: (q0, a) = q1, (q0, b) = q2,

(q1, a) = q0, etc, ou seja, a mesma funo representada pela tabela acima.

Cada estado de um af corresponde a uma determinada informao sobre a parte da cadeia de entrada j lida. No caso do exemplo, a informao pode ser descrita em frases curtas, mas isso nem sempre acontece. Para o estado q2, por exemplo, podemos dizer "se o estado atingido q2, o nmero de smbolos a j lidos par, e o nmero de smbolos b j lidos mpar". (Note que 0 par.)

Fig. 4.2 - afd para o Exemplo 1 Em resumo, temos: q0 q1 q2 q3 nmero de a's par mpar par mpar nmero de b's par par mpar mpar

A linguagem aceita ou reconhecida por M (ver definio abaixo) a linguagem formada pelas cadeias em que os nmeros de a's e de b's so ambos mpares. Isso se deve ao fato de que o nico estado final q3. Por exemplo, a cadeia abaa da linguagem de M, porque, com essa cadeia, os seguintes estados so atingidos: q0, q1, q3, q2, q3. Como o ltimo estado final, a cadeia aceita. A linguagem de um afd. Para definir a linguagem L(M), a linguagem das cadeias aceitas ou reconhecidas pelo afd M, podemos definir inicialmente uma configurao de M como sendo um par (q, x) K *, composto pelo estado corrente (o estado atual da mquina) e pela cadeia x, a parte da entrada que ainda no foi lida. Como observado, oJ. L. Rangel, L. C. Guedes - Ling. Formais - 4-3

estado representa a parte j lida da cadeia de entrada. A configurao (i, x) a configurao inicial de M para a cadeia x; qualquer configurao (q, ) uma configurao final se q F. A mudana de configurao caracterizada pela relao |, definida abaixo: (q, ax) | (p, x) se e somente se (q, a) = p ou seja, se tivermos (q, a) = p, e se M estiver no estado q, lendo um smbolo a da cadeia de entrada, M mover a cabea de leitura uma posio para a direita e ir para o estado p. O smbolo a, depois de lido, no precisa mais aparecer na configurao. Podemos agora definir a linguagem L(M) por L(M) = { x * | (i, x) |* (f, ), com f F } Como em casos anteriores, |* indica o fechamento reflexivo-transitivo da relao, no caso a relao | de mudana de configurao, indicando que a configurao final pode ser atingida em zero ou mais passos. Exemplo 1: (continuao) Para mostrar que abaa L(M), basta observar que (q0, abaa) | (q1, baa) | (q3, aa) | (q2, a) | (q3, ), porque q3 final. Por outro lado, como (q0, abab) | (q1,bab) | (q3, ab) | (q2, b) | (q0, ), abab no pertence a L(M). $ Uma caracterizao alternativa de L(M) pode ser baseada em uma extenso da funo , feita de forma a aceitar cadeias no segundo argumento, isto com domnio $ K * em vez de K . Pode-se definir a nova funo : K * K por $ (q, ) = q, q K $ $ (q,ax) = ( (q,a), x), q K, x *, a . $ $ Fato: A funo realmente uma extenso de , isto , sempre que definida, $ tambm , e tem o mesmo valor. Ou seja, se q K e a , (q, a) = (q, a). Dem. Exerccio. $ Fato: A funo e a relao | se relacionam por $ (q, x) = p se e somente se (q, x) |* (p, ) Portanto, temos $ L(M) = {x * | (q, x) F } Demonstrao: Exerccio.

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-4

Exemplo 1: (continuao) Para mostrar que abaa L(M), basta ver que $ $ $ $ $ (q0, abaa) = (q1, baa) = (q3, aa) = (q2, a) = (q3, ) = q3 F $ Como (q0, abab) = q0 F, abab L(M). Exerccio 1: Mostre que o afd M do Exemplo 1 aceita a linguagem L(M) = { x {a, b}* | os nmeros de a's e de b's em x so mpares } Sugesto: induo no comprimento de x. $ Exerccio 2: Mostre que a definio anterior de pode ser substituda pela equivalente $ (q, ) = q, q K $ $ (q, xa) = ( (q, x),a), q K, x *, a . Exerccio 3: Modifique a definio do af M do Exemplo 1, fazendo F= { q1, q2 } Descreva a linguagem aceita por M assim modificado. Exerccio 4: Descreva a linguagem do afd M dado pelo diagrama de estados da Fig. 4.3.

Fig. 4.3 - afd para o Exerccio 4 Exerccio 5: Descreva a linguagem do afd M = (K, , , i, F), onde K={q0, q1, q2, q3}, = { a, b }, i = q0, F = { q2 }, e dada pela tabela abaixo: q0 q1 q2 q3 a q1 q2 q3 q4 b q3 q0 q1 q2J. L. Rangel, L. C. Guedes - Ling. Formais - 4-5

4.3 - Autmato finito no determinstico Passaremos agora ao estudo do af no determinstico. Em oposio ao que acontece com o afd, a funo de transio de um afnd no precisa determinar exatamente qual deve ser o prximo estado. Em vez disso, a funo de transio fornece uma lista (um conjunto) de estados para os quais a transio poderia ser feita. Essa lista pode ser vazia, ou ter um nmero qualquer positivo de elementos. Essa possibilidade de escolha entre vrios caminhos a serem seguidos nos leva a modificar a definio de aceitao. Um afd aceita se "o ltimo estado atingido final"; mas um afnd aceita se "existe uma sequncia de escolhas tal que o ltimo estado atingido final". Podemos alternativamente imaginar que o afnd "escolhe", "adivinha", o caminho certo para a aceitao, uma vez que a existncia de escolhas erradas, que no levam a um estado final, irrelevante. Exemplo 2: Considere o afnd dado pelo diagrama da Fig. 4.4 e a cadeia de entrada ababa.

Fig. 4.4 - afnd para o Exemplo 2 A cadeia ababa aceita, porque uma das possibilidades a sequncia de estados q0, q1, q1, q1, q1, q2. Naturalmente, com a mesma cadeia, poderamos escolher a sequncia q0, q1, q1, q1, q1, q1, que no leva a um estado final. Ou a sequncia q0, q1, q1, q2, interrompida, porque q2 no prev uma transio com o segundo b. Mas estes casos em que "o automato adivinhou errado" no criam problemas para a aceitao, porque "existe um caminho certo". Este afnd aceita a linguagem das cadeias (de comprimento maior ou igual a 2), cujo primeiro e ltimo smbolos so a, sendo os restantes quaisquer. (Compare este afnd com o afd de um dos exemplos anteriores, que aceita a mesma linguagem.) Definio. Formalmente, um Autmato Finito no Determinstico (afnd) M, sobre um alfabeto um sistema (K, , , i, F), onde K um conjunto (finito, no vazio) de estados, um alfabeto de entrada (finito), : K( { }) P(K) a funo de transio, iK o estado inicial, FK o conjunto de estados finais.

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-6

A notao P(K) indica o conjunto "partes" de K (conjunto potncia de K, ou, ainda, "powerset" de K), o conjunto de todos os subconjuntos de K. Pela definio, portanto, uma funo que aceita como argumentos q e a, onde q um estado e a pode ser um smbolo de ou a cadeia vazia . Em qualquer caso, (q, a) sempre um conjunto de estados, ou seja, um subconjunto de K. Se tivermos (q, a) = {p1, p2, ..., pk}, entendemos que o autmato M, a partir do estado q, pode escolher um dos estados p1, p2, ..., pk para ser o prximo estado. Se a = , nenhum smbolo da entrada lido; se a , o smbolo a da entrada lido. Podemos considerar o caso a= como correspondendo a transies espontneas: M muda de estado sem estmulo da entrada. Se tivermos (q, a) = , no h transies possveis a partir do estado q com o smbolo a. Definimos configuraes para o caso do afnd da mesma forma que anteriormente. A mudana de configurao dada pela relao |, definida abaixo: (q, ax) | (p, x) se e somente se p (q, a) Note que a pode ser a cadeia vazia, caso em que temos, particularizando, (q, x) | (p, x) se e somente se p (q, ) Podemos agora definir a linguagem L(M) por L(M) = { x * | (i, x) |* (f, ), com f F } Exemplo 2: (continuao) Temos, para a mesma cadeia ababa de entrada, (q0, ababa) | (q1, baba) | (q1, aba) | (q1, ba) | (q1, a) | (q2, ) e, portanto, ababa L(M). Temos tambm o "caminho errado" (q0, ababa) | (q1, baba) | (q1, aba) | (q1, ba) | (q1, a) | (q1, ) que leva configurao no final (q1, ), e no permite nenhuma concluso. Cadeias como bab e abab no levam a configuraes finais e no so aceitas. Da configurao (q0, bab) nenhuma configurao atingvel; para abab temos: (q0, abab) | (q1, bab) | (q1, ab) | (q1, b) | (q1, ) Adicionalmente, temos um outro caminho (q0, abab) | (q1, bab) | (q1, ab) | (q2, b) que tambm no atinge nenhuma configurao final. Assim, as cadeias bab e abab no so aceitas e no fazem parte de L(M). Exemplo 3: Considere o afnd M da Fig. 4.5. M aceita cadeias da forma c y c, onde c pode ser a ou b e y pode ser qualquer cadeia de a's e b's. A cadeia ababa = cyc = ababa aceita por M, atravs da sequncia de configuraes abaixo, em que a primeira e a ltima transies so realizadas atravs de transies-.J. L. Rangel, L. C. Guedes - Ling. Formais - 4-7

(A, ababa) | (B, ababa) | (C, baba) | (C, aba) | (C, ba) | (C, a) | (D, ) | (I, )

M l e adivinha que c=a M l a e confere que c=a M l b M l a e adivinha que este a faz parte de y M l b M l a e adivinha que este a o ltimo c M l e adivinha que a cadeia acabou M aceita

Fig. 4.5 - afnd para o Exemplo 3 Todas as configuraes atingveis (caminhos certos e errados) esto indicadas abaixo: (A, ababa) | (B, ababa) . | (C, baba) . | (C, aba) . | (C, ba) . . | (C, a) . . | (C, ) -- no aceita . . | (D, ) . . | (I, ) -- ok! aceita! . | (D, ba) . | (I, ba) -- bloqueado | (F, ababa) -- bloqueado Exerccio 6: Considere a linguagem composta pelas cadeias no alfabeto {a, b} que contm a cadeia aaa ou a cadeia bb. Ou seja, a linguagem L = { x y z | x, z {a, b}* e ( y=aaa ou y=bb ) } Construa um afnd M que aceite L.

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-8

Sugesto: M adivinha se a cadeia de entrada contm aaa ou bb, e apenas verifica esse fato. 4.4 - Equivalncia dos afd's e dos afnd's Mostraremos nesta seo que uma linguagem aceita por um af determinstico se e somente se ela aceita por um af no determinstico. A classe de linguagens reconhecidas por afd's e afnd's a classe das linguagens regulares (ver seo 4.6).

Teorema: Toda linguagem reconhecida por um afd reconhecida por um afnd. Demonstrao: Exerccio. Sugesto: Basta definir um afnd em que a nica transio possvel em cada caso aquela especificada no afd. Teorema: Toda linguagem reconhecida por um afnd reconhecida por um afd. Demonstrao: ver Lemas 1 e 2 abaixo. Lema 1: Toda linguagem reconhecida por um afnd reconhecida por um afnd que no tem transies com . Demonstrao: Seja M = (K, , , i, F) um afnd qualquer. Vamos construir um afnd M' = (K, , ', i, F') equivalente a M, isto L(M') = L(M). Para isso vamos "simular" o efeito das transies com de duas maneiras: se tivermos a , (p1, ) = p2, e (p2, a) = q, acrescentaremos a ' uma transio de p1 para q com a, ou seja, acrescentaremos q ao conjunto '(p1, a); se tivermos (p1, ) = p2, e p2 F, acrescentaremos p1 a F. (ver figura abaixo)

Isso deve ser feito repetidamente enquanto novas transies forem acrescentadas a ', e enquanto novos estados forem acrescentados a F. Aps isso, retiramos de as transies com , e chamamos os resultados de ' e F'. Exemplo 4: Considere o afnd M do Exemplo 3 (Fig. 4.5). A construo descrita na prova do Lema 1 permite construir o afnd equivalente M' (Fig. 4.6), que no temJ. L. Rangel, L. C. Guedes - Ling. Formais - 4-9

transies com . Note que M' tem estados inteis: B, F e I passaram a ser inacessveis a partir do estado inicial. Para aceitar a cadeia ababa, as configuraes de M esto na tabela a seguir: Configuraes de M (A, ababa) (B, ababa) (C, baba) (C, aba) (C, ba) (C, a) (D, ) (I, ) --- final Configuraes de M' (A, ababa) --(C, baba) (C, aba) (C, ba) (C, a) (D, ) --- final ---

Fig. 4.6 - afnd sem transies-

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-10

Lema 2: Toda linguagem aceita por um afnd sem transies com aceita por um afd. Demonstrao. Seja M = (K, , , i, F) um afnd sem transies com . Vamos construir um afd M' = (K', , ', i', F'), equivalente a M, isto , M' tambm aceita L. A idia da demonstrao que os estados de M' so conjuntos de estados de M: a cada momento o estado de M' contm todos os estados em que M poderia se encontrar. Desta maneira, M' pode seguir ao mesmo tempo todos os caminhos percorridos por M. Temos: K'= P(K); estados de M' so conjuntos de estados de M i' = { i } o estado inicial de M' contm apenas o estado inicial de M F' = { Q K | Q F } os estados finais de M' so os conjuntos de estados de M que contm pelo menos um estado final de M ': K' K' A funo ' deve cobrir todas as possibilidades: '(Q, a) deve incluir todos os estados em todos os conjuntos (q, a), para cada q em Q, ou seja, (Q,a) = U (q,a)q Q

para cada a . A aceitao nas duas mquinas se d de forma paralela: M aceita x, e temos em M (i, x) |* (f, ), com f F M' aceita x, e temos em M' (i', x) |* (Q, ), com Q F A ligao entre as duas sequncias de configuraes feita pelo estado f Q. O restante da demonstrao consiste na prova de que dada uma das sequncias de configuraes, possvel construir a outra, e vice-versa. Observamos que em geral no necessrio levar em considerao todos os estados de M', bastando apenas considerar aqueles que so acessveis a partir de i'. Se M tem n estados, M' tem um mximo terico de 2n estados, mas em geral apenas uma frao desses estados acessvel a partir do estado inicial i'.

Exemplo 4 (continuao): Podemos construir um afd M'' a partir de M', como descrito na demonstrao do Lema 2. M'' ser equivalente a M (Exemplo 3) e a M'. Temos: i'' = { A }. A tabela abaixo mostra a funo ''. Note que os 251 estados no acessveis a partir de { A } foram ignorados. O afd pode ser visto tambm na Fig. 4.7. '' {A} {C} {G} { C, D } { G, H } a {C} { C, D } {G} { C, D } {G} b {G} {C} { G, H } {C} { G, H }

Os estados finais de M'' que precisam ser considerados so, portanto, {C, D} e {G, H}, que contm os estados finais D e H de M'. Para comparao, a tabela abaixo apresenta as configuraes assumidas por M, M' e M'' na aceitao de ababa. J. L. Rangel, L. C. Guedes - Ling. Formais - 4-11

Fig. 4.7 - afd para o Exemplo 4

M (A, ababa) (B, ababa) (C, baba) (C, aba) (C, ba) (C, a) (D, ) (I, )

M' (A, ababa) --(C, baba) (C, aba) (C, ba) (C, a) (D, ) ---

M'' ({A}, ababa) --({C}, baba) ({C}, aba) ({C, D}, ba) ({C}, a) ({C, D}, ) ---

Exerccio 7: Construa um afd equivalente ao afnd do Exerccio 6.

4.5 - Minimizao de autmatos finitos Para af determinsticos, possvel fazer uma minimizao: dado um afd M, possvel construir um afd M', que equivalente a M, e que tem o menor nmero de estados possvel para todos os afd's que aceitam L(M). (Esta construo no se aplica a af no determinsticos.) Uma propriedade adicional, que no demonstraremos aqui, que o afd mnimo nico, exceto pelos nomes dos estados, que podem ser escolhidos arbitrariamente. Ou seja, o mesmo afd mnimo obtido, a partir de qualquer afd que aceite a linguagem considerada.

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-12

A maneira de construir o afd mnimo baseada na idia de estados equivalentes, que podem ser reunidos em um s. Dois estados p e q so equivalentes quando as mesmas cadeias levam dos dois estados at a aceitao (at um estado final). Temos: p q se e somente se para toda cadeia x *, $ $ (p, x) F se e somente se (q, x) F A ltima linha pode ser substituda por $ $ ou (p, x) e (q, x) so ambos finais, ou so ambos no finais. A relao uma relao de equivalncia. Portanto, trivialmente, para estados p, q e r quaisquer, temos pp se p q, ento q p se p q e q r, ento p r

(reflexividade) (simetria) (transitividade)

(Demonstrao: exerccio.) O algoritmo que vamos descrever aqui se baseia no fato de que mais fcil provar que dois estados p e q no so equivalentes do que provar que so. Para mostrar $ que p e q no so equivalentes, basta achar uma cadeia x tal que (p, x) final e $ (q, x) no final, ou vice-versa. Dizemos que essa cadeia x distingue o estado p do estado q, e que p e q so distinguveis. As propriedades que vamos usar no algoritmo so: Propriedade 1. (Equivalncia se propaga para a frente.) Se p q, ento para qualquer a , os estados p' = (p, a) e q' = (q, a) so equivalentes. $ Dem. Seja x * uma cadeia qualquer. Devemos mostrar que p'' = (p', x) e $ q'' = (q', x) so ambos finais ou ambos no finais. Seja y = ax. Temos $ $ $ $ p'' = (p', x) = ((p, a), x) = (p, ax) = (p, y) e $ $ $ $ q'' = (q', x) = ((q, a), x) = (q, ax) = (q, y) Como p q, p'' e q'' so ambos finais ou ambos no finais. Propriedade 2. (Distinguibilidade se propaga para trs.) Para qualquer a , se p' = (p, a) e q' = (q, a) no so equivalentes, ento p e q tambm no so equivalentes. Dem. Se p'e q' no so equivalentes, existe uma cadeia x que distingue p' e q'. Ou seja, $ $ chamando p'' = (p', x) e q'' = (q', x), temos que um deles final e o outro no. Fazendo y = ax, temos $ $ $ $ p'' = (p', x) = ((p, a), x) = (p, ax) = (p, y) e $ $ $ $ q'' = (q', x) = ((q, a), x) = (q, ax) = (q, y)J. L. Rangel, L. C. Guedes - Ling. Formais - 4-13

e vemos que y = ax distingue p e q. Propriedade 3. (Iniciao) Um estado final e um estado no final no podem ser equivalentes. $ Demonstrao: Sejam p F, e q F. A cadeia vazia distingue p de q: p = (p, ) F, $ e q = (q, ) F. Para minimizar um afd M, comeamos por determinar quais so os pares de estados de M que so equivalentes, isto , que podem ser reunidos em um nico estado. Como mais fcil descobrir quais so os pares de estados no equivalentes, consideramos que estados p e q so equivalentes se no conseguirmos mostrar que so distinguveis (no equivalentes). As estruturas de dados usadas pelo algoritmo so: para cada par (p, q) de estados distintos, um valor booleano marca(p, q), inicialmente com o valor false.

Se marca(p,q) = true, p e q so distinguveis. uma lista de pares de estados, inicialmente vazia. Se (r, s) est na lista de (p, q), isto significa que r e s sero distinguveis, se p e q forem distinguveis. Se marca(p, q) = true, dizemos que o par (p, q) est marcado. Note que o par identificado como (p, q) o mesmo par identificado como (q, p), e, portanto, tanto faz marcar (p, q), como marcar (q, p). Note que o algoritmo que determina os pares de estados equivalentes baseado nas propriedades vistas acima. As listas so usadas para evitar a necessidade de passar mais de uma vez por cada par de estados. Ao final da execuo do algoritmo, os pares de estados equivalentes so os que no esto marcados. A prova de correo do algoritmo, pode ser encontrada, por exemplo, em [HopUll79]1. Algoritmo. Determinao dos estados equivalentes em um afd M. procedimento mark(p, q); se p q ento marca(p, q) := true; para cada par (r,s) na lista de (p, q) execute mark( r, s);

E. Hopcroft, Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979 - Sec. 3.4, p.68 J. L. Rangel, L. C. Guedes - Ling. Formais - 4-14

1John

{parte principal do algoritmo} para cada p final, para cada q no final, marca(p, q):= true; para cada par (p, q) no marcado, se existe um smbolo a tal que o par ((p,a), (q,a)) est marcado, execute mark(p, q) seno, para cada smbolo a faa p' := (p, a); q' := (q, a); se p' q' e (p, q) (p', q'), acrescente (p, q) lista de (p', q'). O teste da penltima linha no realmente necessrio, e pode ser considerado como uma otimizao. Dado M = (K, , , i, F), usamos como estados as classes de equivalncia de , obtidas para M para a construo do afd mnimo M' = (K', , ', i', F'). Temos: K' = K/ = { [q] | q K } ': K' K', dada por '([q], a) = [(q, a)] i' = [ i ] F' = { [ f ] | f F } Deixamos como exerccio demonstrar a consistncia da definio de ', isto , a demonstrao de que o resultado da aplicao de ' independe da escolha do representante q da classe de equivalncia [q]. Exemplo 5: Seja M um afd com estados A, B, C, D, E e F, sendo A o estado inicial; C e F so os estados finais. Os smbolos de entrada so a e b, e como na tabela abaixo. M aceita as cadeias que tem um nmero de a's da forma 6n+2 ou 6n+5. Na realidade, bastaria exigir que o nmero de a's fosse da forma 3n+2, o que corresponde a um afd com apenas 3 estados, e, por essa razo, M no mnimo, e deve ter estados equivalentes. A tabela de transio de M A B C D E F a B C D E F A b A B C D E F

Os pares de estados (representados em ordem alfabtica sem os parenteses) a serem considerados so AB, AC, AD, AE, AF, BC, BD, BE, BF, CD, CE, CF, DE, DF,J. L. Rangel, L. C. Guedes - Ling. Formais - 4-15

e EF. No h necessidade de incluir pares como AA por causa da reflexividade, nem pares como BA por causa da simetria: basta incluir AB. Vamos aplicar o algoritmo acima para determinar os pares de estados equivalentes. (marcao dos pares final / no final) marcamos AC, AF, BC, BF, CD, CE, DF e EF. (exame de cada par no marcado) AB: Temos (A, a)=B, (B, a)=C, e BC est marcado. Logo, marcamos AB. AD: Temos (A, a)=B, (D, a)=E, e (A, b)=A, (D, b)=D. Como BE no est marcado, inclumos AD na lista de BE. (Note que no h necessidade de incluir AD na lista de AD.) AE: Temos (A, a)=B, (E, a)=F, e BF est marcado. Logo, marcamos AE. BD: Temos (B, a)=C, (D, a)=E e CE est marcado. Logo, marcamos BD. BE: Temos (B, a)=C, (E, a)=F, e (B, b)=B, (E, b)=E. Como CF no est marcado, inclumos BE na lista de CF. CF: Temos (C, a)=D, (F, a)=A, e (C, b)=C, (F, b)=F. Como AD no est marcado, inclumos CF na lista de AD. DE: Temos (D, a)=E, (E, a)=F e EF est marcado. Logo, marcamos DE. (os pares restantes so equivalentes) Os pares marcados aparecem na tabela abaixo: A B C D E F X X X X A

X X X B

X X C

X X D

X E

F

Os pares restantes (no marcados) so AD, BE, CF. Logo, A D, B E e C F. Naturalmente, alm disso, A A, D A, etc. Note que as cadeias que distinguem os pares de estados no equivalentes podem ser deduzidas da ordem de marcao: para os pares final/no final, a cadeia . Para os demais pares, neste exemplo, a cadeia a. Por exemplo, marcamos AB porque BC estava marcado, e porque de A e B passamos com o smbolo a para B e C. A cadeia correspondente a AB portanto a = a. Podemos agora construir o afd mnimo: o conjunto de estados o das classes de equivalncia. Como previsto, tem apenas 3 estados. Temos: K' = { [A], [B], [C], [D], [E], [F] } = { {A, D}, {B, E}, {C, F} } i' = [A] = {A, D} F' = { [C], [F] }= {C, F} Para calcular as transies, escolhemos representantes das classes. Por exemplo, como [A] = [D] = {A, D}, '( {A, D}, a) pode ser calculada como '( [A], a ) = [(A, a)] = [B] = {B, E} ou como '( [D], a ) = [(D, a)] = [E] = {B, E}. Qualquer que seja oJ. L. Rangel, L. C. Guedes - Ling. Formais - 4-16

representante escolhido, o resultado ser o mesmo, porque, como vimos na propriedade 1, "a equivalncia se propaga para a frente". A funo de transio pode ser vista na tabela abaixo: ' {A, D} {B, E} {C, F} a {B, E} {C, F} {A, D} b {A, D} {B, E} {C, F}

Um resultado interessante, cuja demonstrao pode ser encontrada na referncia citada, o de que o afd mnimo que aceita uma dada linguagem nico, exceto por isomorfismo. Neste contexto, isomorfismo quer dizer simplesmente re-nomeao de estados: dados dois afd's M1 e M2 que aceitam a mesma linguagem L, se construirmos os afd's mnimos associados ao dois afd's, encontraremos dois afd's M1' e M2' que so, na prtica, idnticos: M1' e M2' s se distinguem pelos nomes de seus estados. Ou seja, a linguagem L que define o afd mnimo que a aceita, e o resultado sempre o mesmo, independente do afd aceitador de L do qual partimos. Isso pode ser usado para resolver dois problemas interessantes. Primeiro, se quisermos determinar se dois afd's M1 e M2 so equivalentes, basta construir os afd's M1' e M2' mnimos correspondentes. Se M1' e M2' forem isomorfos, M1 e M2 so equivalentes. Segundo, se quisermos mostrar que um afd M dado mnimo, basta aplicar a M o processo de minimizao, e verificar que o resultado M' isomorfo de M. Isto feito no Exemplo 6, onde, adicionalmente, para cada par de estados (p, q) distintos de M, deduzimos exemplos de cadeias que os distinguem. Exemplo 6: Vamos verificar que um afd mnimo, aplicando a ele o processo de minimizao, e mostrando que o resultado final isomorfo do afd inicial. Seja M o afd com estados A, B, C, D, E e F, sendo A o estado inicial; e F o nico estado final. Os smbolos de entrada so a e b. A tabela de transio de M A B C D E F a B C D E F A b A B C D E F

Aplicando o processo de minimizao, temos: (marcao dos pares final / no final) marcamos AF, BF, CF, DF, EF. (exame de cada par no marcado) AB: inclumos AB na lista de BC; AC: inclumos AC na lista de BD;J. L. Rangel, L. C. Guedes - Ling. Formais - 4-17

AD: inclumos AD na lista de BE; AE: como BF est marcado, marcamos AE; BC: inclumos BC na lista de CD; BD: inclumos BD na lista de CE BE: como CF est marcado, marcamos BE; portanto, marcamos AD (da lista de BE); CD: inclumos CD na lista de DE; CE: como DF est marcado, marcamos CE; portanto, marcamos BD (da lista de CE) e AC (da lista de BD); DE: como EF est marcado, marcamos DE; portanto, marcamos CD (da lista de DE), BC (da lista de CD) e AB (da lista de BC). Os pares marcados aparecem na tabela abaixo: A B C D E F X X X X X A

X X X X B

X X X C

X X D

X E

F

(os pares restantes so equivalentes) No h pares de estados distintos restantes. Ou seja, cada estado equivalente apenas a ele mesmo. O afd mnimo idntico a M, apenas tem estados {A}, {B}, {C}, {D}, {E}, {F}. As cadeias d(XY) que distinguem os pares de estados XY so: d(AF) = d(BF) = d(CF) = d(DF) = d(EF) = . d(AE) = a d(BF) = a = a d(BE) = a d(CF) = a = a d(AD) = a d(BE) = a a = aa d(CE) = a d(DF) = a = a d(BD) = a d(CEF) = a a = aa d(AC) = a d(BD) = a aa = aaa d(DE) = a d(EF) = a = a d(CD) = a d(DE) = a a = aa d(BC) = a d(CD) = a aa = aaa d(AB) = a d(BC) = a aaa = aaaa Naturalmente, as cadeias d(XY) podem tambm ser obtidas por inspeo, sem executar o algoritmo. Exerccio 8: Construa um afd mnimo que aceite a linguagem L no alfabeto = {a, b}, com L ={ cdxcd | c, d , x * } Exerccio 9: Construa um afd mnimo que aceite o complemento da linguagem L do Exerccio 8.

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-18

4.6 - Equivalncia entre autmatos finitos e gramticas regulares Um dos resultados que devemos estabelecer neste captulo que a classe de linguagens reconhecidas por automatos finitos a classe das linguagens regulares. J sabemos, da seo anterior, que a classe das linguagens aceitas por af determinsticos exatamente a mesma classe das linguagens aceitas por af no determinsticos. Trata-se, portanto de estabelecer dois resultados simples, expressos atravs dos Teoremas 4.6 e 4.7, a seguir. Teorema 4.6: Toda linguagem regular aceita por um afnd. Demonstrao: Seja L uma linguagem regular. Portanto, L = L(G), para alguma gramtica regular G = ( N, , P, S ). Vamos construir um afnd M = ( K, , , i, F ) que aceita a linguagem L(G). Temos: K = N U { f }, i = S, F = { f }. Ou seja, os estados de M sero os no terminais de M, mais um estado f criado para ser o nico estado final. O estado inicial o smbolo inicial de G. (Note que f deve ser um smbolo novo, para no causar confuso.) As transies de M so dadas pelas regras de G: Inicialmente, faa (A, a)= , para todos os noterminais A e para todos os smbolos a, e para a = . A seguir, para todas as regras de G, se G tem uma regra A a B, acrescente uma transio de A para B com o smbolo a, ou seja, acrescente B a (A, a). se G tem uma regra A a, acrescente uma transio de A para f com o smbolo a, ou seja, acrescente f a (A, a). se G tem uma regra A , acrescente uma transio de A para f com , ou seja, acrescente f a (A, ). Devemos mostrar que, para qualquer x *, M aceita x sse x L(G). A demonstrao se completa pela verificao de que a sequncia de configuraes (S, x) |* (f, ) em M corresponde exatamente sequncia de passos da derivao S * x em G. Exemplo 7: Seja a gramtica regular G, dada por suas regras: SaA|bB AaA|bA|a BaB|bB|b que gera a linguagem { c x c | c {a, b} e x {a, b}*}. O afnd descrito na prova do teorema anterior M = ({ S, A, B, f }, { a, b }, , S, { f }), com dada pela tabela abaixo. S A B f a {A} { A, f } {B} b {B} {A} { B, f }

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-19

Seja a cadeia x=ababa. A cadeia x pertence linguagem, como se pode ver pela derivao S aA abA abaA ababA ababa. A cadeia x tambm aceita por M, como se pode ver pela sequncia de configuraes (S, ababa) | (A, baba) | (A, aba) | (A, ba) | (A, a) | (f, ) Note que os estados e os smbolos no terminais aparecem na mesma ordem, exceto por f, que no aparece na derivao. Os smbolos terminais, entretanto, tem tratamento diverso: so gerados na derivao, e aparecem desde sua introduo at a cadeia final, e so consumidos nas transies do afnd, aparecendo desde a configurao inicial at o momento de sua leitura.

Exemplo 8: Seja a gramtica regular G, dada por suas regras: SaA|bA| AaS|bS Temos L(G) = { x {a, b}* | |x| par }. O afnd descrito na prova do teorema anterior M = ({ S, A, f }, { a, b }, , S, { f }), com dada pela tabela abaixo. S A f {f} a {A} {S} b {A} {S}

Seja a cadeia x = abba, de comprimento par. Temos: S aA abS abbA abbaS abba. em G, e (S, abba) | (A, bba) | (S, ba) | (A, a) | (S, ) | (f, ) em M.

Teorema 4.7: Se L aceita por um automato finito, ento L regular. demonstrao: Podemos supor que L aceita por um afd M = (K, , , i, F). Vamos construir uma gramtica regular G para L. A gramtica G = (K, , P, i) tem como smbolos no terminais os estados de M, e como smbolo inicial o estado inicial i de M. As regras de G so dadas pelas transies e pelos estados finais de M: se p = (q, a) em M, G tem uma regra q ap em P. se q final (q F), G tem uma regra q em P A demonstrao semelhante a anterior: devemos mostrar que, para qualquer x *, M aceita x sse x L(G). Exemplo 9: Seja o afd M = ({q0, q1}, {a, b}, , q0, {q1}), com dada pela tabela abaixo.J. L. Rangel, L. C. Guedes - Ling. Formais - 4-20

q0 q1

a q1 q0

b q1 q0

M aceita as cadeias de {a, b}* que tem comprimento mpar. A gramtica G correspondente, de acordo com o teroema acima, q0 a q1 | b q1 q1 a q0 | b q0 | Para a cadeia x= ababa, temos (q0, ababa) | (q1, baba) | (q0, aba) | (q1, ba) | (q0, a) | (q1, ) e q0 aq1 abq0 abaq1 ababq0 ababaq1 ababa 4.7 - Expresses regulares Vamos agora definir expresso regular. A expresso regular a maneira mais compacta e mais simples de descrever conjuntos regulares, e usada com essa finalidade em construo de compiladores, editores, sistemas operacionais, protocolos, etc. A definio abaixo uma definio recursiva, e ser usada como base para outras definies, e para as demonstraes. Definio. Definimos uma expresso regular (er) em um alfabeto atravs de ER1 ER6 abaixo: ER1. ER2. ER3. ER4. ER5. ER6. uma er. uma er. para cada a , a uma er. Se e so er's, ento ( ) uma er. Se e so er's, ento ( ) uma er. Se uma er, ento (*) uma er.

Naturalmente, uma er se e somente se isso pode ser provado a partir de ER1 ER6. Usualmente, so omitidos os parenteses de er's, de acordo com a ordem de precedncia * e considerando os operadores como associativos esquerda. Alm disso, o smbolo frequentemente omitido. Exemplo 10: Seja = {a, b} e seja a expresso regular = (ab)* a b b, ou seja, com todos os parnteses, = (((((ab)*)a)b)b). Mostramos que uma er, mostrando sucessivamente que so er's as expresses a seguir: 1. 2. 3. 4. a b (ab) (ab)* de ER3 de ER3 de 1, 2 e ER4 de 3 e ER6J. L. Rangel, L. C. Guedes - Ling. Formais - 4-21

5. 6. 7.

(ab)*a (ab)*ab (ab)*abb

de 4, 1 e ER5 de 5, 2 e ER5 de 6, 2 e ER5.

Definio. A linguagem L[] associada a uma er (ou denotada pela er) definida de forma recursiva, seguindo a definio de er: ER1. L[] = ; ER2. L[] = {}; ER3. para cada a , L[a] = {a}; ER4. L[()] = L[] L[]; ER5. L[()] = L[] L[]; ER6. L[(*)] = (L[])*. Exemplo 11: Seja = (ab)*abb, como acima. Podemos determinar a linguagem L[] seguindo o mesmo caminho usado para provar que uma er. 1. L[a] = {a} de ER3 2. L[b] = {b} de ER3 3. L[ab] = L[a] L[b] = {a} {b} = {a, b} de 1, 2 e ER4 4. L[(ab)*] = (L[ab])* = {a, b}* de 3 e ER6 5. L[(ab)*a] = L[(ab)*] L[a] = {a, b}*{a} de 4, 1 e ER5 6. L[(ab)*ab] = L[(ab)*a] L[b] = = {a, b}*{a}{b} = {a, b}*{ab} de 5, 2 e ER5 7. L[(ab)*abb] = L[(ab)*ab] L[b] = = {a, b}*{ab}{b} = {a, b}*{abb} de 6, 2 e ER5 Assim, L[] a linguagem das cadeias que terminam em abb. Uma outra forma de indicar as mesmas propriedades de pertinncia vistas acima, mais adequada para provar a pertinncia em casos isolados : ER1. ER2. ER3. ER4. ER5. ER6. No existe x tal que x L[]. Se x L[], ento x= Se x L[a] (para a ), ento x=a. Se x L[ ], ento ou x L[], ou x L[]. Se x L[ ], ento x=yz, com y L[] e z L[]. Se x L[*], ento ou x=, ou x=yz, com y L[] e z L[*].

Os casos 1..5 so autoexplicativos; para o caso 6, basta observar a propriedade apresentada no Exerccio 10. Exerccio 10: Mostrar que, para qualquer linguagem L , L* = {} (L L*). Exemplo 12: Suponhamos que desejamos provar que x = abaabb L[], para a er =(ab)*abb, usando as propriedades acima. Os passos intermedirios da prova esto indicados abaixo: 1. 2. 3. 4. a L[a] a L[ab] b L[b] b L[ab] de 1 de 3J. L. Rangel, L. C. Guedes - Ling. Formais - 4-22

L[(ab)*] a L[(ab)*] de 2 e 5 ba L[(ab)*] de 4 e 6 aba L[(ab)*] de 2 e 7 abaa L[(ab)*a] de 8 e 1 abaab L[(ab)*ab] de 9 e 3 abaabb L[(ab)*abb] de 10 e 3 Note que cada ocorrncia de um smbolo (a ou b) em x fica associada a uma ocorrncia do mesmo smbolo em . No fundo a construo da prova de que x L[] consiste exatamente na descoberta de uma associao adequada. No exemplo acima, a nica associao possvel est indicada abaixo, pela numerao das ocorrncias de smbolos, na er e na cadeia considerada: 5. 6. 7. 8. 9. 10. 11. = (a1 b2 )* a3 b4 b5 , x = a1 b2 a1 a3 b4 b5 Em outros casos, podem ser possveis vrias associaes. Por exemplo, considere o alfabeto = {a, b, c}, a er = (ab)* (bvc)* e a cadeia y = bb. Neste caso, temos = (a1 b2)* (b3 c4)* e podemos ter y = b2 b2, ou y =b2 b3, ou ainda, y =b3 b3 . Definio. Dizemos que duas er's e so equivalentes se as linguagens a elas associadas so iguais: L[] = L[]. A equivalncia indicada por . Exerccio 11: Mostre que, dada uma er , sempre possvel construir uma er equivalente a , de forma que ou = , ou no contm o smbolo . Sugesto: considere as equivalncias * Exerccio 12: Mostre que, dada uma er , sempre possvel construir uma er equivalente a , de forma que ou = , ou = , e no contm o smbolo . Sugesto: considere as equivalncias ( )* * ( ) ( ) ( ) ( ) Exerccio 13: Suponha a seguinte definio: uma er ambgua se para algum xL[], existe mais de uma associao possvel entre as ocorrncias de smbolos em x e em . Sejam as expresses = (a b)* (b c)* = (a b)* (aa bb) (a b)*J. L. Rangel, L. C. Guedes - Ling. Formais - 4-23

- Mostre que e so ambguas, de acordo com a definio dada. - Construa er's equivalentes a e que no sejam ambguas.

Teorema 4.8: Toda linguagem denotada por uma expresso regular regular. Demonstrao. Seja uma er qualquer. Vamos mostrar que L() regular construindo um afnd M() que aceita L(), preparando para uma demonstrao por induo na estrutura de . Por simplicidade, vamos construir todos os afnd M() considerados nesta demonstrao com exatamente um estado final, distinto do estado inicial. Para uma er no elementar, o afnd M() ser construdo a partir dos afnd's das er's componentes. Para evitar a necessidade de nomear cada estado de cada uma dessas mquinas, vamos indicar a forma de composio graficamente. Por conveno, sempre representaremos o estado inicial esquerda, e o estado final direita. ER1. O afnd M() que aceita

ER2.

O afnd M() que aceita L[]

ER3. O afnd M(a) que aceita L[a], a

ER4. Se e so er's, podemos supor (pela Hiptese de Induo) que j esto construdos M() e M(). O afnd M( ) que aceita L[ ] obtido acrescentando um estado inicial e um final novos a M() e M(). As novas transies so transies com entrada do estado inicial novo para os antigos estados iniciais de M() e de M(), e dos antigos estados finais de M() e de M() para o novo estado final. O resultado

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-24

ER5. Se e so er's, podemos supor (pela Hiptese de Induo) que j esto construdos M() e M(). O afnd M( ) que aceita L[ ] obtido acrescentando um estado inicial e um final novos a M() e M(). As novas transies so transies com entrada do estado inicial novo para o antigo estado inicial de M(), do antigo estado final de M() para o antigo estado inicial de M(), e do antigo estado final de M() para o novo estado final. O resultado

ER6. Se uma er, podemos supor (pela Hiptese de Induo) que j est construdo M(). O afnd M(*) que aceita * obtido acrescentando um estado inicial e um final novos a M(). As novas transies so transies com entrada do estado inicial novo para o antigo estado inicial de M() e para o novo estado final e do antigo estado final de M() para o novo estado inicial.

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-25

O restante da demonstrao deixado como exerccio. Exemplo 13: Seja a er = (a b)* a. Vamos construir um afnd que aceita L(), seguindo a construo indicada na demonstrao acima. Os passos intermedirios e os resultados esto indicados nas tabelas a seguir M(a) inicial: final: M(b) inicial: final: M(a b) inicial: {A, C} {F} {F} a {B} a a {B} b b {D} b {D}

A B

C D

final:

E A B C D F

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-26

M((a b)*) inicial:

final: M((a b)*a) inicial:

G E A B C D F H

{E, H} {A, C} {F} {F} {G} {G} {E, H} {A, C} {F} {F} {G} {A'} {J}

a {B} a {B} {B'}

b {D} b {D}

final:

I G E A B C D F H A' B' J

Note que a sub-expresso a ocorre duas vezes em M(), e porisso foi necessrio incluir duas vezes M(a); para a segunda vez renomeamos os estados, que passaram a ser A' e B'. Exerccio 14: Construa um afd mnimo para a linguagem denotada pela er do Exemplo 13, a partir do afnd M() construdo no exemplo. Exerccio 15: Construa afd's mnimos que aceitem as linguagens denotadas pelas expresses regulares do Exerccio 13, = (a b)* (b c)* = (a b)* (aa bb) (a b)* Teorema 4.9: Toda linguagem regular denotada por uma expresso regular. Demonstrao: ver referncia citada. A demonstrao do Teorema 4.9 constri a expresso regular que representa a linguagem aceita por um afd examinando os caminhos entre o estado inicial e os estados finais do afd. O operador usado para tratar caminhos alternativos, o operador para tratar caminhos de comprimento maior que 1, e o operador * para tratar laos. Embora a construo seja interessante, na prtica o uso normalmente feito de er's paraJ. L. Rangel, L. C. Guedes - Ling. Formais - 4-27

especificao de linguagens regulares, e muito mais frequente a construo de afd's a partir de er's, do que a construo inversa.

4.8 - O Lema do Bombeamento para linguagens regulares Como mencionado anteriormente, precisamos de um resultado que nos permita demonstrar que algumas linguagens no so regulares. Este resultado o "Lema do Bombeamento", ou "Pumping Lemma", que nos diz que qualquer cadeia suficientemente longa z de uma linguagem regular pode ser decomposta em trs partes: z = uvw, de maneira que podemos construir outras cadeias da linguagem pela repetio da parte central v: todas as cadeias da forma u vi w so tambm da linguagem. Ou seja, podemos acionar a bomba quantas vezes quisermos, para criar quantas sentenas novas da linguagem desejarmos: uw, uvvw, uvvvw, ... . Para mostrar que uma linguagem no regular, mostramos que no h como decompor uma cadeia (qualquer, arbitrariamente longa) da linguagem de forma que seja possvel bombear e continuar na linguagem. Teorema 4.10: (Lema do Bombeamento) Seja L uma linguagem regular. Ento, existe um natural n tal que qualquer cadeia z de L com comprimento maior ou igual a n pode ser decomposta em trs cadeias u, v e w (z = uvw) de forma que |uv| n v para qualquer i 0, u vi w L Demonstrao: A demonstrao se baseia no fato de que para as cadeias longas z necessrio usar pelo menos um loop de estados num afd que aceite a linguagem. Assim, os smbolos de u so usados para chegarmos a um estado q do loop; os smbolos de v so usados para dar a volta no loop, de volta ao estado q; os smbolos de w so usados para ir de q at um estado final. Portanto, podemos dar quantas voltas no loop quisermos, e repetir v um nmero qualquer i de vezes: u vi w. As cadeias curtas (comprimento < n) devem ser excludas porque podem ser aceitas sem passar por nenhum loop. A demonstrao completa pode ser encontrada em [HopUll79]. Exemplo 14: Seja a linguagem regular L = L[] = L[], com = 1(01)* e = (10)*1. Considere a cadeia z=10101, pertencente a L. Podemos decompor a cadeia, da forma descrita no teorema acima, de diversas formas. Por exemplo: w = 01 w=1 w=1 Note que todas as cadeias das formas 1(01)i01, 10(10)i1, (1010)i1 pertencem a L. u=1 u = 10 u= v = 01 v = 10 v = 1010

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-28

Exerccio 16: (baseado no Exemplo 14) Mostre que e so equivalentes. Estime o valor de n (Teorema 4.10) para L. Mostre todas as formas de decomposio de z que satisfazem o Teorema. Exemplo 15: A linguagem L = { ai bi | i 0} no regular. (J vimos que L uma llc.) Vamos mostrar aqui que L no regular. A demonstrao por contradio. Suponha que L regular. Se L regular, o Teorema acima se aplica, e existe n tal que a decomposio descrita pode ser realizada para qualquer cadeia de comprimento igual ou maior que n. Seja k=n+1. Considere a cadeia z=ak bk. Qualquer decomposio z=uvw deve ter em v o mesmo nmero de a's e de b's, para que a propriedade de que o nmero de a's igual ao de b's se mantenha nas cadeias u vi w. Se isso no acontecer, quando acrescentarmos mais um v (aumentando i de 1), obteremos uma cadeia fora da linguagem. Portanto, v deve ser da forma aj bj, com j>0, j que v no pode ser vazia. Mas nesse caso, u v2 w conter a cadeia aj bj aj bj, com pelo menos um a depois de um b, o que no pode acontecer na linguagem. Ou seja, nenhuma decomposio possvel, contrariando o Teorema, e podemos concluir que L no regular. Exerccio 17: Mostre que a linguagem L = { x xR | x {0, 1}* } no regular. 4.9 - Propriedades de fechamento das linguagens regulares Vamos ver agora algumas propriedades de fechamento da classe das linguagens regulares. A maioria das provas pode ser feita usando mais de um dos formalismos usados para definir linguagens regulares: gramticas regulares, afd's, afnd's e expresses regulares veja o Exerccio 18. Teorema 4.11: A classe das linguagens regulares no alfabeto fechada para as operaes de (a) unio, (b) interseo, (c) complemento em relao a *, (d) concatenao e (e) fechamento transitivo (estrela). Demonstrao: (a) Vamos mostrar que se L1 e L2 so linguagens regulares, ento L1L2 uma linguagem regular. Sejam e er's tais que L()=L1 e L() = L2. Portanto, L1 L2 = L( ) tambm regular. (b) Vamos mostrar que se L1 e L2 so linguagens regulares, ento L1L2 uma linguagem regular. Sejam M1 = (K1, , 1, i1, F1) e M2 = (K2, , 2, i2, F2), afd's tais que L(M1)=L1 e L(M2) = L2. Seja M = (K1 K2, , , (i1, i2), F1 F2), com definida por ( (q1, q2), a) = ( 1(q1, a), 2(q2, a) ) M aceita L1L2 , porque

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-29

( (i1, i2), x) |* ( (f1, f2), ) em M sse ( i1, x) |* ( f1, ) em M1 e ( i2, x) |* (f2, ) em M2, e (f1, f2) final em M sse f1 final em M1 e f2 final em M2. L aceita por M, e portanto, regular. (c) Vamos mostrar que se L regular, o complemento L = * - L tambm regular. Seja M =(K, , , i, F) um afd que aceita L. Ento M' = (K, , , i, K-F) aceita L. Temos: $ $ M' aceita x (i, x) K - F (i, x) F M no aceita x x L x L. (d) Vamos mostrar que, se L1 e L2 so regulares, L1 L2 regular. Sejam e er's tais que L()=L1 e L() = L2. Portanto, L1 L2 = L( ) tambm regular. (e) Vamos mostrar que se L regular, o fechamento L* tambm regular. Seja a uma er tal que L() = L. Ento L(*)* = (L())* = L* tambm regular.

Exerccio 18: Considere o Teorema 4.11. Construa demonstraes alternativas para os casos indicados: (a) construindo uma gramtica regular para a unio de L1 e L2, a partir de gramticas regulares de L1 e L2. (b) usando (a), (c), e a propriedade de conjuntos (de Morgan) que diz que X Y = X Y (d) construindo uma gramtica regular para a concatenao de L1 e L2, a partir de gramticas regulares de L1 e L2. (e) construindo uma gramtica regular para o fechamento de L, a partir de uma gramtica regular de L. Exerccio 19: Mostre que, na construo usada na demonstrao do Teor. 4.11 parte (c), no pode ser usado um afnd. Sugesto: Considere o afnd

(reviso de 27fev97)

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-30