03b · Expressões Regulares

Resumo em 30 segundos

Uma expressão regular (ER) descreve uma linguagem regular de forma compacta usando só três operações: união ($\alpha |\beta$), concatenação ($\alpha \beta$) e repetição / fecho de Kleene (${\alpha }^{\ast }$). Precedência: $\ast$ antes de concatenação, concatenação antes de $|$. ER, gramática regular e autômato finito descrevem a mesma classe de linguagens.

Anterior: 03 - Gramáticas Regulares · Voltar ao mapa · Próxima: 04 - Autômatos Finitos Determinísticos

---

Slide 3: conceito

• Esquema “informal” e sucinto para representar linguagens regulares.
• Formalismo denotacional (a ER representa a linguagem) e gerador (dá para produzir as sentenças a partir dela). Ver os três tipos de formalismo em aula 01.
• C/C++, Java, Perl, Python e outras suportam ERs nativamente ou por biblioteca.

Slide 4: definição

Base:

1. $\varnothing$, $\epsilon$ e cada símbolo $a\in V_t$ são ERs.

Indução: se $\alpha$ e $\beta$ são ERs, então também são ERs:

• $\alpha |\beta$ (união)
• $\alpha \beta$ (concatenação)
• ${\alpha }^{\ast }$ (repetição, zero ou mais vezes)

Detalhe no slide 4

O slide escreve ”$\alpha$ e $\beta \in V_t$ são ERs, então…”. O correto é “se $\alpha$ e $\beta$ são ERs” (quaisquer ERs, não apenas símbolos do alfabeto). Senão não daria para montar $(ab{)}^{\ast }$, por exemplo, já que $ab$ não é um símbolo de $V_t$.

Precedência: repetição > concatenação > união.

ER	Lida como	Linguagem
$a{b}^{\ast }$	$a(b^{\ast })$	a, ab, abb, …
$(ab{)}^{\ast }$		$\epsilon$, ab, abab, …
$a\mid bc$	$a\mid (bc)$	a, bc
$(a\mid b)c$		ac, bc

Slide 5: extensões e notação alternativa

Extensão	Definição	Leitura
${\alpha }^{+}$	$\alpha {\alpha }^{\ast }$	uma ou mais vezes
${\alpha }^{?}$	$\alpha \mid \epsilon$	opcional
${\alpha }^n$	$\alpha \alpha \dots \alpha$ ($n$ vezes)	exatamente $n$

Notação alternativa (o professor avisa que não usa no curso): $\alpha |\beta =\alpha +\beta =\alpha \cup \beta$, e ${\alpha }^{\ast }=\{\alpha \}$.

Cuidado ao ler outros materiais

Muitos livros escrevem união como $+$, então $a+b$ lá significa $a|b$ aqui, e não “um ou mais”. E a notação $\{\alpha \}$ para ER é diferente de $L(\alpha )=\{\alpha \}$, que é um conjunto com uma palavra. O balão do slide 5 chama a atenção exatamente para isso.

Slide 6: que linguagem uma ER representa

• $L(\varnothing )=\varnothing$
• $L(a)=\{a\}$, para $a\in V_t$
• $L(\alpha \beta )=L(\alpha )L(\beta )$ (concatenação de linguagens: toda palavra de uma seguida de toda palavra da outra)
• $L(\alpha |\beta )=L(\alpha )\cup L(\beta )$ (o slide escreve com $|$, mas a operação entre conjuntos é a união $\cup$)
• $L({\alpha }^{\ast })=L(\alpha {)}^{\ast }$

Falta no slide, mas faz parte da definição: $L(\epsilon )=\{\epsilon \}$.

Slide 7: exemplo resolvido

Linguagem de $\alpha (\alpha |\beta {)}^{\ast }$:

$L(\alpha (\alpha |\beta {)}^{\ast })=L(\alpha )(L(\alpha )\cup L(\beta ){)}^{\ast }=\{\alpha \}\{\alpha ,\beta {\}}^{\ast }$

Ou seja, todas as palavras sobre $\{\alpha ,\beta \}$ que começam com $\alpha$.

Slide 8: representações que valem decorar

ER	Linguagem	Conferido
$\alpha \beta$	$\{\alpha \beta \}$
$\alpha \mid \beta$	$\{\alpha ,\beta \}$
$\alpha (\alpha \mid \beta {)}^{\ast }$	$\{\alpha ,\alpha \alpha ,\alpha \beta ,\alpha \alpha \alpha ,\dots \}$
${\alpha }^{\ast }\beta {\alpha }^{\ast }\beta {\alpha }^{\ast }$	palavras com exatamente dois $\beta$
$0^{\ast }10^{\ast }(10^{\ast }10^{\ast }{)}^{\ast }$	palavras com número ímpar de 1	sim, até tamanho 10
$1^{\ast }(101{)}^{\ast }{1}^{\ast }$	slide diz: palavras sem 00	não confere, ver abaixo

A última linha do slide 8 não confere

Testei por programa todas as palavras até tamanho 10. A ER $1^{\ast }(101{)}^{\ast }{1}^{\ast }$ realmente não gera nenhuma palavra com 00, mas também deixa de fora muitas palavras sem 00: 0, 01, 10, 010, 011, 110…

Uma ER que gera exatamente as palavras sem 00:
$(1\mid 01{)}^{\ast }(0\mid \epsilon )$
Intuição: todo 0 precisa ser seguido de 1 (bloco 01), exceto possivelmente um 0 no final. Conferida por programa até tamanho 10.

Pode ser que os expoentes do slide estejam em posições que a exportação do PDF deslocou. Vale confirmar com o professor.

Leitura de $0^{\ast }10^{\ast }(10^{\ast }10^{\ast }{)}^{\ast }$: o trecho $0^{\ast }10^{\ast }$ garante um 1; cada repetição de $(10^{\ast }10^{\ast })$ acrescenta dois. Então o total é sempre ímpar, e os $0^{\ast }$ permitem zeros em qualquer lugar.

Slides 9 e 10: ER e elementos léxicos

É aqui que a teoria encontra o compilador. O analisador léxico reconhece:

Elemento	Descrição	ER
Letra	$L=\{A,\dots ,Z,a,\dots ,z\}$	$L$
Dígito	$D=\{0,\dots ,9\}$	$D$
Identificador	letra seguida de zero ou mais letras ou dígitos	$I=L(L\mid D{)}^{\ast }$
Número inteiro	0 sozinho, ou um dígito de 1 a 9, opcionalmente com - antes, seguido de dígitos	$N=0\mid ({-}^{?}(1\mid 2\mid \cdots \mid 9)D^{\ast })$

Repare que $N$ não aceita -0 nem 007. Os elementos léxicos formam uma linguagem dentro da linguagem de programação.

Complemento: as mesmas ERs em JavaScript/TypeScript

const identificador = /^[A-Za-z][A-Za-z0-9]*$/;
const inteiro       = /^(0|-?[1-9][0-9]*)$/;
identificador.test("x1");   // true
inteiro.test("-0");         // false

Diferenças da notação da aula: [1-9] é a união $1|2|\dots |9$; ? é o opcional; ^ e $ exigem casar a palavra inteira. As regex de programação têm recursos extras (retrovisores como \1, lookahead) que ultrapassam as linguagens regulares da teoria.

Slide 11: equivalência entre ERs

$\alpha =\beta$ se, e somente se, $L(\alpha )=L(\beta )$.

Identidade	Por quê
$\varnothing \alpha =\alpha \varnothing =\varnothing$	concatenar com “nenhuma palavra” não produz palavra
$\epsilon \alpha =\alpha \epsilon =\alpha$	$\epsilon$ é neutro da concatenação
${\varnothing }^{\ast }=\epsilon$	zero repetições dá sempre $\epsilon$
${\epsilon }^{\ast }=\epsilon$	repetir o vazio continua vazio
$\alpha \mid \beta =\beta \mid \alpha$	união é comutativa
$\varnothing \mid \alpha =\alpha$	$\varnothing$ é neutro da união
$\alpha \mid \alpha =\alpha$	união é idempotente
$({\alpha }^{\ast }{)}^{\ast }={\alpha }^{\ast }$	repetir repetição não acrescenta nada
$\alpha (\beta \mid \gamma )=\alpha \beta \mid \alpha \gamma$	distributiva à esquerda
$(\alpha \mid \beta )\gamma =\alpha \gamma \mid \beta \gamma$	distributiva à direita
$(\alpha \beta {)}^{\ast }\alpha =\alpha (\beta \alpha {)}^{\ast }$	”deslizamento”: abab...a = a + baba...
$(\alpha \mid \beta {)}^{\ast }=({\alpha }^{\ast }\mid \beta {)}^{\ast }={\alpha }^{\ast }(\alpha \mid \beta {)}^{\ast }=(\alpha \mid \beta {\alpha }^{\ast }{)}^{\ast }=({\alpha }^{\ast }{\beta }^{\ast }{)}^{\ast }={\alpha }^{\ast }(\beta {\alpha }^{\ast }{)}^{\ast }=({\alpha }^{\ast }\beta {)}^{\ast }{\alpha }^{\ast }$	todas geram “qualquer palavra sobre $\{\alpha ,\beta \}$”

Armadilha clássica

$(\alpha \beta {)}^{\ast }\ne {\alpha }^{\ast }{\beta }^{\ast }$. Exemplo: abab está em $(ab{)}^{\ast }$ mas não em $a^{\ast }{b}^{\ast }$; aab está em $a^{\ast }{b}^{\ast }$ mas não em $(ab{)}^{\ast }$.

Slide 12: ERs do mundo real

Objeto	ER do slide	Exemplo que casa
Números com sinal	$0\mid ({-}^{?}(1\text{-}9)(0\text{-}9{)}^{\ast })$	-42
Endereço de internet	$w^3.(a\text{-}z{)}^{+}.(a\text{-}z{)}^3.(a\text{-}z{)}^2$	www.exemplo.com.br
IPv4	$((1^{?}{d}_1{)}^{?}{d}_1\mid 2(d_2{d}_1\mid 5d_3)).{)}^3((1^{?}{d}_1{)}^{?}{d}_1\mid 2(d_2{d}_1\mid 5d_3))$	192.168.0.1
Valor monetário	R$ seguido de $(0\mid ((1\text{-}9)(0\text{-}9{)}^{\ast })),(0\text{-}9{)}^2$	R$1500,00

Como ler o octeto do IPv4, com $d_1=\mathrm{0..9}$, $d_2=\mathrm{0..4}$, $d_3=\mathrm{0..5}$:

• $(1^{?}{d}_1{)}^{?}{d}_1$ cobre 0 a 199 (um dígito; dois dígitos; ou 1 + dois dígitos).
• $2d_2{d}_1$ cobre 200 a 249.
• $25d_3$ cobre 250 a 255.

Conferi por programa: aceita 192.168.0.1 e 255.255.255.255, rejeita 256.1.1.1 e 300.1.1.1. Aceita também formas com zero à esquerda como 01, o que alguns validadores rejeitariam.

Limitação do exemplo de endereço

A ER de endereço exige exatamente www, um nome, 3 letras e 2 letras. Ela casa www.exemplo.com.br, mas não exemplo.com nem www.exemplo.org. É um exemplo didático, não um validador completo.

Slides 13 e 14: exercícios

Slide 13, parte 1: ∈ ou ∉

Lembre: $\{a{\}}^{\ast }\{b{\}}^2$ é a linguagem de $a^{\ast }bb$.

Afirmação	Resposta	Por quê
ab em $\{a{\}}^{\ast }\{b{\}}^2$	∉	precisa terminar em bb
ba em $\{b{\}}^{\ast }\{a\}$	∈	$b^{1}a$
ab em $(\{a{\}}^{\ast }\{b\}{)}^2$	∉	precisa de dois b
$a{b}^2$ = abb em $(\{a{\}}^{\ast }\{b\}{)}^2$	∈	ab · b (segundo bloco com zero a)

Slide 13, parte 2: em relação a (a ba)*

Truque: $(a^{\ast }b{a}^{\ast }{)}^{\ast }$ é $\{\epsilon \}$ mais toda palavra que tem pelo menos um b. Cada b “puxa” os a vizinhos para o seu bloco.

Palavra	Resposta
$a^{2}b{a}^{10}$	∈
$a{b}^{10}$	∈
$b^{10}a$	∈
$a{b}^{2}a{b}^3$	∈

Todas pertencem (conferido por programa). A única forma de não pertencer seria uma palavra não vazia sem nenhum b, como aaa.

Slide 14: ERs sobre {a, b}

Todas conferidas por programa contra a definição, até tamanho 12.

Contêm aa e bb: um aparece antes do outro, então une as duas ordens.
$(a|b{)}^{\ast }aa(a|b{)}^{\ast }bb(a|b{)}^{\ast }\mid (a|b{)}^{\ast }bb(a|b{)}^{\ast }aa(a|b{)}^{\ast }$

Não contêm aba: entre dois blocos de a, os b precisam vir em grupos de pelo menos dois. Só no fim pode sobrar um b sozinho.
$b^{\ast }(a^{+}b{b}^{+}{)}^{\ast }(a^{+}{b}^{?}{)}^{?}$

Contêm aa exatamente uma vez (contando ocorrências sobrepostas, então aaa tem duas): antes do aa, nada de aa e não pode terminar em a; depois, nada de aa e não pode começar com a.
$(b|ab{)}^{\ast }aa(b|ba{)}^{\ast }$

Slide 14: ERs sobre {a, b, c}

Contêm aa, bb e cc: união das 6 ordens possíveis. Com $\Sigma =(a|b|c)$:
${\Sigma }^{\ast }aa{\Sigma }^{\ast }bb{\Sigma }^{\ast }cc{\Sigma }^{\ast }\mid {\Sigma }^{\ast }aa{\Sigma }^{\ast }cc{\Sigma }^{\ast }bb{\Sigma }^{\ast }\mid \dots (\text{6 permutac¸o˜es})$

“Se contêm b, ele é logo seguido pelo último c”: interpretei como: pode haver no máximo um b; se houver, o símbolo seguinte é c, e depois dele não aparece mais nenhum c.
$(a|c{)}^{\ast }\mid (a|c{)}^{\ast }bc{a}^{\ast }$
O enunciado é ambíguo; se o professor quis outra leitura, a ER muda.

Comprimento 3: $(a|b|c)(a|b|c)(a|b|c)$, ou $(a|b|c{)}^3$.

Slide 14: verdadeiro ou falso

• baa ∈ $a^{\ast }{b}^{\ast }{a}^{\ast }{b}^{\ast }$: verdadeiro ($a^0{b}^1{a}^2{b}^0$).
• abcd ∈ $(a(cd{)}^{\ast }b{)}^{\ast }$: falso. Cada bloco é a, depois cd repetido, depois b. Em abcd, o primeiro bloco fecha em ab e sobra cd, que não começa com a.

---

Aprofundamento com os livros

Páginas das edições da sua pasta: Menezes 3ª edição (2000) e Ramos, José Neto e Vega (Bookman).

A notação dos livros usa + para união

Os dois livros escrevem a união como $r+s$ (o Ramos aceita também $r\mid s$). É a “notação alternativa” que o slide 5 avisa que o curso não usa. Na hora de ler:

Slides	Menezes (Def. 2.12, p. 50)	Ramos (p. 147 e 148)
$a\mid b$	$a+b$	$a\mid b$ ou $a+b$
$a^{+}$	$a{a}^{\ast }$ (ele não define ${}^{+}$ para ER)	$x^{+}=x{x}^{\ast }$

A precedência é a mesma nos três: repetição, depois concatenação, depois união.

O Ramos conta que a notação de expressões regulares foi criada por Kleene na década de 1950 como forma mais compacta de escrever conjuntos regulares (p. 147). Um conjunto regular é definido quase igual: $\varnothing$, $\{\epsilon \}$ e $\{a\}$ são regulares, e união, concatenação e fecho de regulares são regulares (p. 145 e 146).

Tabela de ERs do Menezes (Exemplo 12, p. 51)

Com a notação do curso (conferi cada linha por programa, até tamanho 12):

ER	Linguagem
$aa$	só a palavra aa
$b{a}^{\ast }$	começa com b, seguido de zero ou mais a
$(a\mid b{)}^{\ast }$	todas as palavras sobre $\{a,b\}$
$(a\mid b{)}^{\ast }aa(a\mid b{)}^{\ast }$	contém aa
$a^{\ast }b{a}^{\ast }b{a}^{\ast }$	exatamente dois b (igual ao slide 8)
$(a\mid b{)}^{\ast }(aa\mid bb)$	termina com aa ou bb
$(b\mid ab{)}^{\ast }(\epsilon \mid a)$	não tem dois a seguidos

A última é a “irmã” da correção que eu fiz para o slide 8: trocando $a\leftrightarrow 0$ e $b\leftrightarrow 1$, é a mesma ideia de $(1\mid 01{)}^{\ast }(0\mid \epsilon )$.

Exemplos práticos do Ramos (Exemplos 3.4 e 3.6, p. 146 a 148)

Com $D=(0\mid 1\mid \cdots \mid 9)$:

Objeto	ER	Detalhe
Naturais	$D{D}^{\ast }$	aceita zeros à esquerda
Reais sem sinal	$D{D}^{\ast }.D^{\ast }\mid D^{\ast }.D{D}^{\ast }$	aceita .315 e 47., mas não aceita . sozinho
Ponto flutuante	$(+\mid -\mid \epsilon )(D{D}^{\ast }.D^{\ast }\mid D^{\ast }.D{D}^{\ast })E(+\mid -\mid \epsilon )D{D}^{\ast }$	exemplo: -211.56E+3

O truque dos reais é bom de lembrar: a união de “dígitos antes do ponto obrigatórios” com “dígitos depois do ponto obrigatórios” garante que pelo menos um lado tem dígito. Conferi que $D{D}^{\ast }.D^{\ast }\mid D^{\ast }.D{D}^{\ast }$ não aceita ..

Linguagens sobre $\{a,b,c,d\}$ do Exemplo 3.6 do Ramos, reescritas na notação do curso:

• pelo menos um a: $(a\mid b\mid c\mid d{)}^{\ast }a(a\mid b\mid c\mid d{)}^{\ast }$
• exatamente dois a: $(b\mid c\mid d{)}^{\ast }a(b\mid c\mid d{)}^{\ast }a(b\mid c\mid d{)}^{\ast }$
• número par de a: $((b\mid c\mid d{)}^{\ast }a(b\mid c\mid d{)}^{\ast }a{)}^{\ast }(b\mid c\mid d{)}^{\ast }$ (cada volta do fecho consome dois a; o final cobre o resto, inclusive palavras sem nenhum a)
• começa com a e termina com b ou c: $a(a\mid b\mid c\mid d{)}^{\ast }(b\mid c)$

Duas ERs diferentes, mesma linguagem

O Ramos mostra (Exemplo 3.8, p. 148) que ERs com cara muito diferente podem ser equivalentes. Conferi por programa: $a\mid aaa{a}^{\ast }$ e $(aa{)}^{\ast }a(aaa{)}^{\ast }$ geram exatamente as cadeias de a com comprimento diferente de 0 e de 2. Para provar equivalência sem programa, compare os comprimentos: $2i+1+3j$ cobre 1, 3, 4, 5, 6, … e nunca 0 ou 2.

Leis algébricas (Ramos, p. 148 e 149)

O Ramos organiza as identidades do slide 11 por propriedade, o que ajuda a lembrar:

Propriedade	União	Concatenação
Associativa	$(\alpha \mid \beta )\mid \gamma =\alpha \mid (\beta \mid \gamma )$	$(\alpha \beta )\gamma =\alpha (\beta \gamma )$
Comutativa	$\alpha \mid \beta =\beta \mid \alpha$	não vale
Elemento neutro	$\varnothing$	$\epsilon$
Distributiva		$\alpha (\beta \mid \gamma )=\alpha \beta \mid \alpha \gamma$ e $(\beta \mid \gamma )\alpha =\beta \alpha \mid \gamma \alpha$

E $\varnothing$ “anula” a concatenação: $\alpha \varnothing =\varnothing \alpha =\varnothing$. O Menezes pede para provar várias dessas propriedades no exercício 2.13 (p. 81 e 82).

ER vira autômato e autômato vira ER

Os dois livros provam que ER e autômato finito descrevem a mesma classe de linguagens:

• ER para autômato (Menezes Teorema 2.13, p. 51 a 54; Ramos Algoritmo 3.16, p. 207 a 210): por indução no número de operadores. Monta-se um autômato pequeno para $\varnothing$, $\epsilon$ e cada símbolo, e depois “encaixa” os pedaços com transições vazias ($\epsilon$) para união, concatenação e fecho. O Menezes alerta (p. 53 e 54) que pular os estados novos de início e fim, “unificando” estados, pode gerar autômatos que aceitam palavras a mais.
• Autômato para ER (Menezes Teorema 2.14, p. 55, enunciado sem prova; Ramos Algoritmo 3.17, p. 211 a 216): elimina-se um estado de cada vez, trocando os rótulos das setas por ERs.

Os detalhes e um exemplo estão em 08 - Tópicos Complementares dos Livros.

Exercícios extras do Menezes (seção 2.10, p. 80 e 81)

2.6: descreva em palavras as linguagens destas ERs (convertidas para a notação do curso)

Minhas respostas, todas conferidas por programa até tamanho 12:

a) $(aa\mid b{)}^{\ast }(a\mid bb)$: o começo $(aa\mid b{)}^{\ast }$ só tem blocos de a de tamanho par, e a palavra termina com a ou com bb. Resultado: se a palavra termina em a, o último bloco de a é ímpar e todos os outros são pares; se termina em b, termina com bb e todos os blocos de a são pares.

b) $(b\mid ab{)}^{\ast }(\epsilon \mid a)$: palavras sem dois a seguidos.

c) $(aa\mid bb\mid (ab\mid ba)(aa\mid bb{)}^{\ast }(ab\mid ba){)}^{\ast }$: palavras com número par de a e par de b. É a versão em ER do AFD de paridade do slide 14 da aula 04.

2.4 c) ER para palavras sem aba

É o mesmo exercício do slide 14 desta aula. A resposta está lá: $b^{\ast }(a^{+}b{b}^{+}{)}^{\ast }(a^{+}{b}^{?}{)}^{?}$.

Para aprofundar nos livros

Onde ler (páginas das edições da sua pasta)

• Menezes (3ª ed.): 2.5 Expressão Regular, p. 50 a 55; exercícios 2.4, 2.6 a 2.8 e 2.13, p. 80 a 82.
• Ramos, José Neto e Vega: 3.2 Conjuntos e Expressões Regulares, p. 145 a 150; 3.6 Conjuntos Regulares e Autômatos Finitos, p. 206 a 216.

Relacionadas: 04 - Autômatos Finitos Determinísticos · Glossário · Flashcards