Draft-v

0.23Linguagens regulares e expressões

regulares

Uma classe de conjuntos é fechada por uma operação se o resultado da operaçãode conjuntos dessa classe for ainda um elemento dessa classe.

Definição 3.1 (Linguagens regulares) Considerando um alfabeto ⌃, a classedas linguagens regulares (LR) é a menor classe que contém ;, {"} e {a}

(para todo o a 2 ⌃), e que é fechada para a reunião, concatenação e fechode Kleene.

Neste e nos capítulos seguintes vamos estudar várias representações finitasde linguagens regulares.

Seja L1 a linguagem de alfabeto {0, 1} formada pelas palavras que têm 000

como sua subpalavra. A linguagem L1 pode ser então expressa à custa de outraslinguagens usando as operações sobre linguagens definidas no Capítulo 2,

L1 = {0, 1}?{000}{0, 1}?.

Podemos continuar a expressar L1, agora usando conjuntos singulares desímbolos:

L1 = ({0} [ {1})?{0}{0}{0}({0} [ {1})?.

Se assumirmos que cada símbolo do alfabeto representa a linguagem que contéma palavra formada unicamente por esse símbolo, obtemos da expressão anterior,outra muito mais simples onde a reunião é representada pelo símbolo +:

(0+ 1)?000(0+ 1)?.

25

Draft-v

0.2Esta é a ideia que está por detrás das expressões regulares. Para indicar alinguagem definida por esta expressão regular escrevemos:

L1 = L((0+ 1)?000(0+ 1)?).

Consideremos outro exemplo. A linguagem

L1 = {x 2 {0, 1}? | x tem 2 ou 3 ocorrências de 1, não sendo as duas primeirasconsecutivas},

pode ser descrita por:

L1 = {0}?{1}{0}?{0}{1}{0}?({1}{0}? [ {"}),

ou simplificando, podemos representar a linguagem L1 pela expressão

0?10

?010

?(10? + ").

Podemos, então, definir o conjunto das expressões regulares (ER) da seguinteforma.

Definição 3.2 (expressão regular (ER)) O conjunto ER das expressõesregulares r e as linguagem por elas descritas L(r) definem-se indutiva-mente como:

i) ; 2 ER; e L(;) = ;.

ii) " 2 ER e L(") = {"}.

iii) Se � 2 ⌃ então � 2 ER; e L(�) = {�}.

iv) Se r1 2 ER e r2 2 ER então (r1r2) 2 ER; e L((r1r2)) = L(r1)L(r2).

v) Se r1 2 ER e r2 2 ER então (r1+r2) 2 ER; e L((r1+r2)) = L(r1)[L(r2).

vi) Se r1 2 ER então (r1)? 2 ER; e L((r1)?) = L(r1)?.

As expressões regulares constituem uma representação compacta e expres-siva para representar linguagens regulares, i.e,

Teorema 3.3 Uma linguagem sobre um alfabeto ⌃ é regular se e só se érepresentada por uma expressão regular.

Dem. É imediato pela definição de linguagem regular. ⇤

Exemplo 3.4 Seja ⌃ = {0, 1}. As expressões regulares seguintes represen-tam respectivamente a linguagem indicada à direita.

26

Draft-v

0.2expressão regular linguagem descrita(0+ 1) {0, 1}

(0)? {", 0, 00, 000, 0000, 00000, . . .}

((0)?(11)) {11, 011, 0011, 00011, 000011, 0000011, . . .}

(01)? {", 01, 0101, 010101, 01010101, 0101010101, . . .}

(0+ 1)? {", 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, . . .}

((1)?(0((0+ 1)?))) {0, 10, 01, 00, 000, 100, 010, 001, 110, 101, 011, . . .}

= {x | x tem algum 0}

Usando uma convenção idêntica à aplicada a expressões aritméticas en-volvendo soma, produto e potenciação, podemos abreviar as expressões reti-rando parêntesis não necessários, como ilustrado na Figura 3.1. As regras deprecedência para as operações + (união), concatenação e ? (fecho de Kleene)correspondem às usadas nas expressões aritméticas para a adição, a multi-plicação e a potenciação, respectivamente. Isto é, a precedência é fecho deKleene > concatenação > união. A vantagem da introdução desta simplificaçãoé claramente ilustrada pelos exemplos dados na Figura 3.1.

(r+ s) r+ s

((r+ s) + t) r+ s+ t

(r(st)) rst

(r(s+ t)) r(s+ t)((rs) + (rt)) rs+ rt

(;)? ;?

((r)?)? (r?)?

(((r)?(s)?))? (r?s?)?

(0+ 1) 0+ 1

((0)?(1(1)?)) 0?11

?

(((0)?(11)) + ((10)1)) 0?11+ 101

((01))? (01)?

((1)?(0(0+ 1)?)) 1?0(0+ 1)?

(((0+ 1)?)((00)(0+ 1)?)) (0+ 1)?00(0+ 1)?

((((0+ 1)?)((00)0)) + (((01)?)(01)?)) (0+ 1)?000+ (01)?01?

Figura 3.1: Expressão regular e a sua abreviatura.

Exemplo 3.5 i) A palavra baaababbaa pertence à linguagem L((aa?b?a+

27

Draft-v

0.2b)?) uma vez que:

b 2 L(b)

aa 2 L(aa?b?a)

aba 2 L(aa?b?a)

b 2 L(b)

b 2 L(b)

aa 2 L(aa?b?a).

Logo, baaababbaa 2 L((aa?b?a+ b)?).

ii) A linguagem

L1 = { x 2 {0, 1}? | x tem pelo menos um 1 }

pode ser representada por L((0+ 1)?1(0+ 1)?).

iii) A linguagem

L2 = { x 2 {0, 1}? | x tem um número par de 0’s }

pode se representada por L((1?01?0)?1?).

iv) A linguagem

L3 = { x 2 {0, 1}? | x não tem 111 como subpalavra }

pode ser representada por L((0+ 01+ 011)? + 1+ 11).

Exemplo 3.6 Para cada uma das linguagens seguintes determinar umaexpressão regular que a representa.

i) Seja A = { x 2 {0, 1}? | x tem pelo menos um 11 entre cada par de 0’s}

Numa palavra de A, se ocorrer um 0 tem de ocorrer 11 a seguir.Temos então a expressão regular

(1+ 011)?.

Mas, excepto para o 0 mais à direita. Então, temos que

A = L((1+ 011)?("+ 0+ 01)).

ii) Seja B = { x 2 {a, b}? | x que tem um número par de a’s }.

Se uma palavra de B tiver um a tem necessariamente outro. Temosentão que:

28

Draft-v

0.2B = L((ab?

a+ b)?).

Nota que se uma palavra tiver número par de a’s, e esse número nãofor zero, então a palavra pode ser vista como uma sequência de b’s ede palavras em L(ab?

a).

Por exemplo, para babbbbbabbbbbbbbbaaaa tem-se a seguinte de-composição

b|{z}2

L(b?)

abbbbba| {z }2

L(ab?a)

bbbbbbbbb| {z }2

L(b?)

aa|{z}2

L(ab?a)

aa|{z}2

L(ab?a)

Exemplo 3.7 Seja C = {x 2 {0, 1} | x não tem a subpalavra 111}

Numa palavra de C, se houver um 1 ou um 11 tem de haver pelomenos um 0. Isto é,

C = L((0? + 0?(1+ 11)(0+(1+ 11))?0?))

Seja D = {x 2 {0, 1}? | x não tem a subpalavra 00}

Numa palavra de D, à direita de um 0 tem de haver um 1. Temosentão a expressão (01+1)?. Mas a palavra pode terminar em 0. Fica,então,

D = L((01+ 1)?(0+ "))

Seja R, linguagem dos números decimais racionais em ⌃ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,-, .}

Para os dígitos temos a expressão regular: digito = (0 + 1 + 2 + 3 +4+ 5+ 6+ 7+ 8+ 9). E,

R = L(("+-)digito+(.digito+ + "))

Exercício 20 Melhorar a expressão regular obtida no exemplo anterior para alinguagem R, para que não existam 0’s à esquerda não significativos.

Exercício 21 Escreve expressões regulares para cada uma das seguintes lingua-gens de {0, 1}.

1. palavras com mais do que três 0’s

2. palavras com um número de 0’s divisivel por três.

3. palavras com exactamente uma ocorrência da subpalavra 000.

29

Draft-v

0.24. palavras em que não ocorre a subpalavra 000.

A verificação que uma dada palavra pertence à linguagem definida poruma expressão regular tem uma complexidade O(mn

2) [Yu97], onde n é ocomprimentoda palavra e m o número de símbolos da expressão regular.

Exercício 22 Quais das seguintes afirmações são verdadeiras? Justifica.

1. baa 2 L(a?b?a?b?)

2. L(b?a?) \ L(a?

b?) = L(a? + b

?)

3. L(a?b?) \ L(c?d?) = ;

4. abcd 2 L((a(cd)?b)?)

3.1 Equivalência de expressões regulares

Definição 3.8 (Expressões regulares equivalentes) Duas expressões re-gulares r1 e r2 são equivalentes, e escreve-se r1 = r2, se L(r1) = L(r2).

Pode verificar-se que = é uma relação de equivalência em ER, i.e.,

r = r, para todo o r 2 ER (reflexiva)

se r = s então s = r, para todos r, s 2 ER (simétrica)

se r = s e s = t então r = t, para todos r, s e t 2 ER (transitiva)

Exercício 23 Verifica as condições anteriores.

Exemplo 3.9 A expressão regular

1? + 1

?0(110)?1?

é equivalente à expressão

1?("+ 0(110)?1?),

e define a linguagem das palavras que têm exactamente dois 1’s entre cadaduas ocorrências consecutivas de 0’s. Notar que se x é uma palavra tal queentre cada duas ocorrências consecutivas de 0’s há exactamente dois 1’s,então se x for da forma

x10x2

sendo o 0 indicado o 0 mais à esquerda, podemos dizer que x1 2 L(1?)e que ou não há 0’s em x2 (isto é, x2 2 L(1?)) ou x2 = 110x3, com x3

pertencente exactamente à mesma linguagem que x2. Assim conclui-seque x2 2 L((110)?1?).

30

Draft-v

0.2Exemplo 3.10 A linguagem das palavras de alfabeto {0, 1} que têm 00 comosubpalavra é descrita pela expressão regular

(0+ 1)?00(0+ 1)?.

Uma expressão regular equivalente é por exemplo,

(01+ 1)?00(0+ 1)?.

Notar que, a expressão regular

(01+ 1)?,

descreve as palavras em {0, 1}? que se tiverem 0’s, então imediatamente àdireita de cada 0 têm um 1. Assim, ao definirmos (01+ 1)?00(0+ 1)? comosendo a expressão das palavras que têm 0’s consecutivos, o par de 0’s quedestacámos é o par de 0’s consecutivos mais à esquerda na palavra.

Exercício 24 Escreve expressões regulares mais simples equivalentes às seguin-tes expressões, indicando as equivalências usadas.

1. ;+ a? + b

? + (a+ b)?

2. ((a?b?)?(b?

a?)?)?

3. (a?b)? + (b?

a)?

4. (a+ b)?a(a+ b)?

Exercício 25 Para cada um dos seguintes pares de expressões regulares, indica,justificando, se são equivalentes.

1. (a?b)?, (a+ b)?

2. (a(bba)?)?, (a+ bb)?

3. (a?b?)?, (a+ b)?

4. ;+ a+ (a?b)b?, (ab?)?

3.1.1 Expressões Regulares e Álgebras de Kleene

Podemos associar diversas estruturas algébricas aos conjuntos de linguagensformais. Vamos ver que as linguagens regulares (expressões regulares) formamuma álgebra de Kleene.

31

Draft-v

0.2Um semigrupo é uma estrutura algébrica (S, ·) onde S é um conjunto e ·

uma operação binária associativa, isto é tal que x · (y · z) = (x ·y) · z para todo ox, y, z 2 S. Um monóide é uma estrutura algébrica (M, ·, 1), onde (M, ·) é umsemigrupo e 1 é um elemento de M que é a identidade direita e esquerda para·, i.e. x · 1 = 1 · x = x para qualquer x 2 M.

Dado um alfabeto ⌃, a estrutura algébrica (⌃?, ·, ✏) é um monóide. Para

tal basta considerar a definição da operação de concatenação de palavras (2.5).Um monóide M é comutativo se xy = yx, para todo x, y 2 M.

Definição 3.11 (Semianel) Um semianel é uma estrutura algébrica (S,+, ·, 0, 1)tal que:

(S,+, 0) é um monóide comutativo.

(S, ·, 1) é um monóide.

a operação · distribui à esquerda e à direita sobre a operação +, i.e.x(y+ z) = xy+ xz e (x+ y)z = xz+ yz para todos x, y, z 2 S.

0 é um elemento absorvente para ·, i.e. 0 · x = x · 0 = 0 para todox 2 S.

Podemos omitir os parêntesis considerando que a operação · tem prioridadesobre a operação +.

Um semianel S é idempotente se x + x = x para todo o x 2 S. Umsemianel idempotente (S,+, ·, 0, 1) é caracterizado, então, pelo seguinte conjuntode propriedades para todo x, y, z 2 S:

x+ (y+ z) = (x+ y) + z, (3.1)x+ y = y+ x, (3.2)x+ 0 = x, (3.3)x+ x = x, (3.4)

x(yz) = (xy)z, (3.5)1x = x, (3.6)x1 = x, (3.7)

x(y+ z) = xy+ xz, (3.8)(x+ y)z = xz+ yz, (3.9)

0x = 0, (3.10)x0 = 0. (3.11)

As propriedades 3.1-3.4 correspondem, respectivamente, à associatividade, co-mutatividade, elemento neutro e idempotência do operador + (e definem ummonóide comutativo e idempotente). As propriedades 3.5 a 3.7 indicam que

32

Draft-v

0.2S com a operação · é um monóide. As propriedades 3.8 e 3.9 correspondem àdistributividade de · sobre +. Finalmente, as propriedades 3.10 e 3.11 definemo elemento absorvente para ·.

Definimos num semianel idempotente a seguinte relação de ordem:

x ydef= x+ y = y.

Exercício 26 Mostrar que a relação é uma relação de ordem, isto é, quereflexiva, anti-simétrica e transitiva.

As operações + e . são monótonas em relação a , i.e. para todo ox, y, z 2 S temos que:

x y ! x+ z y+ z, (3.12)x y ! z+ x z+ y, (3.13)

x y ! xz yz, (3.14)x y ! zx zy. (3.15)

Exercício 27 Mostrar as desigualdes anteriores, i.e. que as operações + e . sãomonótonas em relação a .

Definição 3.12 (Álgebra de Kleene) Uma álgebra de Kleene é uma es-trutura algébrica (S,+, ·,

?, 0, 1) onde (S,+, ·, 0, 1) é um seminanel idempo-

tente e ? é uma nova operação unária que verifica as seguintes propriedadespara todo x, y, z 2 S:

1+ xx? x

?, (3.16)

1+ x?x x

?, (3.17)

z+ yx x ! y?z x, (3.18)

z+ xy x ! zy? x. (3.19)

Podemos considerar o conjunto de expressões regulares sobre um alfabeto ⌃ umaestrutura algébrica se considerarmos as operações + e ·, one o elemento neutro,1, de · é o " e o elemento neutro , 0, de + é o ;. Dado que duas expressõesregulares r e s verificam r = s se as suas linguagens são iguais, atendendo àspropriedades das operações sobre linguagens, temos o seguinte teorema.

Teorema 3.13 Dado um alfabeto ⌃, o conjunto das expressões regularesER forma uma álgebra de Kleene (ER,+, ·,

?, ;, ")).

Dem. Que (ER,+, ·,?, ;, ") é um semianel idempotente resulta directamente

da definição de equivalência de expressões regulares e das propriedades

33

Draft-v

0.2da reunião e concatenação de linguagens, e que foram definidas no Teo-rema 2.19 do Capítulo 2. Por exemplo, para mostrar que para quaisquerexpressões regulares r e s, se tem r + s = s + t, basta ver que L(r +s) = L(r) [ L(s) = L(s) [ L(r) = L(s + t). Do mesmo modo se t

for também uma expressão regular, para provar que r(st) = (rs)t bastaver que L(r(st)) = L(r)L((st)) = L(r)(L(s)L(t)) = (L(r)L(s))L(t) =L((rs))L(t) = L((rs)t).

Falta demonstrar que verificam as propriedades 3.16–3.19. Sendo r e s

duas expressões regulares seja A = L(r) e B = L(s). Neste caso a relação é a relação ✓ em ⌃

?. Para a propriedade 3.16, "+ rr? r

?, temos quemostrar que

{"} [AA?✓ A

?.

Seja x 2 {"} [ AA?. Se x = ", então por definição x 2 A

?. Senão, existel 2 N, tal que x 2 A

l+1, logo x 2 A?. Analogamente demonstra-se a

propriedade 3.17. Para a propriedade 3.18, s + rx x ! r?s x ,temos

que mostrar queB [AX ✓ X ! A

?B ✓ X.

Se B [AX ✓ X, então B ✓ X e AX ✓ X. Temos então que AB ✓ AX ✓ X,isto é, AB ✓ X. Então A

2B ✓ AX ✓ X, isto é A

2B ✓ X. Por indução

podemos provar que AnB ✓ X, para n 2 N. Verifica-se para n = 1.

Suponhamos que AnB ✓ X, então A

n+1B = AA

nB ✓ AX ✓ X. Logo,

A?B ✓ X. Em particular temos que B [A(A?

B) = A?B:

B [A(A?B) = ({"} [AA

?)B = A?B.

De modo análogo demonstra-se a propriedade 3.19. ⇤

Podemos então concluir que para determinar se duas expressões regularessão equivalentes, r1 = r2 bastaria que isso fosse consequência das propriedadesda Álgebra de Kleene. Contudo, na prática, descobrir quais as igualdades a usarnão é tarefa fácil. Vamos considerar alguns exemplos. Por exemplo, mostrarque

"+ rr? = r

?.

Pela propriedade 3.16 já temos que " + rr? r

?. Temos que demonstrarque r

? "+ rr

?, ou equivalentemente que

r?" "+ rr

?.

Esta expressão é o lado direito da implicação na propriedade 3.18 com z subs-tituído por ", a substituído por r e x substituído por " + rr

?. Basta entãodemonstrar que o lado esquerdo da implicação se verifica, i.e.

"+ r("+ rr?) "+ rr

?.

34

Draft-v

0.2Mas isto é verdade pela propriedade 3.16, substituindo o lado esquerdo de

por ("+ rr?), isto é, porque ("+ rr

?) r? e considerando as monotonias 3.19

e 3.16. De modo analogo se prova que

"+ r?r = r

?.

Considera agorar?r? = r

?.

Mostramos, primeiro, que r?r? r

?. Como " + rr? = r

?, temos rr? r

?.Então, por 3.4, r? + rr

? r

? e pela propriedade 3.18, temos r?r? r

?. Para aoutra desigualdade,

r?r? = r

?("+ rr?) = r

? + r?rr

?.

Donde concluímos que r?r? = r

?.Finalmente vamos ver que

(r+ s)? = r?(sr?)?.

Para mostrar que (r+ s)? r?(sr?)?, nota que:

" r?(sr?)?

rr?(sr?)? r

?(sr?)?

sr?(sr?)? (sr?)?

r?(sr?)?.

Então,

"+ (r+ s)r?(sr?)? "+ rr?(sr?)? + sr

?(sr?)?

r?(sr?)?.

A desigualdade segue da propriedade 3.18. Considerando a monotonia dosoperadores, temos a outra desigualdade:

r?(sr?)? r+ s

?((r+ s)(r+ s)?)?

(r+ s)?(r+ s)?)?

(r+ s)?.

A proposição seguinte resume algumas das propriedades obtidas.

Proposição 3.14 Quaisquer que sejam as expressões regulares r e s, asseguintes propriedades verificam-se:

1. r? = "+ rr

?.

35

Draft-v

0.22. r

?r? = r

?.

3. (r+ s)? = r?(sr?)?.

4. (r+ s)? = (r?s?)?.

5. r(sr)? = (rs)?r

6. r?? = r

?

Dem. As propriedades 1. a 3. foram obtidas acima. As restantes podemser demostradas de forma análoga ou deduzidas directamente a partir daspropriedades das linguagens consideradas no Teorema 2.19 do Capítulo 2.⇤

Exercício 28 Termina a demonstração da Proposição 3.14.

Lema 3.15 (de Arden) Sejam r e s duas expressões regulares sobre umalfabeto ⌃. A equação s + xr = x (respectivamente s + rx = x) tem comosolução mínima a expressão sr

? (respectivamente r?s), que é única se " /2

L(r).

Dem. Para ver que é uma solução basta ver que

s+ sr?r = s("+ r

?r) = sr

?,

e de modo análogo se mostra que r?s é solução de s+ rx = x. Da proprie-

dade 3.19 (respectivamente 3.18) concluí-se que sr? x (respectivamente

r?s x) para qualquer x que seja solução da equação. ⇤

3.2 Expressões regulares e padrões

Em várias aplicações e linguagens de programação usam-se variantes das expres-sões regulares, denominados também por padrões, para descrever e reconhecerconjuntos de palavras (sequências de caracteres) que correspondem a lingua-gens regulares:

em linguagens de programação que manipulam sequências de caracteres :bash, Tcl, Perl, Python, etc

reconhecedores de padrões em ficheiros, como o comando grep em UNIX:grep ’ex*’ teste.txt

36

Draft-v

0.2analisadores lexicais, como lex, que permitem seccionar um texto emelementos identificados (tokens): p.e. num programa em C, identificar oque são palavras reservadas (if, while,struct,. . . ), variáveis, constantes,operadores, etc. São usados pelos compiladores.

editores de texto, na procura de palavras.

Um padrão é uma sequência de símbolos duma dada forma que representauma linguagem num dado alfabeto. O conjunto de palavras que são reconhecidaspor um dado padrão ↵ denota-se por L(↵).

3.2.0.1 Padrões para expansão de nomes de ficheiros

Estes padrões são usuais em linguagens de comandos em UNIX, por exemplo nabash. O alfabeto é o conjunto de caracteres do código ASCII (ou UNICODE).Os padrões normalmente usados são os da tabela seguinte.

Padrão Reconhece Exemploa o carácter a ls -l ola? qualquer carácter do alfabeto ls -l ex?.c* zero ou mais caracteres ls -l *.c

[...] qualquer carácter da lista ls -l ex*.[ch][c-d] qualquer carácter entre dois caracteres separados por

-ls -l ex[1-9].c

[^...] caracteres que não pertencem à lista ls -l ex[^12].c{...} conjuntos alternativos ls -l *.{gif,jpg}

Tabela 3.1: Padrões usuais de “expressões regulares”

Exercício 29 Verificar que são regulares as linguagens descritas por cada umdos padrões acima. Nota a diferença do uso do símbolo *. E o que significa ?.

3.2.0.2 Regexp

Estes padrões são geralmente usados no comando grep do UNIX e em linguagensde programação como o Perl, o Python e o Tcl.

Salientámos os seguintes padrões atómicos:

37

Draft-v

0.2Padrão atómico Reconhece Exemplo

a o carácter a a\a o carácter especial a \n. qualquer carácter .

[...] qualquer carácter da lista [abc]qualquer carácter entre dois caracteres separados por-

[a-z]

[^...] caracteres que não pertencem à lista [^0-9]^ o inicio da palavra ^a$ o fim da palavra a$

Tabela 3.2: Padrões atómicos

Em relação padrões compostos, para além das operações de união, conca-tenação e fecho de Kleene, consideram-se o r

+ que é equivalente a r+r?, a opção

r? que é equivalente a r+ " e o agrupamento, que é um operação que pode não

ser regular.

Padrão composto Reconhece Exemploregex|regex qualquer dos padrões [0-9]|[+-]regexregex concatenação de padrões [0-9][a-z]

regex? zero ou mais regex [0- 9]?

regex+ um ou mais regex [0- 9]+

regex? zero ou um regex [0-9]?(regex) regex (permite agrupamentos) (a|o)

Tabela 3.3: Padrões compostos

38