69
C ít l 3 Capítulo 3 Expressões Regulares Expressões Regulares, Linguagens Regulares e guage s egu a es e Gramáticas Regulares 3.1. Expressões Regulares (RE) 3.2. Relação entre ER e Linguagens Regulares (LR) 3.3. Gramáticas Regulares (GR) 3.4. Síntese das equivalências © ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 123

Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Embed Size (px)

Citation preview

Page 1: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

C ít l 3Capítulo 3

Expressões RegularesExpressões Regulares, Linguagens Regulares e guage s egu a es eGramáticas Regularesg

3.1. Expressões Regulares (RE)3.2. Relação entre ER e Linguagens Regulares (LR)3.3. Gramáticas Regulares (GR)3.4. Síntese das equivalências

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 123

Page 2: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3 1 Expresssões regulares (RE)3.1. Expresssões regulares (RE)

uma forma de descrever linguagens regulares

desenvolvidas a partir de :

- os símbolos do alfabeto

d d- operadores de união : ou +

t ãconcatenação: •fecho-estrela : *

- parênteses

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 124

Page 3: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Exemplo 1

={a, b, c, ..., z}

L = {a} é definida pela expressão regular :

a

L = {d, m, u }, é definida pela expressão regular:

d m uou

d+m+u.

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 125

Page 4: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Exemplo 2

qual é a linguagem definida pela expressão regular (a+bc)* ?

(a+bc)* = (a+bc)0 (a+bc)1 (a+bc)2 ...

- (a+bc)0 : - (a+bc)1 : a, bc

2- (a+bc)2 = (a+bc) (a+bc) : aa, abc, bca, bcbc- (a+bc)3 : aaa, aabc, abcbc, abca, bcbcbc, ....- ......

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 126

Page 5: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

E l 3Exemplo 3

= {a, b, c}

(a + b)* :

d i b bb b b bb bbb b bcadeias , a, b, aa, bb, ab, ba, aaa, abbaa, bbbaabab, …... qualquer cadeia com a’s e b’s

a* b* :

cadeias an bm , n,m 0 ou seja , a,b, aab, aabb, abb,bbb aabbbbbbb, aabbbb,...

(c+) : cadeia c© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 127

(c+) : cadeia c

Page 6: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3.1.1. Definição formal, recursiva, de expressão regularç , , p g

Definição 3.1. Considere-se um dado alfabeto .ç

1. expressões regulares a ( para a )

p gprimitivas

2 Se r e r são expressões regulares também o serão2. Se r1 e r2 são expressões regulares, também o serão

i) r1+r2 (união)

ii) r1 r2, (concatenação)

iii) r1* , r2* (fecho-estrela)

iv) (r1), (r2) (parênteses)

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 128

iv) (r1), (r2) (parênteses)

Page 7: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3. Uma cadeia é uma expressão regular se e só se puder ser derivada

- a partir das expressões regulares primitivas e

- pela aplicação de um número finito de vezes das dregras de 2.

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 129

Page 8: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

ExemplosExemplos

= {0 1} {0,1}

01* = {0, 01, 011, 0111, …..}

(01*)(01) = {001, 0101, 01101, 011101, …..}

(0+1)* = {, 0, 1, 00, 01, 10, 11, …..}, todas as cadeias de “0” e “1”

(0+1)*00(0+1)* = {00, 1001, …..}, todas as cadeias de 0 e 1 contendo “00”

= {a b c} = {a,b,c}

(a+bc)*(c+) é expressão regular ?

(a + c + ) é expressão regular ?

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 130

Page 9: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Exemplos :Exemplos :

={0,1} {0,1}

(1+10)* = todas as cadeias iniciadas por “1” e não contendo pares de zeros “00”

(0+1)*011 = todas as cadeias que terminam com “011”

0*1* = todas as cadeias que não têm um “0” depois de “1”

00*11* = todas as cadeias com pelo menos um “0” e um “1”, e nenhum “0” depois de “1”

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 131

Page 10: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3 1 2 Regras algébricas para expressões regulares

R i

3.1.2. Regras algébricas para expressões regulares

Regras comutativas

Regras associativas

Regras distributivas

Identidades e anuladores

Regras de fecho

Hopcroft, Motwani & Ullman, 114-121

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 132

Page 11: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3 1 2 1 Regras comutativas e associativas3.1.2.1 Regras comutativas e associativas

Sejam L, M e N expressões regulares. Então:

L + M = M + L comutatividade da união

(L + M) + N = L + (M + N) associatividade da união( ) ( ) (LM)N = L(MN) associatividade da

concatenação

LM ML ?? t ti id d d LM = ML ?? comutatividade da concatenação

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 133

Page 12: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3 1 2 2 Regras distributivas

L(M + N) = LM + LN distributividade à esquerda da

3.1.2.2. Regras distributivas

L(M + N) = LM + LN distributividade à esquerda da concatenação em relação à união

(M + N)L = ML + NL distributividade à direita da concatenação em relação à uniãoconcatenação em relação à união

(MN) + L = (M + L)(N + L) ???

L + (MN) = (L + M)(L + N) ???

( ) ( )( )

L + (MN) (L + M)(L + N) ???

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 134

Page 13: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3 1 2 3 Identidades e anuladores (zeros)3.1.2.3. Identidades e anuladores (zeros)

é a identidade para a união + L = L + = L

é a identidade para a concatenação: é a identidade para a concatenação: L = L = L

é o anulador para a concatenação L = L =

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 135

Page 14: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3 1 2 4 Regras do fecho estrela3.1.2.4. Regras do fecho-estrela

(L*)* = L*

L+ = LL* = L*L

L* = L+ +

* * =

* = * =

( L+M )* = (L* M *)* ( L+M ) (L M )

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 136

Page 15: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3 1 2 5 Outras regras algébricas

P l éb i l l

3.1.2.5. Outras regras algébricas

Para provar uma regra algébrica qualquer, por exemploL + ML = (L + M)L

tem que se provar que qualquer cadeia gerada pela RE da esquerda é também gerada pela RE da direita.Para provar que é falsa, basta dar um contra exemplo.

Para auxiliar a prova podem-se substituir os símbolos das RE por caracteres de um alfabeto no caso por exemploRE por caracteres de um alfabeto, no caso por exemplo

(a+ba) = (a + b)af il ê f lque facilmente se vê ser falso.

ver Hopcroft, Motwani & Ullman, 118-119

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 137

p , ,

Page 16: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3 1 3 Li i d ã l3.1.3. Linguagem associada a uma expressão regular

D fi i ã 3 2 S é ã l L( ) dDefinição 3.2. Se r é uma expressão regular, L(r) denota a linguagem associada com r, e é definida pelas regras:

1. r = é uma expressão regular, o conjunto vazio

2. r = é uma expressão regular, o conjunto {}

3. para todo o a , r = a é uma expressão regular, {a}

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 138

Page 17: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Se r1 e r2 são expressões regulares, então1 2 p g ,

4. L(r1+r2) = L(r1) L(r2)

5. L(r1r2) = L(r1) L(r2) , concatenação de L(r1) com L(r2)

6. L((r1)) = L(r1)

7. L(r1*) = (L(r1))*

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 139

Page 18: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

As regras 4 a 7 usam-se para reduzir recursivamente uma linguagem L a expressões mais simples.

As regras 1 a 3 são as condições terminais para esta recursão.

P ifi l li d Para se verificar qual a linguagem que corresponde a uma dada expressão regular, aplicam-se aquelas regras tantas

t á ivezes quantas as necessárias.

A precedência dos operadores é a seguinte A precedência dos operadores é a seguinte1º- fecho- estrela (*),2º concatenação ()2 - concatenação (),3º- (+) união

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 140

Page 19: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Exemplos:

i) = {x}

L( *) { } L( +)L(xx*) ={x, xx, xxx,...}= L(x+)

L(x(xx)*) ={x, xxx, xxxxx,..} =L(xímpar)

ii) = { a, b, c }

L((a+c)b*) = L(a+c)L(b*) = (L(a) L(c)) (L(b))* =

= { a c } { b bb bbb }= { a, c } { , b, bb, bbb, … }

= { a, c, ab, cb, abb, cbb, abbb,..}

iii) { b}

L(c+) = { c }

iii) ={a, b}L((a+b).(a+b).(a+b)) = L(a+b) L(a+b) L(a+b) = {a,b} {a,b} {a,b}

= {aaa, aba, abb, baa, bba,..}

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 141

{ , , , , , }

Page 20: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Notas:

(a+b)*= (a+b)*+(a+b)*

(a+b)* = (a+b)*(a+b)*

(a+b)* = a(a+b)*+b(a+b)*+( ) ( ) ( )

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 142

Page 21: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

= {0 1}

A) ã l li

= {0,1}

A) escrever a expressão regular para a linguagem

L { t i ú í d }L ={w : w termina com um número ímpar de zeros }

r = (0+1)*10(00)* + 0(00)*

B) Qual é a linguagem representada pela expressão regular:

i) (1+01+001)*(+0+00)

ii) ((0+1)(0+1))*+((0+1)(0+1)(0+1))*

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 143

Page 22: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Exemplo de linguagens complementares

= {0,1} {0,1}

Encontrar uma expressão regular para as linguagensp g p g g

i) L(r) = {w * : w tem pelo menos um par de zeros consecutivos }

Exemplo 3.5, p. 75 Linz

ii) L (r) = {w * : w não tem qualquer par de zeros consecutivos }

Exemplo 3.6 , p. 75 Linz

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 144

Page 23: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3 1 4 Equivalência de expressões regulares3.1.4. Equivalência de expressões regulares

Duas expressões regulares são equivalentes se elas denotam a mesma linguagem.

Q d i lifi l b ê Quando se simplifica uma expressão regular, obtêm-se sucessivamente expressões regulares equivalentes.

P d d li i t l t ú Para uma dada linguagem existe geralmente um número ilimitado de expressões regulares equivalentes.

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 145

Page 24: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3 2 Relação entre expressões regulares e linguagens regulares3.2. Relação entre expressões regulares e linguagens regulares

Para toda a linguagem regular existe uma expressão regular

Para toda a expressão regular existe uma linguagem regular.

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 146

Page 25: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3.2.1 Determinação de linguagens regulares a partir de3.2.1 Determinação de linguagens regulares a partir de expressões regulares

Uma linguagem é regular se for aceite por um DFA ou um NFA

Se se construir um NFA a partir de uma expressão regular r qualquer r denotará uma linguagem regular L(r)qualquer, r denotará uma linguagem regular L(r).

Para o provar recorre-se à definição recursiva de L(r)Para o provar, recorre se à definição recursiva de L(r),

aplicando as regras 1-3 para definir os elementos básicos e aplicando as regras 1 3 para definir os elementos básicos e

as regras 4-7 para as composições de elementos básicos.g p p ç

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 147

Page 26: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

1º definem-se NFA para as expressões regulares primitivas

i) NFA aceitador de L1= : q qr= q0 q1

ii) NFA aceitador de L2= {}r= q0 q1

iii) NFA aceitador de L3= {a} r=a

q0 q1a

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 148

Page 27: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

2º Ad i ã l2º Admitamos agora que temos uma expressão regular r e que o NFA que aceira L(r) é representado por M (r)

M (r)

q0 qF

com o estado inicial q e o estado final q Note se que qualquercom o estado inicial q0 e o estado final qF. Note-se que qualquer NFA pode ser representado com um só estado final.

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 149

Page 28: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3º Temos NFA’s M(r ) e M(r ) que aceitam as linguagens3 Temos NFA s M(r1) e M(r2) que aceitam as linguagens L(r1) e L(r2) .

iv) L(r1+r2)

M (r1)

iv) L(r1+r2)

M (r1)

q0 qf

M (r2)

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 150

Page 29: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

v) L (r1 r2 )) ( 1 2 )

M (r1) M (r2)

q0 qf

q0 qf

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 151

Page 30: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

vi) L(r1*)

M (r1) M (r1)q0

qf

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 152

Page 31: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Usando os autómatos anteriores como elementos construtivos é possível construir um NFA para qualquer expressão regular.possível construir um NFA para qualquer expressão regular.

Teorema 3.1. Se r é uma expressão regular, existe algum autómato finito não-determinísticoexiste algum autómato finito não-determinístico que aceita L(r).

Logo L(r) é uma linguagem regular.Logo L(r) é uma linguagem regular.

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 153

Page 32: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Exemplo

r = 1*

Exemplo

r = 1*

1

1 1 0 11

q

1

0

0,1

DFAq0 q0DFA

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 154

Page 33: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3.3.2. Determinação de expressões regulares a partir de3.3.2. Determinação de expressões regulares a partir de linguagens regulares

A toda a linguagem regular se pode associar um NFA e t t f d t i õportanto um grafo de transições.

P ti d d t d t d i h Partindo do estado q0, procuram-se todos os caminhos possíveis até ao estado final e as suas etiquetas.

É possível depois encontrar uma expressão regular que gere todas essas etiquetastodas essas etiquetas.

Para facilitar esta operação usam-se os grafos de transição Para facilitar esta operação, usam se os grafos de transição generalizados.

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 155

Page 34: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Grafos de transição generalizados:

as arestas podem ser etiquetadas por expressões regulares,

ç g

a etiqueta de um caminho desde o estado inicial até a um t d fi l é t ã d ti t d t destado final é a concatenação das etiquetas das arestas do

caminho, i.e, a concatenação de expressões regulares e portanto é uma expressão regularportanto é uma expressão regular,

as cadeias expressas por essa expressão regular são um as cadeias expressas por essa expressão regular são um subconjunto da linguagem aceite pelo grafo de transição generalizadogeneralizado,

a linguagem total será a união de todos os subconjuntos a linguagem total será a união de todos os subconjuntos gerados deste modo.

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 156

Page 35: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

NFANFA

grafos de transição generalizados

expressões regulares

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 157

Page 36: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

O f d NFA d id f li dO grafo de um NFA pode considerar-se um grafo generalizado :

Uma aresta etiquetada com um único carácter a interpreta-se como etiquetada pela expressão regular a,como etiquetada pela expressão regular a,

Uma aresta etiquetada por vários caracteres a,b, ..., interpreta-q p , , , pse como etiquetada pela expressão regular a + b + ....,

Pode-se assim afirmar que para toda a linguagem regular existe um grafo de transição generalizado que a aceita,

Por outro lado toda a linguagem aceite por um grafo generalizado é uma linguagem regular.

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 158

Page 37: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

G f i l i lifi ã d fGrafos equivalentes – simplificação de grafos

Dois grafos são equivalentes se aceitam a mesma linguagemDois grafos são equivalentes se aceitam a mesma linguagem

eecd

qiq qj

a b

a, b, c, d e e são expressões regulares quaisquer

Pode-se eliminar o estado q ??

, , , p g q q

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 159

Page 38: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Sim, desde que não se altere a linguagem ...

ecd

, q g g

cd

q qjqiq qj

a b

qi qi : ae*d

qi qj : ae*b

qj qi : ce*dqj qi : ce d

qj qj : ce*b

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 160

Page 39: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

ce*bce*dae*d ce d ae d

qi qj

ae*b

qj

ae b

qi qi : ae*dqi qj : ae*bqj qj : ce*bqj qj : ce bqj qi : ce*d

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 161

Page 40: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Este procedimento assegura que a linguagem aceite não é p g q g galterada

Num grafo com mais estados mais complicadoNum grafo com mais estados, mais complicado,

este é feito para todos os pares (q q ) em Q {q} antes- este é feito para todos os pares (qi , qj ) em Q – {q} antes de se remover q (i.e, todos os pares que estejam ligados a q).

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 162

Page 41: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

T 3 2Teorema 3.2.Seja L uma linguagem regular. Então existe j g g guma expressão regular r tal que L = L (r).

Demonstração:

existe um NFA que aceita L, com um só estado final e tal que o estado inicial q0 não é estado final. Pode-se interpretar como um grafo de transição

li dgeneralizado

aplica-se-lhe o procedimento anterior de eliminar vértices q, até que se p p q, qfique apenas com o estado inicial e o estado final, obtendo-se o grafo da figura seguinte

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 163

Page 42: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

r4r1

r3r3

q0 qfq0 qf

r2

ã õ lr1 , r2 , r3 , r4 são expressões regulares

A linguagem aceite pelo grafo éA linguagem aceite pelo grafo é

* ( + * ) *r=r1* r2 ( r4 + r3 r1* r2) *

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 164

Page 43: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

N d b f d i i i l bé éNo caso de se obter um grafo em que o estado inicial também é estado final,

r4r1

rr3

q qq0 q

r2

a expressão regular é

r = (r1* + (r2 r4* r3 ))*

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 165

Page 44: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

d fr4r1

... de facto

r3

qq0 qf

r2

li i

q q : (r * + (r r * r ))*

elimine-se q:

qf qf : (r1* + (r2 r4* r3 ))*

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 166

Page 45: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

(r1* + (r2 r4* r3 ))*(r1 + (r2 r4 r3 ))

q qf r = (r4+ ))* =r4*q0qf ( 4 )) 4

= (r1* + (r2 r4* r3 ))*

r4r1

r3

q0 qf r = r1* r2 ( r4 + r3 r1* r2) *

r2

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 167

Page 46: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Exemplo 0Introduz-se um estado inicial,

Exemplo 0

A

0

Aq0

10

1

C11

0

1

C1

0B

1

0

B1

011*0

A

11*0

Bq0

r4

0 Aq0

r4 = ( 0 + (11*0)(11*0)*0 )*Alicando agora o resultado geral r=(r4 + )* =r4*= r4

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 168

Page 47: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3.3. Gramáticas Regulares3.3. Gramáticas Regulares

Uma gramática G = (VT S P)

linear à direita se todas as

Uma gramática G = (V,T,S,P)

linear à esquerda se todas as linear à direita se todas as suas produções são da forma

linear à esquerda se todas as suas produções têm a forma

A xB,A x

A Bx,A x A x

A B V conjunto das variáveis x T* T conjunto dos símbolos terminais

A x

A, B V, conjunto das variáveis, x T , T conjunto dos símbolos terminais

Uma gramática diz se regular se ela é ou linear à esquerda ouUma gramática diz-se regular se ela é ou linear à esquerda ou linear à direita

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 169

Page 48: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

E l 1Exemplo 1

G ({S} { b} S P ) li à di itG1= ({S}, {a,b}, S, P1) , linear à direita

P : S abS | aP1 : S abS | a

Como derivar ababa ?Como derivar ababa ?

S abS ababS ababaS abS ababS ababa

Aplicando P1 sucessivamente obtém-se a linguagemAplicando P1 sucessivamente obtém se a linguagem (regular) denotada pela expressão regular

r=(ab)*a

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 170

Page 49: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Exemplo 2p

G2 =({S,A,B}, {a,b}, S, P2 } , linear à esquerda

P2 : S Aab,A Aab | BB a

Como derivar aababab ?

S Aab Aabab Aababab Bababab aababab

Aplicando P2 sucessivamente conclui-se que esta gramática gera a linguagem regular definida pela expressão regularg g g p p g

r=aab(ab)*

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 171

Page 50: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

E l d á i ã lExemplos de gramáticas não-regulares

G ({S A B} { b} S P }G3 =({S,A,B}, {a,b}, S, P }

P: S A (i)P: S A , (i)A aB | , (ii)B Ab (iii)B Ab (iii)

tem umas produções lineares à direita (i ii) tem umas produções lineares à direita (i, ii) e outras lineares à esquerda (i, iii) e por isso é linear mas não regular e por isso é linear mas não regular

Nem todas as lineares são regulares.Nem todas as lineares são regulares.

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 172

Page 51: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3.3.2. Determinação das linguagens regulares a partir das gramáticas lineares à direitagramáticas lineares à direita.

Pode-se construir um NFA que imita as derivações daPode-se construir um NFA que imita as derivações da gramática linear à direita.

Uma forma sentencial tem uma e uma só variável que é o símbolo mais à direita.símbolo mais à direita.

A produção D dE resulta em p ç

ab...cD ab...cdE

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 173

Page 52: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

b D b dEab...cD ab...cdE

Um NFA pode imitar esta produção se tiver um estado D e um estado E e entre os dois uma aresta etiquetada por d :um estado E e entre os dois uma aresta etiquetada por d :

dD EdD

Estados do autómato : variáveis das formas sentenciaisEstados do autómato : variáveis das formas sentenciais.

A parte da cadeia ab...c já processada foi obtida por construções semelhantes anteriores.

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 174

Page 53: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Teorema 3.3.

S j G (VT S P) á i li àSeja G = (V,T,S,P) uma gramática linear à direita. Então L(G) é uma linguagem regular.( ) g g g

Para o demonstrar constrói-se um NFA que imite as produções da gramática.

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 175

Page 54: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

V = {V0,, V1 , ..., Vn } o conjunto das variáveis da gramática{ 0 1 n } j gS = V0

P : V0 v1Vi0 1 iVi v2Vj

…Vn vl

vi: sub-cadeias (um ou mais símbolos).

S é d i (G) d áSe w é uma cadeia em L(G), a sua produção será

V VV0 v1Vi v1v2Vj....

v1v2...vkVn v v v v = w

*

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 176

v1v2...vkvl = w

Page 55: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

O NFA imita cada derivação “consumindo” um v de O NFA imita cada derivação consumindo um v de cada vez;

V0, Vi, Vj, ..., Vn são estados do autómato;

existem outros entre eles quando os v’s são cadeias com existem outros entre eles quando os v s são cadeias com mais de um carácter;

é preciso acrescentar o estado final.p

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 177

Page 56: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

P d ãPara a produção:

V VVi a1a2a3...amVj

o NFA terá um caminho ligando V a V ou seja *(V V )o NFA terá um caminho ligando Vi a Vj, ou seja *(Vi, Vj) existe e será definida por

* (V a a a a ) = V* (Vi , a1a2a3...am) = Vj

Via1 am Vj

a2

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 178

Page 57: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Para uma produção

Vi a1a2a3...am

a função de transição generalizada será o estado final Vf.

* (Vi, a1a2a3...am) = Vf

Via1

am Vfa2

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 179

Page 58: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Exemplo:

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

P: S aA | aB ,A bB | b

a a b

A bB | b ,B aA | bB . B

Derivação da cadeia ababab : b

S aA abB abaA ababBababaA ababab

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 180

Page 59: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3.3.3. Determinação das gramáticas lineares à direita a partirç g pdas linguagens regulares

Prova-se que toda a linguagem regular pode ser gerada poruma gramática linear à direita:

constrói-se o DFA para a linguagem

os estados do DFA transformam-se nas variáveis da gramática

os símbolos produtores das transições são os terminais das produções.

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 181

Page 60: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Teorema 3 4 Se L é uma linguagem regular no alfabeto entãoTeorema 3.4. Se L é uma linguagem regular no alfabeto , então existe uma gramática linear à direita G = (V, , S ,P ) tal que

L=L (G)L L (G).

Demonstração com DFA:

Seja M = (Q, , , q0 ,F ) o DFA que aceita L, comQ= {q0 ,q1,...q }Q {q0 ,q1,...qn } ={a1, a2, ..., am}

i li di i ( ) l Construa-se a gramática linear à direita G = (V, , S, P), tal queV= {q0 ,q1,...qn }S = q0S q0

Para cada transição (qi, aj) = qk no DFA M , introduz-e em Pda produção qi ajqk

Se qk faz parte de F, acrescenta-se a P a produção qk

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 182

Se qk faz parte de F, acrescenta se a P a produção qk

Page 61: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Demonstração com DFA:Demonstração com DFA:

Linguagem

DFA

Gramática LDGramática LD

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 183

Page 62: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Demonstração com NFA:

Seja M = (Q, , , q0 ,F ) o NFA que aceita L, comQ= {q0 ,q1,...q }Q {q0 ,q1,...qn } ={a1, a2, ..., am}

C á i li à di i G ( S ) l Construa-se a gramática linear à direita G = (V, , S, P), tal queV= {q0 ,q1,...qn }S = q0S q0

Para cada transição (qi, aj) = qk no NFA M , introduz-e em Pda produção qi ajqk

Se existir também (qi, aj) = ql , introduz-e em P a produçãoqi ajql ou seja qi ajqk | ajqlqi ajql ,ou seja qi ajqk | ajql

Para cada transição (qi, ) = qk no NFA M , introduz-e em Pda produção qi qk

Se qk faz parte de F, acrescenta-se a P a produção qk

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 184

Se qk faz parte de F, acrescenta se a P a produção qk

Page 63: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Demonstração com NFA:Demonstração com NFA:

Linguagem

NFA

Gramática LDGramática LD

Diferente da que se obtém a partir q pdo DFA, mas equivalente.

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 185

Page 64: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Exemplop

Construir a gramática linear à direita para a linguagem L(aab*a)

bO NFA respectivo é

a a a

b

qfq0 q1 q2 qfq0 q1 q2

T i õ M P d õ GTransições em M Produções em G

(q0, a)={q1} q0 aq1

(q1, a)={q2} q1 aq2

(q2,b)={q2} q2 bq2(q2 ) {q2} q2 q2

(q2, a)={qf} q2 aqf

qf F qf

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 186

qf qf

Page 65: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Exemplo:Construir a gramática linear à direita para a linguagemL(aab*a+aa+ab*a)

b a

a a a q4q1 q2 q3

b

a a

b

qq qq0

qfa q7q5 q6

T i õ M P d õ GTransições em M Produções em G

(q0, )={q1, q5} q0 q1| q5

q4 qf

(q5, a)={q6} q5 aq6

(q4, )={qf}

(q1, a)={q2} q1 aq2

(q2,a)={q3, q4} q2 aq3| aq4

(q6, b)={q6} q6 bq6

(q6,a)={q7} q6 aq7(q2 ) {q3 q4} q2 q3| q4

(q3, a)={q4} q3 aq4

q3 bq3 (q3, b)={q3}

(q6 ) {q7} q6 q7

(q7, )={qf} q7 qf

qf F qf

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 187

q3 q3 qf qf

Page 66: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3.3.4. Equivalência entre linguagens regulares e gramáticas regulares

P á i li à d bé d iPara as gramáticas lineares à esquerda também se pode enunciar o teorema de equivalência

Teorema 3.5. A linguagem L é regular se e só se existir uma gramática linear à esquerda G tal que L=L(G)gramática linear à esquerda G tal que L=L(G).

Podemos finalmente enunciar o teorema de equivalência entre linguagens regulares e gramáticas regulares:

Teorema 3 6 Uma linguagem L é regular se e só se existir umaTeorema 3.6. Uma linguagem L é regular se e só se existir uma gramática regular G tal que L=L(G).

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 188

Page 67: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

3 4 Síntese das equivalências

Expressões regulares (ER)

3.4. Síntese das equivalências

Expressões regulares (ER)

Teorema TeoremaTeorema3.1

Teorema3.2

DFA ou NFA

TeoremaTeorema

Teorema3.3

3.4

Gramáticas regulares (GR)

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 189

Page 68: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Teorema 3.1. ER NFA

Teorema 3.2 LR ER (LR DFA GTG ER)

Teorema 3.3 Gramáticas lineares à direita LR

( Gramáticas lineares à direita NFA LR )

Teorema 3.4 LR Gramáticas Lineares à direita(LR DFA Gramáticas lineares à direita)

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 190

Page 69: Cítl3Capítulo 3 Expressões RegularesExpressões Regulares ...cbarrico/Disciplinas/TeoriaComputacao... · Cítl3Capítulo 3 Expressões RegularesExpressões Regulares, Linguageguage

Bibliografia

An Introduction to Formal Languages and Automata Peter Linz 3rdAn Introduction to Formal Languages and Automata, Peter Linz, 3rd Ed., Jones and Bartelett Computer Science, 2001

Introduction to Automata Theory, Languages and Computation, 2nd Ed., John Hopcroft, Rajeev Motwani, Jeffrey Ullman, Addi W l 2001Addison Wesley, 2001.

Elements for the Theory of Computation, Harry Lewis and Christos P di it i 2 d Ed P ti H ll 1998Papadimitriou, 2nd Ed., Prentice Hall, 1998.

Introduction to the Theory of Computation, Michael Sipser, PWS P bli hi C 1997Publishing Co, 1997.

© ADC/TCI/Cap.3/2009-10/LEI/DEIFCTUC 191