04 - Linguagens Regulares

LINGUAGENS REGULARES

Prof. Ronaldo R. Goldschmidt [email protected]


So linguagens mais simples, segundo Chomsky

Tambm chamadas de Linguagens do Tipo 3

Permitem desenvolver algoritmos de:

Reconhecimento de formalismos (*)

Gerao de formalismos (*)

Converso entre formalismos (*)

Possuem fortes limitaes de expressividade

Ex: Linguagens com duplo balanceamento no so regulares

Pascal, C, Java, dentre outras

Exemplo de aplicao: Anlise Lxica

(*) de pouca complexidade, grande eficincia e fcil implementao


Sistema de Estados Finitos:

Modelo matemtico de sistemas com entradas e sadas discretas.

Pode assumir um nmero finito e predefinido de estados.

Cada estado resume informaes do passado necessrias para determinar as aes sobre a entrada seguinte.

Ex. Clssico: Elevador

No memoriza requisies anteriores.

Cada estado indica andar corrente e direo movimento.

Entradas so requisies pendentes.


Um autmato Finito um sistema de estados finitos.

Constitui modelo computacional do tipo seqencial, comum em diversos estudos terico-formais da computao.

Pode ser:

Determinstico (AFD) Estado corrente e smbolo lido determinam um nico estado.

No Determinstico (AFN) Estado corrente e smbolo lido determinam um conjunto de estados.

Com Movimentos Vazios Dependendo do estado corrente e sem ler qualquer smbolo, o sistema pode assumir um conjunto de estados.

Movimentos vazios podem ser vistos como transies encapsuladas nas

quais, alm de uma eventual mudana de estado, nada mais pode ser

observado. Ideia anloga ao conceito de encapsulamento das Linguagens

de Programao.

Autmato Finito


Pode ser interpretado como uma mquina com controle finito constituda de:

Fita

Unidade de Controle

Programa (Funo Programa ou Funo Transio)

Autmato Finito Determinstico (AFD)

Fita finita, dividida em clulas, cada uma armazenando um smbolo do alfabeto de entrada.

No possvel gravar sobre a fita.

Unidade de controle possui nmero finito e predefinido de estados.

Unidade de controle se desloca para a direita.

a a b c c b a a b c

Controle


Formalmente: AFD=(,Q,,q0,F)

um alfabeto de smbolos de entrada

Q um conjunto finito de estados possveis

uma funo parcial denominada funo programa

: Q x Q

(p, a) = q uma transio do estado p para o estado q

q0 um elemento de Q, chamado estado inicial

F Q, denominado conjunto de estados finais



Autmato Finito Determinstico (AFD) Representao Grfica

Representao por meio de grafos dirigidos.

Estados so ns (vrtices)

Transies so arestas, ligando os ns

correspondentes. Ex: (p, a)=q

Estados iniciais e finais possuem

representao distinta dos demais.

Representaes de Transies Paralelas

(mesma origem e destino)


Autmato Finito Determinstico (AFD) Representao Grfica

Representaes Alternativas Outros Autores:



Representao do Processamento

a a b b

Controle Finito

fita com a cadeia w de entrada

Cabea de leitura

Incio do processo de reconhecimento pelo estado inicial qo


Representao alternativa de uma funo programa: tabela de dupla entrada.

a b

q0 q1 q2

q1 qf q2

q2 q1 qf

qf qf qf


Exemplo de uma funo programa:

Argumentos:

- Estado Atual

- Valor de Entrada

Sada:

- Prximo Estado


Exemplo: AFD que reconhece strings binrias com um nmero mpar de

smbolos 1.

Forma Tabular: Forma Grfica:


0 1

qo

q1

qo

q1

q1

qo

qo q1

0

1

1

0


Exemplo: Seja a cadeia 01110 e o AFD do exemplo anterior. Veja o

processamento:


0 1 1 1 0

Controle Finito

Cabea de leitura

q1 F

0 1 1 1 0

Controle Finito

(q0, 0) = q0

Cabea de leitura

Incio do AFD em q0

0 1 1 1 0

Controle Finito

(q0, 1) = q1

Cabea de leitura

q0

0 1 1 1 0

Controle Finito

(q1, 1) = q0

Cabea de leitura

q1

0 1 1 1 0

Controle Finito

(q0, 1) = q1

Cabea de leitura

q0

0 1 1 1 0

Controle Finito

(q1, 0) = q1

Cabea de leitura

q1


A computao de um autmato finito, para uma palavra de

entrada w, consiste na sucessiva aplicao da funo

programa para cada smbolo de w (da esquerda para a direita)

at ocorrer uma condio de parada.

Autmato Finito (AF)

Obs: AF sempre pra (palavra tem comprimento finito)

AF:

aceita W quando aps ltimo smbolo processado, o estado final rejeita W quando aps ltimo smbolo processado, o estado no final. ou quando a funo programa indefinida para o argumento


Exemplo: AFD que reconhece palavras de *, onde ={a}

M = (, Q, , qo, F)

Q = { qo }, = { a }, F = { q0 }

Forma Tabular : Forma Grfica :


a

qo qo qo

a


Exemplo: AFD que reconhece palavras sobre ={a},

iniciadas com a letra a.

M = (, Q, , qo, F)

Q = {qo, q1 }, = { a }, F = { q1 }

Forma Tabular : Forma Grfica :


a

qo

q1

q1

q1

qo q1

a a


Ex: Considere a linguagem L = {w / w possui aa ou bb como subpalavra}

O AFD M a seguir reconhece L.

M = ({a,b}, {q0, q1, q2, qf}, 1, q0, {qf})

q0

q1

q2

qf

a a

a b b

b

a,b

1 a b

q0 q1 q2

q1 qf q2

q2 q1 qf

qf qf qf

Obs: Os estados q1 e q2 so usados para representar a ocorrncia anterior de a e b, respectivamente.

E quanto a q0 e qf ? Para que servem?



Exerccio: Represente a funo programa e os componentes (, Q, , qo, F)

do AFD M1 abaixo. Em seguida, indique a sequncia de processamento de

M1 diante da cadeia 001122120. Qual o tipo de cadeia reconhecida (ou

aceita) por M1?



Exerccio: Considere o AFD M2 = ({a,b}, {q0, qf}, 2, q0, {qf}) cuja

funo programa encontra-se definida abaixo. Indique a representao

grfica de M2. Em seguida, indique a sequncia de processamento de M2

diante da cadeia aaba. Qual o tipo de cadeia reconhecida (ou aceita) por

M2?

2 a b

q0 q0 qf

qf q0 qf



Exerccio: Represente a funo programa e os componentes (, Q, , qo, F)

do AFD M3 abaixo. Em seguida, indique a sequncia de processamento de

M3 diante da cadeia aabbccabc. Quais os tipos de cadeia reconhecidos por

M3?



Seja M=(,Q,,q0,F) um AFD. A Funo Programa Estendida

ou Computao de M, denotada por:

*: Q x * Q

a funo programa : Q x Q estendida para palavras e indutivamente definida como segue:

(i) *(q, ) = q (base da induo)

(ii) *(q, aw) = *( (q,a), w) (passo indutivo)

Portanto, a funo programa estendida consiste na sucessiva

aplicao da funo programa para cada smbolo da palavra, a

partir de um dado estado.



Exemplo de Funo Programa Estendida:

Cadeia de entrada: abaa

Computao de abaa:

*(q0, abaa) =

*((q0,a), baa) =

*(q1, baa) =

*((q1,b), aa) =

*(q2, aa) =

*((q2,a), a) =

*(q1, a) =

*((q1,a), ) =

*(qf, ) = qf


q0

q1

q2

qf

a a

a b b b

a,b

Portanto, a cadeia abaa aceita pelo AFD


Outro exemplo de Funo Programa Estendida:

Cadeia de entrada: babab

Complete a computao de babab:

*(q0, babab) =


q0

q1

q2

qf

a a

a b b b

a,b

A cadeia babab aceita ou rejeitada pelo AFD ?


Seja M=(,Q,,q0,F) um AFD; A Linguagem Aceita ou

Linguagem Reconhecida por M, denotada por ACEITA(M) ou

L(M) o conjunto de todas as palavras de * aceitas por M a

partir do seu estado inicial q0.

Linguagem Aceita

L(M)={w/*(q0,w)F}, onde * a Funo Programa Estendida

Analogamente, a Linguagem Rejeitada por M:

REJEITA(M)={w/*(q0,w)F ou *(q0,w) indefinida}


Exemplo: Seja M=(,Q,,q0,F) o AFD abaixo; A Linguagem

Aceita ou Linguagem Reconhecida por M formada por cadeias

que possuem subcadeias aa ou bb.

= {a, b}, Q = {q0, q1, q2, qf}, F = {qf}

Linguagem Aceita

q0

q1

q2

qf

a a

a b b

b

a,b


ACEITA(M) REJEITA(M)=*

ACEITA(M) REJEITA(M)=

* - ACEITA(M) = REJEITA(M)

* - REJEITA(M) = ACEITA(M)

Todo autmato M define partio sobre *

ACEITA(M)

REJEITA(M)

*

Partio de *, induzida por um Autmato Finito M


Exemplo: Seja M=(,Q,,q0,F) o AFD abaixo.

ACEITA(M)={ | possui aa ou bb como subcadeias}.

REJEITA(M)={ | no possui aa nem bb como subcadeias}.

= {a, b}, Q = {q0, q1, q2, qf}, F = {qf}

Linguagem Aceita e Linguagem Rejeitada

q0

q1

q2

qf

a a

a b b

b

a,b


Diferentes autmatos finitos podem aceitar uma mesma

linguagem.

Assim, sendo M1 e M2 autmatos finitos:

M1 equivalente a M2

se, e somente se

ACEITA(M1)=ACEITA(M2)

Autmato Finitos Equivalentes


Exemplo: Sejam os autmatos M1 e M2 abaixo. Eles so

equivalentes?


M1 = (, Q, , qo, F)

Q = {qo, q1 , q2 }, = { a,b }, F = { q1 }

M2 = (, Q, , qo, F)

Q = {qo, q1 , q2 , q3 }, = { a,b }, F = { q1 }

qo q1

a a, b

q2 b

a, b qo q1

a a, b

q2 b

a, b

q3 a, b


Exemplo: Sejam os autmatos M1 e M2 abaixo. Eles so

equivalentes?


M1 = (, Q, , qo, F)

Q = { qo }, = { a }, F = { q0 }

M2 = (, Q, , qo, F)

Q = { qo }, = { a }, F = { q0 }

qo

a

qo q1

a a


Construa autmatos finitos determinsticos que reconheam cada uma

das seguintes linguagens sobre ={a,b}

a) { * : cada a em imediatamente precedido por um b}

b) { * : possui baba como subcadeia}

c) { * : no possui aa nem bb como subcadeias}

d) { * : possui um nmero mpar de a e um nmero par de b}

e) { * : possui aa e bb como subcadeias}

Exerccios:

Ateno:

Utilizar a ferramenta JFLAP para implementar e testar cada um dos AFDs

construdos no exerccios anterior.


L dita uma Linguagem Regular (ou Linguagem do tipo 3) se

existe pelo menos um AFD que aceita L.

Linguagem Regular (Tipo 3)

Ex: Considere a linguagem L = {w / w possui aa ou bb como subpalavra}

Como vimos, o AFD M abaixo reconhece L. Portanto L uma linguagem

regular.

M = ({a,b}, {q0, q1, q2, qf}, 1, q0, {qf})

q0

q1

q2

qf

a a

a b b

b

a,b

1 a b

q0 q1 q2

q1 qf q2

q2 q1 qf

qf qf qf

Atividades Prticas

Lista de Exerccios III Exerccios 1 e 5

Exerccio 8 da Lista III: Desenvolva um programa em computador (linguagem a

sua escolha) que simule o processamento de qualquer autmato finito

determinstico como segue: (a) Entradas: Alfabeto, conjunto de estados, funo

de transio, estado inicial, conjunto de estados finais e as palavras a serem

processadas; (b) Sadas: Condio de parada ACEITA/REJEITA e identificao

do estado de parada.

Exerccio de T1 (Valendo Nota)



Autmato Finito No Determinstico (AFN)



O no determinismo uma importante generalizao dos modelos de mquinas, sendo de fundamental importncia no estudo de

modelos para concorrncia e das linguagens formais.

A facilidade do no determinismo para AF expressa no programa, sendo este uma funo parcial que: dependendo do estado corrente e

do smbolo lido, determina um conjunto de estados do autmato.

Um Autmato Finito No Determinstico (AFN) pode assumir um conjunto de estados alternativos, como se existisse uma

multiplicao de unidades de controle, uma para cada alternativa,

sem compartilhar recursos com as demais. Da a importncia para

modelos concorrentes.

Qualquer AFN pode ser simulado por um AFD, contribuindo para a simplificao dos modelos.



Formalmente: AFN=(,Q,,q0,F)




:Qx2Q

(p, a) = {q1, q2, ..., qn}




Representao diagramtica em um AFN de uma transio

do tipo: (p, a) = {q1, q2, ..., qn}



De forma anloga a um AFD, a computao de uma palavra de

entrada w por um AFN consiste na aplicao da funo programa

para cada smbolo de w (esquerda direita) at ocorrer condio de

parada.

Condies de parada em um AFN:

Aceita a entrada w, quando aps processar o ltimo smbolo, existe pelo menos um estado pertencente ao conjunto de estados

finais.

Rejeita a entrada w, quando:

Aps processar o ltimo smbolo, todos os estados alcanados no pertencem ao conjunto de estados finais.

Em algum momento durante o processamento de w, a funo programa indefinida para o argumento.



Ex: AFN para reconhecer palavras que contenham aa ou bb.


a b

q0 {q0,q1} {q0,q2}

q1 {qf} -

q2 - {qf}

qf {qf} {qf}

q0

q1

q2

qf

a a

b b

a,b

a,b

Com este AFN existem 3 caminhos:

O ciclo em q0 aps passar em toda a entrada

O caminho q0/q1/qf garante a ocorrncia de aa

O caminho q0/q2/qf garante a ocorrncia de bb


Seja M=(,Q,,q0,F) um AFN. A Funo Programa Estendida

ou Computao de M, denotada por:

*: 2Q x *2Q

a funo programa : Q x 2Q estendida para palavras e conjuntos de estados, indutivamente definida como segue:

(i) *(P, ) = P (base da induo)

(ii) *(P,aw)= *(qP(q,a),w) (passo indutivo)

Transio estendida:

*({q1, q2,..., qn},a) = (q1, a) (q2, a) ... (qn, a)



Exemplo de Funo Programa Estendida:

Cadeia de entrada: abaa

Computao de abaa:

*({q0}, abaa) =

*((q0, a), baa) =

*({q0, q1}, baa) =

*((q0,b) (q1,b), aa) =

*({q0, q2}, aa) =

*((q0,a) (q2,a), a) =

*({q0, q1}, a) =

*((q0,a) (q1,a), ) =

*({q0, q1, qf}, ) = {q0, q1, qf} F


Portanto, a cadeia abaa aceita pelo AFN

q0

q1

q2

qf

a a

b b

a,b

a,b


Outro exemplo de Computao:

Cadeia de entrada: abbaba

Computao de abbaba:

*({q0}, abbaba) =


A cadeia abbaba aceita pelo AFN ?

q0

q1

q2

qf

a a

b b

a,b

a,b


Outro exemplo de Computao:

Cadeia de entrada: ababa

Computao de ababa:

*({q0}, ababa) =


A cadeia ababa aceita pelo AFN ?

q0

q1

q2

qf

a a

b b

a,b

a,b


Autmato Finito No Determinstico (AFN) e Linguagem Aceita

Seja M=(,Q,,q0,F) um AFN; A Linguagem Aceita ou

Linguagem Reconhecida por M, denotada por ACEITA(M) ou

L(M) o conjunto de todas as palavras de * tais que existe pelo

menos um caminho alternativo que aceita a palavra a partir do

seu estado inicial {q0}.

L(M) = {w / *({q0},w) F }

Analogamente, a Linguagem Rejeitada por M:

REJEITA(M)={w / *({q0},w) F = ou *({q0},w) indefinida}


Exemplo: Seja M=(,Q,,q0,F) o AFN abaixo; A Linguagem

Aceita ou Linguagem Reconhecida por M formada por cadeias

que possuem subcadeias aa ou bb.

= {a, b}, Q = {q0, q1, q2, qf}, F = {qf}

q0

q1

q2

qf

a a

b b

a,b

a,b



Exemplo: Seja a linguagem L={w / w possui aaa como sufixo}

sobre o alfabeto {a,b}. Construa um AFN M tal que

L=ACEITA(M).

M=({a,b}, {q0, q1, q2, qf}, , q0, {qf})

Os estados q1, q2 e qf so os marcadores das ocorrncias de a.



Exerccio: Seja a linguagem L={w / w possui aaa como sufixo}

sobre o alfabeto {a,b}. Construa um AFD M tal que

L=ACEITA(M).



Equivalncia entre AFD e AFN

Teorema: A classe dos Autmatos Finitos Determinsticos

equivalente classe dos Autmatos Finitos No Determinsticos.

Demonstrao: (Menezes, 2005, p.58)

1. Mostrar que a partir de um AFD qualquer MD possvel construir um AFN MN que

realiza as mesmas computaes do MD. Isso imediato pois basta adaptar a funo

programa de MD de forma que as sadas sejam conjuntos unitrios formados pelos

estados definidos na funo original, ou seja, sendo:

D: Q x Q, tal que: (p, a) = q, faz-se a seguinte adaptao:

N:Qx2Q , tal que: (p, a) = {q}

AFD AFN



Demonstrao: (cont.1)

2. Mostrar que a partir de um AFN qualquer MN possvel construir um AFD MD que

realiza as mesmas computaes do MN.

Seja MN = (, QN, N, q0, FN) um AFN qualquer.

Construmos um AFD MD = (, QD, D, q0 , FD) da seguinte forma:

a) QD o construdo a partir de todas as combinaes, sem repeties, de estados de QN.

Cada estado de QD denotado por: q1 q2 ... qn , onde qi QN, para i {1, 2, ..., n}

importante observar que a ordem dos elementos no distingue os estados.

Exemplo: qu qv = qv qu




2. Mostrar que a partir de um AFN qualquer MN possvel construir um AFD MD que

realiza as mesmas computaes do MN.

Seja MN = (, QN, N, q0, FN) um AFN qualquer.

Construmos um AFD MD = (, QD, D, q0 , FD) da seguinte forma:

b) D : QD x QD tal que:

D (q1 ...qn, a) = p1 ...pm, se e somente se, N* ({q1, ..., qn }, a) = {p1 ...pm }

c) q0 o estado inicial

d) FD o conjunto de todos os estados q1 q2...qn QD tal que alguma componente qi pertence a FN, para i {1, 2, ..., n}




A demonstrao de que o AFD MD simula as mesmas computaes do AFN MN. por

induo no tamanho de uma palavra qualquer w *.

Deve-se mostrar que:

D *(q0, w) = q1 ...qu, se e somente se, N

* ({q0}, w) = {q1, ..., qu}

a) Base de Induo. Seja w tal que |w| = 0. Portanto, w = , e:

D *(q0, ) = q0, se e somente se, N

* ({q0}, ) = {q0} verdadeiro pela definio de

funo programa estendida;

b) Hiptese de Induo. Seja w tal que |w| = n e n 1. Suponha verdadeiro que:


* ({q0}, w) = {q1, ..., qu};




b) Hiptese de Induo. Seja w tal que |w| = n e n 1. Suponha verdadeiro que:


* ({q0}, w) = {q1, ..., qu};

c) Passo de Induo. Seja w tal que |wa| = n + 1 e n 1. Ento, deseja-se mostrar que:

D*(q0, wa) = p1 ...pv, se e somente se, N

* ({q0}, wa) = {p1, ..., pv}. Essa afirmao

equivale, pela hiptese de induo, a:

D( q1 ...qu , a) = p1 ...pv, se e somente se, N* ({q1, ..., qu}, a) = {p1, ..., pv}, o que

verdadeiro pela prpria definio de D.

Logo, MD simula MN e, portanto, as classes de AFD e AFN so equivalentes.



Teorema: A classe dos Autmatos Finitos Determinsticos

equivalente classe dos Autmatos Finitos No Determinsticos.

Obs: Determinismo x No Determinismo

Muitas vezes mais fcil desenvolver um AFN do que um AFD,

pois as solues deterministas, em geral, so no triviais e

envolvem um nmero possivelmente grande de estados. Em

seguida, a partir do AFN pode-se construir o AFD.

AFD AFN



Exemplo: Considere o AFN reconhecedor da linguagem L={w / w possui aaa

como sufixo} sobre o alfabeto {a,b}:

M=({a,b}, {q0, q1, q2, qf}, , q0, {qf})

Construa um AFD a partir dele.

Seja MD=({a,b}, QD, D, q0, FD)

QD = {q0, q1, q2, qf, q0 q1, q0 q2, ..., q0 q1 q2 qf }

FD = {qf, q0 qf , q1 qf , q2 qf , ..., q0q1q2qf }

Obs: QD e FD so combinaes de estados de Q e F



Exemplo (cont.): M=({a,b}, {q0, q1, q2, qf}, , q0, {qf})

MD=({a,b}, QD, D, q0, FD)

QD = {q0, q1, q2, qf, q0 q1, q0 q2, ..., q0 q1 q2 qf }

FD = {qf, q0 qf , q1 qf , q2 qf , ..., q0q1q2qf }

Por simplicidade, foram explicitados os estados para os quais a funo programa est

definida. Alm disso, os estados foram renomeados para p0 q0, p1 q0 q1, p2 q0 q1 q2 e pf q0 q1 q2 qf .

D a b

q0 q0 q1 q0

q0 q1 q0 q1 q2 q0

q0 q1 q2 q0 q1 q2 qf q0

q0 q1 q2 qf q0 q1 q2 qf q0



Exemplo: Considere o AFN reconhecedor da linguagem L={w / w possui aa

ou bb como subcadeias} sobre o alfabeto {a,b}:

M=({a,b}, {q0, q1, q2, qf}, , q0, {qf})

Construa um AFD a partir dele.

q0

q1

q2

qf

a a

b b

a,b

a,b



Exemplo: Elabore um AFN reconhecedor da linguagem L={w / w possui aa

ou bb como subcadeias e ccc como sufixo} sobre o alfabeto {a,b,c} e, em

seguida, converta-o em um AFD.



Exerccios: Converta os AFN a seguir em AFD:

a)

b)



Exerccios: Converta os AFN a seguir em AFD:

c)



Como:

Toda linguagem L regular se existe pelo menos um AFD M tal que ACEITA(M)=L.

A classe dos AFN equivalente classe dos AFD

Podemos concluir que:

Dada uma linguagem L, se existe pelo menos um AFN M tal que ACEITA(M)=L, ento L uma linguagem regular.

Linguagens Aceitas por AFN so, portanto, Linguagens Regulares (Tipo 3)


Autmato Finito com Movimentos Vazios

Movimentos vazios generalizam os movimentos no determinsticos.

Um movimento vazio uma transio sem leitura de smbolo algum da fita.

AFs com movimentos vazios facilitam construes e demonstraes relacionadas a autmatos.

Definio: Um AFN com Movimentos Vazios (AFN) um autmato

M tal que: M=(,Q,,q0,F), onde:

:Q x ({})2Q e

(p, ) = {q1, q2, ..., qn} um movimento vazio ou transio vazia do autmato.



Supondo um AFN=(,Q,,q0,F) tal que:

(q, ) = {p0}

(q, a1) = {p1}

...

(q, an) = {pn}

Ilustrao diagramtica:

q

p0 p1 pn ...

a1

an



Exemplo: Considere o AFN abaixo que aceita a linguagem

L={aibj / i, j 0}



Exemplo: Considere o AFN abaixo que aceita a linguagem

L={aibjckam / i, j, k, m 0}

Compare com a complexidade do AFD abaixo:


Equivalncia entre AFN e AFN

Teorema: A classe dos Autmatos Finitos com Movimentos

Vazios equivalente classe dos Autmatos Finitos No

Determinsticos.


Obs:

Linguagens aceitas por autmatos finitos com movimentos

vazios so, portanto, Linguagens Regulares (Tipo 3).

AFN AFN


Equivalncia entre AFD, AFN e AFN

Teorema: A classe dos Autmatos Finitos com Movimentos

Vazios equivalente classe dos Autmatos Finitos

Determinsticos.

Demonstrao: (Transitividade)

AFN AFN AFD


Toda linguagem regular pode ser descrita por uma Expresso

Regular.

Trata-se de um formalismo denotacional, porm gerador, pois

se pode inferir como construir as palavras de uma linguagem.

Expresses regulares so consideradas adequadas para a

comunicao humano x humano e, principalmente, para a

comunicao humano x mquina.

Expresses Regulares


Expresses regulares so notaes padronizadas para

caracterizar sequncias de textos.

Possuem muita aplicao prtica no contexto de busca na

web, recuperao de informao, processamento de textos,

clculo de freqncias de termos em corpora (colees de

documentos), dentre outras.

Formalmente, uma expresso regular uma notao algbrica

para caracterizar um conjunto de strings.

Expresses Regulares


Exemplo de aplicao no Google para busca na Web:

Linguagens Formais Pginas contendo combinao exata

Linguagens Formais Pginas contendo ambas as palavras

Linguagens OR Formais Pginas contendo pelo menos uma

Linguagens Formais Pginas contendo somente a primeira

Parnteses definem precedncia (T1 OR T2) T3

Expresses Regulares


Definio: Uma Expresso regular (abreviada por ER) sobre um alfabeto

indutivamente definida como:

a) Base de Induo

Para qualquer x , a expresso x regular e representa a linguagem {x}

A expresso regular e representa a linguagem vazia

A expresso regular e representa a linguagem {}

b) Passo de Induo: Se r e s so expresses regulares e representam as linguagens R

e S, respectivamente, ento a expresso:

(r + s) regular e representa a linguagem R S (Unio)

(rs) regular e representa a linguagem RS={uv / u R e v S} (Concatenao)

(r*) regular e representa a linguagem R* (Concatenao Sucessiva)

Expresses Regulares


Se r uma expresso regular, a linguagem que ela representa

chamada Linguagem Gerada por r, cuja notao :

L(r) ou GERA(r)

A omisso de parnteses em uma ER usual, respeitando as

seguintes convenes:

A concatenao sucessiva tem precedncia sobre a concatenao e a unio.

A concatenao tem precedncia sobre a unio.

Expresses Regulares


A tabela abaixo apresenta exemplos de expresses regulares e

as correspondentes linguagens geradas:

Expresses Regulares

Expresso Regular Linguagem Gerada

aa Somente a palavra aa

ba* Todas as palavras iniciadas por b, seguidas por zero ou

mais a

(a+b)* Todas as palavras sobre {a, b}

(a+b)*aa(a+b)* Todas as palavras contendo aa como subpalavra

a*ba*ba* Todas as palavras contendo exatamente dois b

(a+b)*(aa+bb) Todas as palavras terminadas por aa ou bb

(a+)(b+ba)* Todas as palavras que no possuem dois a consecutivos


Exemplo: Detalhe a linguagem gerada pela expresso regular

(a+b)*(aa+bb):

a e b denotam {a} e {b}, respectivamente

a + b denota {a} {b} = {a, b}

(a + b)* denota {a, b}*

aa denota {a}{a}={aa} e bb denota {b}{b}={bb}

(aa+bb) denota {aa} {bb} = {aa, bb}

(a+b)*(aa+bb) denota {a,b}*{aa, bb}

Portanto, GERA ((a+b)*(aa+bb)) corresponde linguagem:

{aa, bb, aaa, abb, baa, bbb, aaaa, aabb, abaa, abbb, baaa, babb, bbaa,

bbbb, ...}

Expresses Regulares


Exerccio:

Defina expresses regulares para as seguintes linguagens sobre {a,b}:

a) Cadeias que possuam aa como prefixo e bb como sufixo.

b) Cadeias que s possuam trs a no necessariamente consecutivos.

c) Cadeias em que todo a seja seguido de um nico b.

d) Cadeias em que todo a seja precedido de um nico b.

e) Cadeias que no possuam dois b consecutivos.

f) Cadeias iniciadas por aa ou bb e que possuam ab como subcadeia.

g) Cadeias sem ocorrncias de b.

h) Cadeias aa ou bb ou ab.

Expresses Regulares


Teorema: Se r uma expresso regular, ento GERA(r) uma linguagem

regular.


Seja r uma expresso regular, precisamos mostrar que existe um AF M tal que

ACEITA(M) = GERA(r).

Na construo de M, ACEITA(M) = GERA(r) demonstrada por induo no

nmero de operadores.

Expresses Regulares



regular.

Demonstrao: (Cont.1)

a) Base de Induo. Seja r uma expresso regular com zero operadores.

Ento r s pode ser da forma:

r = ou r = ou r = x (onde x )

Os AF abaixo aceitam as linguagens acima:

M1 = (, {q0}, 1, q0, )

M2 = (, {qf}, 2, qf, {qf})

M3 = ({x}, {q0 , qf}, 3, q0, {qf})

Expresses Regulares



regular.


b) Hiptese de Induo. Seja r uma expresso regular com at n > 0

operadores. Suponha que seja possvel definir um AF M tal que:

ACEITA(M) = GERA(r)

c) Passo de Induo. Seja r uma expresso regular com at n + 1

operadores. Ento r pode ser representada por um dos seguintes casos

(onde r1 e r2 possuem juntos, no mximo, n operadores):

r = r1 + r2

r = r1 r2

r = r1*

Expresses Regulares



regular.


c) Passo de Induo. Seja r uma expresso regular com at n + 1

operadores. Ento r pode ser representada por um dos seguintes casos

(onde r1 e r2 possuem juntos, no mximo, n operadores):

r = r1 + r2 r = r1 r2 r = r1*

Por hiptese de induo, possvel construir os autmatos:

M1 = (1, Q1, 1, q01, {qf1}) e M2 = (2, Q2, 2, q02, {qf2})

tais que:

ACEITA(M1) = GERA(r1) e ACEITA(M2) = GERA(r2)

Expresses Regulares



regular.


c) Por hiptese de induo, possvel construir os autmatos:

M1 = (1, Q1, 1, q01, {qf1}) e M2 = (2, Q2, 2, q02, {qf2})

tais que: ACEITA(M1) = GERA(r1) e ACEITA(M2) = GERA(r2)

Sem perda de generalidade, assume-se que M1 e M2 possuem exatamente um

estado final e que Q1 Q2 = .

Assim, os seguintes AFN que aceitam GERA(r) podem ser construdos para

cada operao:

Expresses Regulares



regular.


c) Assim, os seguintes AFN que aceitam GERA(r) podem ser construdos

para cada operao: (i) r = r1 + r2

Seja M = (1 2, Q1 Q2 {q0, qf} , , q0, {qf}):

A partir de q0, M realiza transies para os estados q01 e q02. M1 e M2

processam de forma no determinstica e, basta que um deles aceite a

entrada , para que M tambm aceite.

Expresses Regulares



regular.



para cada operao: (ii) r = r1 r2

Seja M = (1 2, Q1 Q2 , , q01, {qf2}):

Ao processar os mdulos M1 e M2 em sequncia, M aceita uma entrada

se, e somente se, o prefixo pertencer a ACEITA(M1) e o sufixo pertencer

a ACEITA(M2).

Expresses Regulares



regular.



para cada operao: (iii) r = r1*

Seja M = (1, Q1 {q0, qf} , , q0, {qf}):

A transio vazia de q0 para qf garante a aceitao da palavra vazia e o

ciclo de qf1 para q01 permite o sucessivo processamento de M1 para

assegurar o reconhecimento de duas ou mais concatenaes sucessivas.

Expresses Regulares



regular.

Demonstrao: (Concluso)

Assim, dada r uma expresso regular, mostramos que sempre possvel

construir um AF M tal que ACEITA(M) = GERA(r).

Portanto, como existe tal autmato, por definio, GERA(r) uma linguagem

regular.

Expresses Regulares



regular.

Exemplo: (a+b)*aa expresso regular.

L=GERA ((a+b)*aa) = {aa, aaa, baa, aaaa, abaa, baaa, ...}

O AFD ao lado aceita L.

Portanto, L regular.

Expresses Regulares

q0

q1

q2

qf

a a

a b b

a

b

b


Teorema: Se L uma linguagem regular, ento existe uma expresso regular r

tal que: GERA(r)=L


Exemplo: L = {w / w possui aa ou bb como subpalavra} uma linguagem

regular.

O AFD aceita L:

Gera((a+b)*(aa+bb)(a+b)*) = L

Expresses Regulares

q0

q1

q2

qf

a a

a b b b

a,b


Exerccio: Construa um AFN que aceita GERA(a*(aa+bb))

Obs: Os estados foram omitidos para fins de simplificao dos esquemas.

Expresses Regulares


Exerccio: Construa um AFN que aceita GERA(a*(aa+bb)) (cont.)

Sugesto: Experimente o recurso de converso disponvel no JFLAP

Expresses Regulares


O conceito de gramtica pode ser usado para definir tanto

linguagens regulares como linguagens no regulares.

Entretanto, possvel estabelecer restries nas regras de

produo de forma a definir a Classe das Linguagens Regulares.

Existe mais de uma forma de definir uma Gramtica Regular. Na

sequncia so apresentadas quatro dessas formas, denominadas

Gramticas Lineares.

Gramtica Regular


Seja G=(V,T,P,S) uma gramtica. Sejam A e B elementos de V e w uma

palavra de T*. Diz-se que G uma Gramtica Linear se todas as suas

produes encontram-se em uma e somente uma das seguintes formas:

Gramtica Linear Direita (GLD): A wB ou A w

Gramtica Linear Esquerda (GLE): A Bw ou A w

Gramtica Linear Unitria Direita (GLUD): Como GLD e |w| 1

Gramtica Linear Unitria Esquerda (GLUE): Como GLE e |w| 1

Nota-se que, nas gramticas lineares, o lado direito de uma produo

constitudo por, no mximo, uma varivel. Adicionalmente, esta varivel, se

existir, sempre antecede (linear esquerda) ou sucede (linear direita)

qualquer sub-palavra (eventualmente vazia) de smbolos terminais.

Gramtica Regular


Exemplos de Gramticas Lineares:

Gramtica Linear Direita: G=({S, A}, {a, b}, P, S), sendo que P possui as seguintes produes: S aA e A baA |

Gramtica Linear Esquerda: G=({S}, {a, b}, P, S), sendo que P possui a seguinte produo: S Sba | a

Gramtica Linear Unitria Direita: G=({S, A}, {a, b}, P, S), sendo que P possui as seguintes produes: S aA e A bA |

Gramtica Linear Unitria Esquerda: G=({S}, {a, b}, P, S), sendo que P possui a seguinte produo: S Sb | a

Gramtica Regular


Definio: Uma gramtica G dita ser uma Gramtica Regular (GR) se G

uma gramtica linear.

Definio: Seja G=(V,T,P,S) uma gramtica G. A Linguagem Gerada por G

(denotada por L(G) ou GERA(G)) tal que L(G)={w T* / S + w}

Exemplo: A Linguagem a(ba)* gerada pelas seguintes gramticas regulares:

Linear Direita: G=({S, A}, {a, b}, P, S), sendo que P possui as seguintes produes: S aA e A baA |

Linear Esquerda: G=({S}, {a, b}, P, S), sendo que P possui a seguinte produo: S Sba | a

Gramtica Regular


Observao: Gramtica Linear Esquerda e Linear Direita.

Supondo |w| 1, se uma gramtica tiver simultaneamente produes do tipo

AwB (linear direita) e do tipo ABw (linear esquerda), ento a

linguagem gerada por ela poder no ser regular. A prpria gramtica no

seria regular.

Exemplo: L={anbn/ n0} no uma linguagem regular. Procure elaborar uma

gramtica que contenha tanto produes lineares direita quanto produes

lineares esquerda e que gere L.

Gramtica Regular


Teorema: Se L uma linguagem gerada por uma gramtica regular, ento L

uma linguagem regular.

Demonstrao: (Menezes, 2005, p. 75)

Exemplo: Seja L=GERA(G), onde G=({S, A}, {a, b}, P, S), sendo que P

possui as seguintes produes: S aA e A baA |

G linear direita, e, portanto, regular.

O AFD ao lado aceita L.

Portanto L regular.

Gramtica Regular

q0

q1

q2

qf

a

b

a b

a

q3 a

a,b

b


Exemplo de construo de um AFN a partir de uma gramtica linear (esse

processo pode ser automatizado):

Considere a gramtica G = ({S, A, B}, {a,b}, P, S)

P = {S aA, A bB | , B aA}

O AFN que reconhece GERA(G) : M = ({a,b}, {S, A, B, qf}, , S, {qf}), onde:

Gramtica Regular


Teorema: Se L uma linguagem regular, ento existe G, gramtica regular

que gera L.


Exemplo: L={a, aba, ababa, abababa, ...}=GERA(a(ba)*), L linguagem

regular.

G=({S, A}, {a, b}, P, S), sendo que P possui as seguintes produes: S aA

e A baA |

G uma gramtica regular tal que L=GERA(G). Logo existe G regular que

gera L.

Gramtica Regular


Exemplo de construo de uma gramtica regular a partir de um AFD (esse

processo pode ser automatizado):

Considere o AFD M = ({a,b,c}, {q0, q1, q2}, , q0, {q0, q1, q2}), onde:

A gramtica regular correspondente G:

G = ({q0, q1, q2}, {a,b,c}, P, S), onde P construdo

como mostrado na tabela ao lado.

Gramtica Regular

Atividades Prticas

Lista de Exerccios III At o nmero 8 (Parte I)

Leituras Recomendadas

Cap. 3 Paulo Blauth Menezes

Sees 3.1 a 3.6 Marcus Ramos

Sees 2.1 a 2.3 Papadimitriou

Cap. 3 Hopcroft & Ullman



Uma das principais caractersticas das linguagens regulares o fato de serem

representadas por formalismos de pouca complexidade, grande eficincia e

fcil implementao.

Entretanto, por ser uma classe de linguagem relativamente simples, restrita e

limitada, levantando questes a serem analisadas:

Como determinar se uma linguagem regular?

A classe das linguagens regulares fechada para operaes de unio, concatenao e interseo?

Como verificar se uma linguagem regular finita, infinita ou mesmo vazia?

possvel analisar duas linguagens regulares quaisquer e concluir se so iguais ou diferentes?

Propriedades


Traduo dos Formalismos das Linguagens Regulares:

Propriedades


Com relao complexidade de algoritmos, autmatos finitos pertencem

classe de algoritmos mais eficientes em termos de tempo de processamento,

supondo que toda entrada necessita ser lida.

Propriedades

Complexidade Computacional: Seja f(n) funo no negativa para todo

n, n 0. Dizemos de f(n) O(g(n)), se: Existem um inteiro n0 e uma

constante c 0 tais que: Para todo n n0, f(n) cg(n)

Notao: f(n)=O(g(n))


Com relao complexidade de algoritmos, autmatos finitos pertencem

classe de algoritmos mais eficientes em termos de tempo de processamento,

supondo que toda entrada necessita ser lida.

De fato, qualquer autmato finito que solucione um problema igualmente

eficiente, a menos de eventual redundncia de estados, a qual no influi no

tempo de processamento.

Tal redundncia de estados pode ser eliminada, determinando-se um

Autmato Finito Determinstico Mnimo, ou simplesmente, Autmato Finito

Mnimo.

Propriedades


Lema do Bombeamento Ideia Bsica:

Se L uma linguagem regular, ento L aceita por um autmato finito determinstico M que possui um nmero finito e predefinido de n estados.

Se M reconhece uma entrada w de comprimento maior ou igual ao nmero de estados n, obrigatoriamente o autmato assume algum estado q mais de uma

vez (existindo, portanto, um ciclo na funo programa).

Logo, w pode ser dividida em trs subpalavras w=uvz tal que |uv| n, |v| 1, onde v a parte de w reconhecida pelo ciclo.

Tal ciclo pode ser executado (bombeado) zero ou mais vezes. Portanto, para qualquer i 0, u vi z aceita por M (ou seja, palavra da linguagem).

Propriedades Bombeamento para Linguagens Regulares


Lema do Bombeamento:

Se L uma linguagem regular, ento:

existe uma constante n tal que,

para qualquer palavra w de L onde |w| n, w pode ser definida como w=uvz

onde |uv| n, |v| 1,

e sendo que, para todo i, i 0, u vi z palavra da L.


Seja L uma linguagem regular. Portanto, existe um AFD M = (,Q,, q0,F) tal

que ACEITA(M) = L.

Seja n a cardinalidade de Q.

Suponhamos w uma palavra de L tal que |w| = m e m n

Portanto, w = a1 a2 ... am




Demonstrao: (cont. 1)

Suponhamos w uma palavra de L tal que |w| = m e m n

Portanto, w = a1 a2 ... am

(q0, a1) = q1, (q1, a2) = q2, ..., (qm-1, am) = qm

Como m n, ento existem r e s tais que: 0 r s n e

qr =qs

*(q0, a1 ... ar) = qr

*(qr, ar+1 ... as) = qs

*(qs, as+1 ... am) = qm

Ou seja, M passa mais de uma vez no estado qr =qs





*(q0, a1 ... ar) = qr

*(qr, ar+1 ... as) = qs

*(qs, as+1 ... am) = qm

Ou seja, M passa mais de uma vez no estado qr =qs

Assim, sejam :

u = a1 ... ar v = ar+1 ... as z = as+1 ... am

Como r s n, ento: | v | 1 e | uv | n

Como qr =qs , ento v reconhecida em um ciclo. Portanto, para todo i 0, uviz

palavra de L.




Se L uma linguagem regular, ento:

existe uma constante n tal que,

para qualquer palavra w de L onde |w| n, w pode ser definida como w=uvz

onde |uv| n, |v| 1,

e sendo que, para todo i, i 0, u vi z palavra da L.

Exemplo: Considerando o autmato abaixo (qual a linguagem regular definida

por ele?), n=4 e, no caso particular de w=abbba, vale que: u=a, v=bb, z=ba



O Lema do Bombeamento garante que os formalismos regulares so capazes de

expressar diversos bombeamentos (mltiplas aplicaes do lema).

Por exemplo, as seguintes linguagens so regulares (quais seriam os AF?):

Bombeamento Duplo: {anbm / n 0 e m 0}

Bombeamento Triplo: {anbmar / n 0, m 0 e r 0}

Bombeamento Qudruplo: {anbmarbs / n 0, m 0, r 0 e s 0}

etc...

Cada conjunto de repeties sucessivas de uma subpalavra pode ser associado a

um estado distinto, caracterizando uma aplicao do lema do bombeamento.

Assim, mais de um conjunto de repeties sucessivas caracteriza mltiplas

aplicaes do lema.



Exemplo de aplicao do Lema do Bombeamento:

Mostre que a linguagem L sobre {a,b} no regular (ou no-regular):

L={w / w possui o mesmo nmero de smbolos a e b}

Demonstrao (por reduo ao absurdo):

Suponhamos que L seja regular. Ento existe um AFD M com n estados que

aceita L (teorema anterior).

Seja w=anbn palavra de L, sendo |w| = 2n n

Pelo lema do bombeamento, w pode ser definida como w = uvz tal que:

|uv| n e |v| 1.

Portanto, uv formado apenas de smbolos a.



Exemplo de aplicao do Lema do Bombeamento:

Mostre que a linguagem L sobre {a,b} no regular (ou no-regular):

L={w / w possui o mesmo nmero de smbolos a e b}

Demonstrao (cont.):

Pelo lema do bombeamento, w pode ser definida como w = uvz tal que:

|uv| n e |v| 1

Portanto, uv formado apenas de smbolos a.

Tambm pelo lema do bombeamento, para todo i, i 0, u vi z palavra da L.

Logo, se tomarmos i=2, u v2 z palavra da L, o que um absurdo, pois a nova

palavra teria mais smbolos a do que smbolos b. Portanto, L no-regular.

Sugesto: Utilize o JFLAP para exercitar a aplicao do lema do

bombeamento com esta e outras linguagens no regulares. Deixe o computador

iniciar o jogo e apresente parties de w que ilustrem a no aplicao do lema.



Operaes sobre linguagens podem ser usadas para:

Construir novas linguagens regulares a partir de LR conhecidas

Provar propriedades

Construir algoritmos

Teorema: A Classe das Linguagens Regulares fechada para as seguintes

operaes:

Unio (de LR resulta em uma LR)

Concatenao (de LR resulta em uma LR)

Complemento (de LR resulta em uma LR)

Interseo (de LR resulta em uma LR)


Propriedades Fechamento sobre Linguagens Regulares



operaes: Unio, Concatenao; Complemento e Interseo


As provas referentes aos casos de unio e concatenao decorrem diretamente

da definio de expresso regular. Verifique porque.

No caso do complemento, suponha L uma LR sobre *. Ento existe um AFD

M = (, Q, , q0, F) tal que ACEITA(M) = L

A ideia inverter as condies de ACEITA / REJEITA de M para reconhecer

~L. No entanto, como M pode rejeitar por indefinio, necessrio M para

garantir que ele ir parar apenas aps ler toda a entrada.





Demonstrao: (cont.)

A ideia inverter as condies de ACEITA / REJEITA de M para reconhecer

~L. No entanto, como M pode rejeitar por indefinio, necessrio adaptar M

para garantir que ele ir parar apenas aps ler toda a entrada.

Para tanto, suficiente introduzir um novo estado final d, o qual ser destino de

todas as transies originalmente indefinidas. Alm disso, d dever conter um

ciclo para todos os smbolos do alfabeto (a fim de assegurar a leitura de toda a

entrada).

Assim, temos o novo AFD: MC = (, QC, C, q0, FC) tal que ACEITA(MC) = ~L






Assim, temos o novo AFD: MC = (, QC, C, q0, FC) tal que ACEITA(MC) = ~L

(suponhamos d Q)

QC = Q {d} e FC = QC F

C como , com as seguintes transies adicionais (para todo a e q Q):

C(q, a) = d, se (q,a) no estiver definida

C(d, a) = d

Assim, ACEITA(MC) = ~L, ou seja, ACEITA(MC)=REJEITA(M)






No caso da interseo, suponha L1 e L2 linguagens regulares. Como

consequncia da propriedade de DeMorgan para conjuntos, a seguinte

igualdade se verifica:

L1 L2 = ~(~L1 ~L2)

Como a classe das Linguagens Regulares fechada para as operaes de unio

e complemento, ela tambm fechada para a operao de interseo.



Exemplo de Complemento: Considere o AFD (com transies indefinidas):

M = ({a,b}, {q0, q1, q2, qf}, , q0,{qf}) abaixo:

Quem ACEITA(M) = L?

Seguindo a demonstrao do algoritmo anterior, o AFD:

MC= ({a,b}, {q0, q1, q2, qf, d}, C, q0,{q0, q1, q2, d}), ACEITA(MC) = ~L





Exemplo: Sejam as linguagens regulares sobre ={a, b}:

L1 = {aa / {a,b}*} GERA(aa(a+bb)*) = L1

L2 = {bb / {a,b}*} GERA((a+bb)*bb) = L2

L1L2={/(=aa ou =bb) e *} GERA((aa(a+b)*)+((a+b)*bb))

L1L2={aabb / *} GERA(aa(a+b)*bb)

* - L1 = GERA(((ab+b)(a+b)*) + )

L1L2={aabb / *} GERA(aa(a+b)*bb)

As linguagens geradas L1L2 , L1L2 , * - L1 , L1L2 so regulares.



O teorema a seguir assegura que existe um algoritmo para verificar se uma

linguagem regular representada por um autmato finito vazia, finita ou

infinita.

Teorema: Se L uma linguagem regular aceita por um autmato finito M=(,

Q, , q0, F) com n estados (a cardinalidade de Q n), ento L :

Vazia, se e somente se, M no aceita qualquer palavra w tal que |w| < n

Finita, se e somente se, M no aceita palavra alguma w tal que n |w| < 2n

Infinita, se e somente se, M aceita uma palavra w tal que n |w| < 2n


Propriedades LR Vazia, Finita ou Infinita





Demonstrao ():

Suponhamos que M aceita uma palavra w tal que n |w| < 2n.

Seja w tal palavra.

Ento pelo lema do bombeamento, w pode ser definida como w = uvz tal que:

|uv| n e |v| 1, sendo que: para todo i 0, uviz palavra de L.

Portanto, L infinita.






Demonstrao ():

Suponhamos que L seja infinita.

Ento obviamente existe w tal que n |w|. Assim:

1. Caso) |w| < 2n

Neste caso, n |w| < 2n, como queramos demonstrar.

2. Caso) |w| 2n

Suponhamos por absurdo que no existe palavra menor que 2n.

Ento suponhamos que w seja a menor palavra tal que |w| 2n






Demonstrao ( cont.1):

2. Caso) |w| 2n

Suponhamos por absurdo que no existe palavra menor que 2n.

Ento suponhamos que w seja a menor palavra tal que |w| 2n

Pelo lema do bombeamento, w = uvz tal que:

|uv| n e |v| 1, sendo que: para todo i 0, uviz palavra de L.

Em particular, 1 |v| n (pois |uv| n).

Por outro lado, uz palavra de L (basta tomar i = 0), o que um absurdo (como

veremos em seguida):






Demonstrao ( cont.2):

2. Caso) |w| 2n

Por outro lado, uz palavra de L (basta tomar i = 0), o que um absurdo, pois:

a) Se |uz| 2n, isso contradiz a suposio de que w a palavra de menor

comprimento tal que :|w| 2n (pois |w| = |uvz| |uz| 2n)

b) Se |uz| < 2n, ento n |uz| < 2n (pois |uvz| 2n e 1 |v| n) e, portanto,

isso contradiz a suposio de que no existe w tal que: n |w| < 2n






Demonstrao (por contraposio (p q) (~p ~q)):

Esta parte do teorema equivalente ao caso anterior:





Teorema: Se L uma linguagem regular aceita por um autmato finito M=(, Q, ,

q0, F) com n estados (a cardinalidade de Q n), ento L :


Demonstrao:

( por absurdo)

Suponhamos L uma linguagem regular vazia e que exista uma palavra w, |w| < n,

aceita por M.

Como w aceita por M, w L, o que absurdo pois L = , por hiptese.

Logo, se L vazia, ento M no aceita qualquer palavra w tal que |w| < n






Demonstrao: ( por absurdo)

Suponhamos que no exista w, |w| < n, aceita por M.

Suponhamos por absurdo que L no seja vazia. Logo existe w, w L.

Em funo da hiptese acima, |w| n. Pelo Lema do Bombeamento, w pode

ser particionada em uvz, tal que |uv| n, |v| 1 e qqs i 0, uviz L.

Em particular, para i = 0, uz L.

Considerando a nova palavra de L w=uz, repetimos a aplicao do lema do

bombeamento at que |w| = n. Ao aplicar mais uma vez o lema, temos que w

pode ser particionada em xyq, de tal forma que xq L, e |xq| n, o que um

absurdo, pois conflita com a hiptese. Logo L precisa ser vazia.



Teorema: Se L uma linguagem regular aceita por um autmato finito M=(, Q,

, q0, F) com n estados (a cardinalidade de Q n), ento L :




Exemplo de aplicao:

Considere o autmato M abaixo. Pelo teorema anterior, a linguagem por ele

aceita infinita se e somente se, o autmato aceitar uma palavra w tal que n |w|

< 2n.

Se tomarmos w=aabaa, 3 |w| < 6. Portanto, a linguagem aceita por M infinita.

Qual a linguagem aceita por M ?



O teorema a seguir assegura que existe um algoritmo para verificar se dois

autmatos finitos so equivalentes, ou seja, reconhecem a mesma linguagem.

Teorema: Se M1 e M2 so autmatos finitos, ento existe um algoritmo para

determinar se ACEITA(M1) = ACEITA(M2)

Demonstrao:

Sejam M1 e M2 autmatos finitos e L1=ACEITA(M1) e L2=ACEITA(M2)

Seja L3=(L1 ~L2) (~L1 L2). L3 Linguagem Regular.

Da Teoria de Conjuntos, L3= se, e somente se, L1=L2

Se L1=L2 ento L3 vazia

Do teorema anterior, existe um algoritmo para verificar se L3, LR, vazia.

Logo, existe um algoritmo para verificar se L1=L2.

Propriedades Igualdade de Linguagens Regulares


Em termos prticos, dadas duas Linguagens Regulares sobre {a,b}, L1 e L2, para

verificarmos se L1=L2, devemos verificar se L3=(L1 ~L2) (~L1 L2)=

Sejam

L1 = GERA((a+b)*) ~L1=

L2 = GERA(a*b*(a+b)*) ~L2=

L3=(L1 ~L2) (~L1 L2)=(L1 ) ( L2) = =

Portanto L1=L2

Propriedades Igualdade de Linguagens Regulares

Atividades Prticas

Lista de Exerccios III At o nmero 11 (Parte II)



Sees 3.9 e 3.10 Marcus Ramos

Seo 2.4 Papadimitriou



O tempo de processamento necessrio a um AFD para aceitar ou rejeitar uma

entrada diretamente proporcional ao tamanho da entrada, e no depende do

autmato considerado. Ou seja, qualquer AFD que reconhea a linguagem ter

a mesma eficincia. Entretanto, uma otimizao possvel a minimizao do

nmero de estados.

Dado um AFD qualquer, o objetivo da minimizao gerar o autmato finito

equivalente com o menor nmero de estados possvel, denominado Autmato

Finito Determinstico Mnimo, ou simplesmente, Autmato Finito Mnimo.

Um autmato finito mnimo nico (a menos de isomorfismos). Assim, dois

autmatos distintos que aceitam a mesma linguagem, ao serem minimizados,

geram o mesmo autmato finito mnimo, diferenciando-se, eventualmente, na

identificao dos estados. Nestes casos, os conjuntos de estados so isoformos.

Propriedades Minimizao de AFD


Definio: Seja M=(, Q, , q0, F) um AFD qualquer. Dois estados q e p de Q

so ditos Estados Equivalentes se, e somente se, para qualquer palavra w

pertencente a *, (q,w) e (p,w) resultam simultaneamente em estados finais,

ou no finais.

Portanto, o processamento de uma entrada qualquer a partir de estados

equivalentes resulta na mesma condio de aceita/rejeita.

Definio: Para uma dada linguagem regular L, o Autmato Finito Mnimo

um AFD Mm=(, Qm, m, q0m, Fm) tal que ACEITA(Mm) = L e que, para

qualquer outro AFD M=(, Q, , q0, F) tal que ACEITA(M)=L, ocorre que:

#Q #Qm



Pr-Requisitos do Algoritmo de Minimizao:

O autmato deve ser determinstico

Todos os estados do autmato devem ser estados alcanveis a partir do estado inicial. Ou seja, o autmato no pode ter estados inacessveis.

A funo programa deve ser total. Ou seja, a partir de qualquer estado, so previstas transies para todos os smbolos do alfabeto.

Algoritmo de Minimizao:

Passo 1: Construo da tabela relacionando os estados distintos

Passo 2: Marcao dos estados trivialmente no equivalentes (finais e no finais)

Passo 3: Marcao dos estados no equivalentes

Passo 4: Unificao dos estados equivalentes

Passo 5: Excluso dos estados inteis



Compreenso do Algoritmo de Minimizao a partir do exemplo abaixo:

Passo 1: Construo da tabela relacionando os estados distintos.

Cada par no ordenado ocorre somente uma vez.


q1

q2

q3

q4

q5

q0 q1 q2 q3 q4



Passo 2: Marcao dos estados trivialmente no equivalentes (finais e no finais)


Estados finais e no finais

no podem ser equivalentes

Marcar todos os pares do tipo

{estado final, estado no final}

q1 x

q2 x

q3 x

q4 x x x

q5 x x x

q0 q1 q2 q3 q4



Passo 3: Marcao dos estados no equivalentes.


Para cada par {qu, qv} no marcado e para cada

smbolo a do alfabeto, suponha que: (qu, a)=pu e

(qv, a)=pv . Assim:

Se pu=pv, ento so equivalentes para o smbolo a e o par no deve ser marcado.

Se pupv e o par (pu, pv) no est marcado, ento inclui {qu, qv} em uma lista a partir de {pu,pv} para

posterior anlise.

Se pupv e o par (pu, pv) est marcado, ento:

{qu, qv} no equivalente e deve ser marcado.

Se {qu, qv} encabea uma lista de pares, ento marcar todos os pares da lista (e,

recursivamente, se algum par da lista

encabea outra lista).

q1 x

q2 x

q3 x

q4 x x x

q5 x x x

q0 q1 q2 q3 q4



Processamento do Passo 3 no exemplo:

Marcao dos estados no equivalentes.


Anlise do par {q0, q4}:

(q0, a) = q2 (q0, b) = q1

(q4, a) = q3 (q4, b) = q2

Como {q2, q3} e {q1, q2} so no-marcados,

ento {q0, q4} includo nas listas encabeadas

por {q2, q3} e {q1, q2}

q1 x

q2 x

q3 x

q4 x x x

q5 x x x

q0 q1 q2 q3 q4

{q0, q4}

{q0, q4}







(q0, a) = q2 (q0, b) = q1

(q5, a) = q2 (q5, b) = q3

Como {q1, q3} no-marcado e como {q2, q2}

trivialmente equivalente, ento {q0, q5}

includo na lista encabeada por {q1, q3}

q1 x

q2 x

q3 x

q4 x x x

q5 x x x

q0 q1 q2 q3 q4

{q0, q4}

{q0, q4}

{q0, q5}







(q1, a) = q1 (q1, b) = q0

(q2, a) = q4 (q2, b) = q5

Como {q1, q4} marcado ento {q1, q2}

tambm marcado.

Como {q1, q2} encabea uma lista, o par {q0,

q4} tambm marcado

q1 x

q2 x

q3 x

q4 x x x

q5 x x x

q0 q1 q2 q3 q4

{q0, q4}

{q0, q4}

{q0, q5}

x

x

x

x







(q1, a) = q1 (q1, b) = q0

(q3, a) = q5 (q3, b) = q4

Como {q1, q5} e {q0, q4} so marcados ento

{q1, q3} tambm marcado.

Como {q1, q3} encabea uma lista, o par {q0,

q5} tambm marcado

q1 x

q2 x

q3 x

q4 x x x

q5 x x x

q0 q1 q2 q3 q4 {q0, q5}

x

x

x

x

x

x







(q2, a) = q4 (q2, b) = q5

(q3, a) = q5 (q3, b) = q4

Como {q4, q5} no marcado ento {q2, q3}

includo na lista encabeada por {q4, q5} q1 x

q2 x

q3 x

q4 x x x

q5 x x x

q0 q1 q2 q3 q4

{q2, q3}

x

x

x

x







(q4, a) = q3 (q4, b) = q2

(q5, a) = q2 (q5, b) = q3

Como {q2, q3} no marcado, ento {q4, q5}

includo na lista encabeada por {q2, q3}. q1 x

q2 x

q3 x

q4 x x x

q5 x x x

q0 q1 q2 q3 q4

{q4, q5}

{q2, q3}



Passo 4: Unificao dos estados equivalentes.


Os estados de pares no marcados so equivalentes e

podem ser unificados como segue:

A equivalncia dos estados transitiva.

Pares de estados no finais equivalentes podem ser unificados como um nico estado no final.

Pares de estados finais equivalentes podem ser unificados como um nico estado final.

x

x

x

x

q1 x

q2 x

q3 x

q4 x x x

q5 x x x

q0 q1 q2 q3 q4

{q2, q3}

{q4, q5}



Passo 5: Excluso de estados inteis.


Um estado q dito estado intil se no final e a

partir de q no possvel atingir um estado final.

Todas as transies com origem ou destino em um

estado intil so excludas.

No exemplo, o algoritmo de minimizao no gerou

estados inteis.

x

x

x

x

q1 x

q2 x

q3 x

q4 x x x

q5 x x x

q0 q1 q2 q3 q4

{q2, q3}

{q4, q5}


Exerccio: Minimize o autmato abaixo:



Teorema: O autmato finito determinstico mnimo de uma linguagem

nico, a menos de um isomorfismo.

Assim, dois autmatos distintos que aceitam a mesma linguagem, ao

serem minimizados, geram o mesmo autmato finito mnimo,

diferenciando-se, eventualmente, na identificao dos estados.

Como um autmato finito mnimo nico, a menos de um isomorfismo,

usual ser referido como o (e no como um) autmato finito mnimo.

Propriedades Unicidade do Autmato Finito Mnimo

Atividades Prticas

Lista de Exerccios II Exerccios 12 e 13 (Parte II)



Sees 3.7 a 3.12 Marcus Ramos

Sees 2.4 a 2.6 Papadimitriou

Cap. 4 Hopcroft & Ullman



Autmato Finito com Sada


O conceito bsico de autmato finito possui aplicaes prticas restritas, pois

a informao de sada limitada lgica binria aceita/rejeita.

Sem alterar a classe de linguagens reconhecidas, possvel estender a

definio de AF para incluir a gerao de uma palavra de sada.

As sadas podem ser associadas:

s transies (Mquina de Mealy)

aos estados (Mquina de Moore)

Em ambas as mquinas, a sada no pode ser lida (usada como memria

auxiliar).



Nas mquinas de Mealy e de Moore:

A sada definida sobre um alfabeto especial (alfabeto de sada);

A sada armazenada em uma fita de sada independente da de entrada;

A cabea da fita de sada move uma clula para a direita a cada smbolo gravado;

O resultado do processamento do AF o seu estado final (condio de aceita/rejeita) e a informao contida na fita de sada.

As mquinas de Mealy e de Moore so modificaes sobre autmatos finitos

determinsticos.

Ambas as mquinas so equivalentes em termos de capacidade de

processamento.



Definio: Uma Mquina de Mealy um AFD=(,Q,,q0,F,) com sada

associada s transies, onde:




: Q x Q x *



um alfabeto de smbolos de sada (que pode ser igual a )

A funo programa pode ser representada como um diagrama como nos AF

adicionando-se na etiqueta de cada transio, a sada associada, quando

diferente da palavra vazia.

Autmato Finito com Sada Mquina de Mealy


A computao em uma Mquina de Mealy, para uma palavra de entrada w,

consiste na sucessiva aplicao da funo programa para cada smbolo de w

(da esquerda para a direita) at ocorrer uma condio de parada.

A palavra vazia como sada da funo programa indica que nenhuma

gravao realizada, no movimentando a cabea da fita de sada.

Se todas as transies geram sada vazia, ento a Mquina de Mealy processa

como se fosse um autmato finito.



Exemplo: Dilogo entre Programa e Usurio. Simbologia adotada:

entrada fornecida pelo usurio (em um teclado, por ex)

... sada gerada pelo programa (em um vdeo, por ex.)

[...] ao interna do programa, sem comunicao com o usurio

(...) resultado de ao interna ao programa (usado como entrada no diagrama)

A Mquina de Mealy:

M=(, {q0, q1,... q8, qf}, , q0, {qf}, )

e so conjuntos de smbolos

(palavras em Portugus) de entrada e sada

vlidos no dilogo.



Definio: Uma Mquina de Moore um AFD=(,Q,,q0,F,,S) com sada

associada aos estados, onde:



uma funo parcial denominada funo programa : Q x Q



um alfabeto de smbolos de sada (que pode ser igual a )

S uma funo total denominada funo de sada S: Q *

A funo programa pode ser representada como um diagrama como nos AF

adicionando-se na etiqueta de cada estado, a sada associada, quando diferente

da palavra vazia.

Autmato Finito com Sada Mquina de Moore


Exemplo: Hiperdocumento. A Mquina de Moore: M=(, Q, , q0, {qf}, , S) = {prxima, exerccio, anterior, resumos, sada}

= {A,B,C,D,E,F,G,H,I,J,K,L,M},

onde cada letra, corresponde ao seguinte fragmento

de hipertexto na base de dados:

A Introduo ao AF; B Definio de AFD

C Exemplo de AFD; D Exerccio sobre AFD

E Introduo aos AF com Sada

F Definio de Mquina de Mealy

G Exemplo de Mquina de Mealy

H Exerccio sobre Mquina de Mealy

I Definio de Mquina de Moore

J Exemplo de Mquina de Moore

K Exerccio sobre Mquina de Moore

L Concluses; M Fim

Observaes:

Fragmentos so concatenados compondo pginas

Reuso de fragmentos em mais de uma pgina

Alterao de fragmento no BD leva atualizao no AF

Smbolos do alfabeto de entrada so rtulos de ponteiros

Autmato Finito com Sada Mquina de Moore


A estruturao de um hipertexto/hipermdia como um AF com sada possui as

seguintes vantagens:

Alto grau de modularizao dos recursos que constituem a base de dados.

Facilidade de reuso desses recursos.

Independncia da estrutura navegacional (funo de transio) do contedo das pginas. Assim, modificaes na estrutura navegacional no influem no

contedo das pginas e vice-versa.

Facilidade de criao e manuteno de hipertextos/hipermdia.

Interface grfica simples e direta (decorrente da representao de um AF como um diagrama).

Facilidade de implementao (lembrando a simplicidade de implementao de um simulador de AF).

Autmato Finito com Sada Aplicao em Hipertexto


A equivalncia dos dois modelos de mquina de autmato finito com sada no

vlida para a entrada vazia. Neste caso:

Mquina de Moore gera a palavra correspondente ao estado inicial

Mquina de Mealy no gera qualquer sada, pois no executa transio alguma

Teorema: Toda Mquina de Moore pode ser simulada por uma Mquina de Mealy


Teorema: Toda Mquina de Mealy pode ser simulada por uma Mquina de Moore


Autmato Finito com Sada Equivalncia de Mquinas

Atividades Prticas

Lista de Exerccios III Completar




Seo 3.8 Marcus Ramos

Documents

04 - Linguagens Regulares