Expressões regulares

Prévia do material em texto

Expressões regulares
Apresentação
Uma expressão regular pode ser definida como uma sequência de padrões com o intuito de definir 
uma linguagem regular. Apesar de parecerem um fluxo aleatório de caracteres, essas expressões 
podem ser aplicadas na validação, busca e substituição em datas, endereços de e-mail, números de 
CPF (Cadastro de Pessoas Físicas), IPs (Internet Protocol), entre outros.
É válido salientar que, assim como os autômatos finitos, as expressões regulares denotam 
linguagens regulares e, assim, também são muito simples e fazem uso de operações como união, 
concatenação e fecho estrela.
Como visto, as expressões regulares podem ser aplicadas na validação, busca e substituição de 
dados. Desse modo, ao utilizar um aplicativo ou site, durante o preenchimento de algum formulário, 
por exemplo, é comum se deparar com a mensagem de dados inválidos.
Normalmente, esta é a resposta dada por algum conjunto de caracteres dados pelo usuário que não 
atendeu à determinada expressão regular, isto é, durante o processo de desenvolvimento dessa 
ferramenta, o desenvolvedor pode fazer uso do poder dessas expressões com o intuito de verificar 
determinado dado enviado a fim de garantir a validade deste e, dessa forma, impedir a entrada e o 
processamento de dados que possam prejudicar de alguma forma o funcionamento de um sistema.
Nesta Unidade de Aprendizagem, você aprenderá a definição de expressões regulares e seus 
operadores, verá exemplos de construção dessas expressões e saberá como convertê-las em 
autômatos finitos.
Bons estudos.
Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:
Definir expressões regulares e seus operadores.•
Exemplificar a construção de expressões regulares.•
Desenvolver o algoritmo de conversão de expressões regulares em autômatos finitos.•
Laiane
Desafio
A RegEx (abreviação do inglês para regular expression, em português “expressão regular”) é um 
mecanismo que assegura uma alternativa precisa e versátil para identificar um conjunto de 
símbolos ou cadeias de caracteres que possam representar padrões textuais na linguagem em 
questão de forma otimizada.
Neste Desafio, você precisa utilizar os conhecimentos adquiridos 
sobre as expressões regulares e suas estratégias de solução 
para determinados padrões de texto, levando em consideração 
o seguinte contexto: 
 
Aponte a câmera para o 
código e acesse o link do 
conteúdo ou clique no 
código para acessar.
https://statics-marketplace.plataforma.grupoa.education/sagah/b9155498-706c-4003-a844-ec95c3cc7078/625a75a2-0443-4281-a933-6fdbbfcc2ce0.png
 
A partir das especificações disponíveis nos três itens, informe as expressões regulares para cada 
item, representando a solução e justificando a sua estratégia de resolução.
Laiane
Padrão de resposta esperadoPara denotar as expressões solicitadas, pode-se simplesmente construir expressões sob a linguagem de forma a representar um número pela expressão (0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9); no entanto, tal expressão ficaria muito grande, e, assim, será usado Σ para representar qualquer símbolo do alfabeto dos dígitos de 0 a 9.Item 1 — As expressões regulares que denotam essas especificações são (ΣΣ) ΣΣΣΣΣ-ΣΣΣΣ ou escrita em Javascript como:/([/(][0-9]{2}[/)]9[0-9]{4}[/-][0-9]{4})/g.Desse modo, é possível formar cadeias como (99)99999-9999Item 2 — A expressão regular que denota essa especificação é a (ΣΣ) ΣΣΣΣΣ-ΣΣΣ6 ou escrita em Javascript como:/([/(][0-9]{2}[/)]9[0-9]{4}[/-][0-9]{3}6)/g.Assim, é possível obter cadeias como (88)99999-9996Item 3 — A expressão regular que denota essa especificação é (ΣΣ) Σ8ΣΣΣ-ΣΣΣΣ ou conforme a linguagem Javascript:/([/(][0-9]{2}[/)]98[0-9]{3}[/-][0-9]{4})/g.Obtendo cadeias como (88)98999-9999
Infográfico
As expressões regulares podem ser consideradas uma importante ferramenta para qualquer 
profissional que trabalha com computação, característica diretamente relacionada à possibilidade 
de utilizá-las para definir padrões de cadeias, por meio das quais, por exemplo, é possível fazer 
buscas, alterações e validações.
Assim como as expressões regulares, os autômatos finitos denotam linguagens regulares. Trata-se 
de modelos muito simples e de fácil entendimento. Semelhantemente às expressões regulares, 
podem ser utilizados para o reconhecimento de padrões e basicamente representam o modelo 
abstrato de um computador digital.
Ao verificar os dois modelos, é conhecido que ambos denotam linguagens regulares, entretanto há 
aqueles que preferem a notação dada por um modelo de estados, pois o entendimento da 
linguagem regular a partir de estados e transições pode se tornar mais simples do que por uma 
expressão regular.
Tendo em vista o exposto, no Infográfico, você compreenderá como transformar expressões 
regulares em autômatos finitos.
Laiane
Aponte a câmera para o 
código e acesse o link do 
conteúdo ou clique no 
código para acessar.
https://statics-marketplace.plataforma.grupoa.education/sagah/96fb9616-47f6-473f-a81e-c4485a5050ba/e5d8e438-4b52-42fe-a0cc-f53046421906.png
Conteúdo do livro
Uma expressão regular é uma sequência de caracteres que proporciona uma forma bastante 
flexível, eficiente e poderosa para o processamento de textos. Basicamente, consiste em símbolos 
de determinado alfabeto, operadores e definidores de precedências, quando fazem uso de 
parênteses.
Semelhantemente a um autômato finito, uma expressão regular representa uma linguagem regular, 
sendo possível realizar conversões entre eles, ou seja, pode-se realizar a transformação de uma 
expressão regular em um autômato finito, e vice-versa.
Conforme as regras estabelecidas na expressão, ela tem a mesma simplicidade e eficiência de uma 
linguagem regular, possibilitando a busca, a padronização e a substituição de textos.
Na área de desenvolvimento de softwares, pode-se citar exemplos de aplicações: na alteração de 
formato de datas, modificando uma data do formato norte-americano para o formato brasileiro; na 
validação de entrada de dados, verificando se uma entrada referente a um CPF (Cadastro de Pessoa 
Física) tem a combinação de três conjuntos de três símbolos cada um, separados por ponto e, ao 
final, um traço seguido por dois símbolos, etc.
No capítulo Expressões regulares, base teórica desta Unidade de Aprendizagem, compreenda, entre 
outros, sobre seus operadores, como construi-las e como convertê-las em autômatos finitos.
Boa leitura.
Laiane
Laiane
Laiane
LINGUAGENS 
FORMAIS E 
AUTÔMATOS 
OBJETIVOS DE APRENDIZAGEM
 > Definir expressões regulares e seus operadores.
 > Exemplificar a construção de expressões regulares.
 > Desenvolver o algoritmo de conversão de expressões regulares em autô-
matos finitos.
Introdução
Podemos afirmar que uma linguagem é regular se for possível refleti-la em um 
autômato finito. Entretanto, também é possível denotar uma linguagem regular 
por meio de uma expressão regular. Deste modo, considera-se que uma linguagem 
também é regular se existe uma expressão regular que a represente.
De acordo Stubblebine (2007), as expressões regulares são uma linguagem 
usada para análises e manipulação de caracteres. Elas são frequentemente apli-
cadas na realização de tarefas complexas em operações de pesquisa, substituição 
ou validação de dados.
Atualmente as expressões regulares estão presentes na maioria das linguagens 
de programação, de editores de textos, aplicativos, bancos de dados, entre outros.
Salienta-se que, conforme Lima (2020), atualmente vivemos a era da informa-
ção. Isto posto, poder possuir, difundir e gerenciar as informações representa um 
bem diferenciado e valiosíssimo em diversas esferas, como industriais, sociais e, 
inclusive, para o indivíduo comum.
Neste capítulo, você vai compreender o que são expressões regulares, quais 
operações podemos realizar com o uso delas, como construí-las e, por fim, como 
converter um autômato finito em uma expressão regular e vice-versa.
Expressões regulares
Carlos Estevão Bastos Sousa
Expressõesregulares e seus operadores
Conforme Jargas (2016), as expressões regulares são uma composição de 
símbolos, caracteres com funções especiais e caracteres literais que formam 
uma sequência, isto é, uma expressão que pode ser interpretada como uma 
regra que poderá indicar sucesso, se uma dada entrada pertencer à regra 
ou, insucesso, caso contrário. Normalmente, em linguagens de programação 
teremos como saída uma resposta semelhante, ou seja, true ou false para 
representar sucesso ou insucesso na aplicação de uma determinada cadeia 
a uma expressão regular.
Na matemática, mais precisamente na aritmética, podemos fazer uso de 
operações como adição e multiplicação a partir dos símbolos + e ×. Isto posto, 
a partir delas é possível elaborar equações como 5 × (97 + 32). De forma similar, 
também é possível representar as expressões regulares, por exemplo a* + b.
As expressões regulares podem ser aplicadas com o intuito de testar se 
uma determinada cadeia corresponde a uma expressão de busca, localizar 
caracteres em uma cadeia, substituir cadeias em um texto, processar o for-
mato de entradas, etc. Isto posto, podem ser aplicadas, por exemplo, a datas, 
os horários, números de IPs, endereços de e-mail, endereços de websites, 
entre outros.
Hopcroft, Ulman e Motwani (2003) afirmam que antes de conhecer as 
expressões regulares, faz-se necessário entender as três operações sob as 
linguagens regulares que os operadores das expressões regulares repre-
sentam. Vejamos. 
Para as operações apresentadas a seguir, considere o alfabeto Σ = {0,1} e 
as linguagens L = {01, 11} e M = {00, 01}.
 � A união de duas linguagens L e M, também representada por L ∪ M, 
tem como finalidade unir todas as cadeias presentes em ambas as 
linguagens. Deste modo, quando aplicada, L ∪ M = {01, 11, 00}. 
 � Ainda considerando as linguagens L e M, a concatenação, representada 
por LM ou L.M, consiste em formar uma nova linguagem, na qual são 
obtidas as cadeias de L e concatenadas a qualquer cadeia pertencente 
a M, uma seguida da outra. Para este caso, temos LM = {0100, 0101, 
1100, 1101}.
 � O fecho estrela ou fechamento de Kleene é uma operação unária, assim, 
considerando somente a linguagem L. Esta operação, denotada por L*, 
é uma concatenação sucessiva das cadeias de L, isto é, consiste em 
Expressões regulares2
tomar qualquer quantidade de cadeias de L, inclusive nenhuma, ou 
seja, L* = {ε, 01, 11, 0101, 0111, 1111, 1101, 010111, ...}.
Se você já utilizou algum shell do Linux ou fez alguma pesquisa 
em qualquer editor de texto que possibilite fazer buscas, há gran-
des chances de você ter utilizado alguma expressão regular. No Windows, por 
exemplo, ao entrar em qualquer diretório pelo Windows Explorer, é possível 
pesquisar por *.pdf. Perceba que neste caso você estará pesquisando todos os 
arquivos que terminam com a subcadeia .pdf, ou seja, possuem a extensão .pdf.
Em relação à precedência desses operadores, de início é utilizada a ope-
ração estrela, que possui precedência mais alta. Posteriormente, a concate-
nação, ou “ponto”, na qual deve-se sempre agrupar os símbolos existentes 
da esquerda para a direita e, finalmente, a operação de união, em que a 
ordem é pouco importante, mas costumamos agrupar também da esquerda 
para a direita.
No Quadro 1 são apresentados os símbolos que costumam ser utilizados 
e a ordem de precedência dos operadores das expressões regulares.
Quadro 1. Precedência entre operações
Operação Símbolo representante Precedência
Fecho estrela * Alta
Concatenação . Média 
União + Baixa
Ainda sobre as precedências, em casos em que não pretendemos seguir 
as apresentadas anteriormente, podemos fazer uso de parênteses, com o 
intuito de explicitar qual operação deverá ser executada primeiro. 
Vejamos um exemplo.
Expressões regulares 3
Considere a expressão ba + a + ba*. 
Normalmente determinaríamos o início pela realização da opera-
ção de fecho estrela (*) sob a em a*; posteriormente a concatenação com b, aqui 
representada apenas como ba e ba*, ou seja, b concatenado a a; posteriormente, 
b concatenado a a*; e, finalmente, a operação de união (+), unindo ba com a e 
com ba*, assim, formando a expressão ba + a + ba*. 
Diante da expressão formada, ao informarmos a precedência por parênteses 
poderíamos construir outra expressão, que apesar de similar, em muitos dos 
casos gera cadeias diferentes, como é o caso de (b(a + a) + b)a*.
Como visto, as expressões regulares são outra forma de definir lingua-
gens regulares, inclusive, segundo Hopcroft, Ulman e Motwani (2003), elas 
podem ser consideradas uma “linguagem de programação”, na qual podemos 
expressar algumas aplicações importantes como em pesquisas em textos, 
compiladores, entre outras.
Dentre os comandos de pesquisas do Unix, o grep utiliza uma notação 
semelhante às linguagens regulares. Outras notações podem ser utilizadas 
também em linguagens de programação como Java e Python, por exemplo. 
Estas são conhecidas também como RegEx (regular expressions).
Veja a expressão a seguir:
^s......e$
Neste exemplo, considere:
 � ^ como a definição de início da expressão;
 � s como o uso do símbolo s;
 � . representa a existência de qualquer símbolo;
 � e representa a existência desse símbolo; 
 � $ representa o fim da cadeia, deste modo e$ caracteriza que a cadeia 
deverá terminar com e.
Vejamos o exemplo aplicado à linguagem de programação Python, com o 
intuito de verificar se uma determinada cadeia faz parte de uma linguagem.
Expressões regulares4
import re
expressao = '̂ s......e$'
cadeia = 'software'
resultado = re.match(expressao, cadeia)
if resultado:
 print("Cadeia reconhecida.")
else:
 print("Cadeia não reconhecida.")
Salienta-se que no exemplo estamos fazendo uso do módulo re, que 
possibilita o uso de expressões regulares na linguagem Python.
Quanto a saída do código, a mesma será Cadeia reconhecida, pois 
a cadeia software pertence à linguagem definida pela expressão ^s......e$.
Construindo expressões regulares
Como apresentado anteriormente, as expressões regulares são constituídas 
pelas operações de concatenação, união e fecho estrela. A partir de um 
conjunto de símbolos advindos de um determinado alfabeto (Σ) e das ope-
rações citadas, torna-se possível construir expressões regulares; estas, por 
sua vez, representam linguagens regulares. Deste modo, possuem a mesma 
simplicidade e possibilidades de aplicações.
Conforme Hopcroft, Ulman e Motwani (2003), a álgebra das expressões 
regulares segue o mesmo padrão das álgebras de todos os tipos, isto é, inicia 
com algumas expressões elementares, normalmente fazendo uso de cons-
tantes e/ou variáveis, e aplica-as a um conjunto de operadores, geralmente 
fazendo uso de agrupadores como parênteses, por exemplo.
Considere o alfabeto Σ = {a, b}. Neste caso podemos afirmar que a e b 
são duas expressões regulares. Do mesmo modo, a + b, representam uma 
expressão regular formada pela união das expressões a e b. Nós utilizamos 
Expressões regulares 5
as expressões regulares para definir uma linguagem regular tendo como base 
a própria expressão regular, deste modo são dadas algumas definições-base, 
a seguir.
Considerando a como um símbolo qualquer, logo a é uma expressão regular 
que denota a linguagem {a}. Deste modo L(a) = {a}.
L(ε) = {ε} representa a linguagem que possui apenas o símbolo vazio e 
é denotada pela expressão ε. Deste modo, considera-se também ε como a 
expressão que contém exclusivamente a cadeia vazia. O mesmo é válido para 
L(∅) = ∅, isto é, a expressão ∅ não produz nenhuma cadeia.
Por fim, encerrando a base de construção, consideramos L, maiúscula 
e em itálico, como a variável que representa qualquer linguagem. Assim, 
considerando, por exemplo, uma expressão regular R1, L(R1) é a linguagem 
denotada por R1.
Entendida a base de uma expressão regular, conheceremos agora o pro-
cesso de indução. Neste iremos apresentar quatro etapas indutivas, sendo 
três relacionadas ao uso dos operadores e uma para o uso dosparênteses. 
Vejamos a seguir.
Considere R1 e R2. Se estas são expressões regulares, logo R1 + R2 tam-
bém é uma expressão regular, que consiste na união das primeiras, ou seja, 
a partir da união dessas expressões é possível fazer uso de qualquer cadeia 
existente em R1 e R2. Deste modo, L(R1 + R2) = L(R1) L(R2).
Vejamos um exemplo.
Considere um alfabeto que contém os símbolos a e b, ou seja, 
Σ = {a, b}. Seja a uma expressão regular R1 e b uma expressão regular 
R2, o resultado da união entre elas consiste em todas as cadeias de ambas, 
ou seja, {a, b}. 
De modo semelhante, considerando R1 e R2 como expressões regulares, 
então R1R2 também é uma expressão regular construída a partir da operação 
de concatenação, isto é, L(R1R2) = L(R1)L(R2). 
Vejamos um exemplo:
Expressões regulares6
Para um Σ = {a, b}, considere a como a expressão R1e b como R2, deste 
modo, R1R2 consiste na concatenação respectiva das expressões a 
e b, ou seja, L(R1R2) = {ab}.
Salienta-se que na operação de concatenação torna-se facultativo o uso 
do ponto. Deste modo, determinada expressão pode ser escrita tanto como 
R1R2 quanto como R1.R2, e ambas possuirão o mesmo sentido. No entanto, 
normalmente utiliza-se a primeira expressão apresentada, ou seja, sem o 
uso de ponto.
Normalmente optamos por representar a operação de concatena-
ção sem a utilização do ponto (.), pois, como vimos, em diversas 
linguagens de programação este possui um significado diferente. Em Java, 
JavaScript e Python, por exemplo, o sinal de ponto pode representar a utilização 
de qualquer caractere.
Dada uma expressão regular R1, a expressão R *
1 também será uma expressão 
regular composta a partir da operação fecho estrela ou fechamento de R1, 
isto é, L(R*
1) = (L(R1))*.
Vejamos um exemplo:
Para um Σ = {a, b}, considere a como a expressão que denota R1, 
desse modo, ao aplicar a operação de fechamento em R1, teremos 
L(R*
1) = {ε, a, aa, aaa, ...}.
Por fim, para uma expressão regular R1, (R1), a R1 entre parênteses também 
é uma expressão denotada pela mesma linguagem de R1, isto é, L((R1)) = L(R1).
Conforme vimos, a operação de fechamento tem precedência sobre a 
operação de concatenação. Deste modo, ao considerar a expressão aa*, sua 
resolução é dada como se segue:
Expressões regulares 7
 � Passo 1: Consideramos inicialmente a expressão a*, pois ela possui 
precedência sob a concatenação, e tem como resultado {ε, a, aa, aaa, 
...}, isto é, qualquer quantidade de a, inclusive nenhuma. 
 � Passo 2: Considere ainda aa*. O fragmento da expressão representada 
por a à esquerda representa, neste caso, uma unidade de a no início 
de qualquer cadeia formada por R1. Assim, concatenamos uma unidade 
de a a qualquer quantidade de a, apresentado no Passo 1. Deste modo, 
é possível produzir cadeias como {a, aa, aaa, ...}.
De outro modo, ao fazer uso de parênteses na expressão R2 como (aa)*, 
deverá ser resolvida primeiro a operação de concatenação, pois está entre 
parênteses, e, posteriormente, a de fechamento. Isto é, o resultado consiste 
em {ε, aa, aaaa, aaaaaa, ...}, ou seja, nenhuma ou uma quantidade par de 
símbolos a, o que torna R1 ≠ R2. Vejamos:
 � Passo 1: Considere a expressão R2 = (aa)*. O primeiro passo é considerar 
os operadores a de forma individual, deste modo, ao efetuar a operação 
de concatenação sob eles, o resultado consistirá em aa.
 � Passo 2: Aprendemos que a operação de fechamento, quando aplicada 
a algum símbolo ou conjunto de símbolos, possui como resultado 
qualquer quantidade deste, inclusive nenhuma. Isto posto, ao aplicar a 
operação de estrela sob aa, teremos nenhuma (ε) ou várias representa-
ções de aa concatenadas. Deste modo, L(R2) = {ε, aa, aaaa, aaaaaa, ...}.
Com base no exposto, e no Σ = {a, b}, vejamos alguns exemplos no Quadro 2.
Quadro 2. Exemplificação de expressões regulares e seus significados
Expressão regular Linguagem 
ab Possibilita a leitura apenas da cadeia ab por meio da 
operação de concatenação.
ab* Possibilita a leitura de qualquer cadeia iniciada pelo 
símbolo a seguido por qualquer quantidade de b, 
inclusive nenhum. 
Neste exemplo é feito uso da operação de 
concatenação e fechamento. 
(Continua)
Expressões regulares8
Expressão regular Linguagem 
(a + b)* Possibilita a leitura vazia (ε) ou de qualquer cadeia 
que contenha os símbolos a ou b.
Neste exemplo são utilizadas as operações de união 
e fechamento. De forma implícita, temos a operação 
de concatenação, pois a operação de fechamento 
consiste em uma generalização da concatenação.
b(a + b)* a Possibilita a leitura de todas as cadeias que iniciam 
com b e terminam com a.
Vejamos agora um exemplo de problema que consiste em, com base em 
uma linguagem regular, construir a expressão regular que a denote. 
Considere L1 como uma linguagem regular de forma que {w ∈ Σ*, com 
Σ = {0,1} | |w| é múltiplo de 7}.
Para a resolução deste problema, inicialmente, faz-se necessário entendê-lo. 
Desse modo, consideramos w como qualquer cadeia pertencente a Σ = {0, 1}, 
ou seja, qualquer cadeia que possui combinações dos símbolos 0 e 1. Por fim, 
solicita-se também que o comprimento de w seja múltiplo de 7. 
Vejamos a resolução:
Ao considerar Σ como qualquer símbolo pertencente ao alfabeto, ou seja, 0 e 1, 
para construirmos a expressão regular, com cadeias de tamanho de comprimento 
múltiplo de sete, podemos começar pelo caso-base, que é uma expressão de 
comprimento sete. Assim temos:
ΣΣΣΣΣΣΣ
Por fim, considerando que 0 é múltiplo de qualquer número, podemos inserir 
a operação de fecho estrela sobre a expressão elaborada para o caso base. 
Assim, temos qualquer quantidade da expressão inserida entre parênteses.
(ΣΣΣΣΣΣΣ)*
Note que nesta expressão regular é possível produzir cadeias como 
{ε, 0000000, 1111111, 00000000000000, 00000001111111, ...}.
(Continuação)
Expressões regulares 9
Convertendo expressões regulares em 
autômatos finitos
Anteriormente vimos que toda linguagem regular pode ser representada por 
uma expressão regular. Dito isto, se R é uma expressão regular, então L(R) 
é uma linguagem regular; assim, se L é uma linguagem regular, então existe 
uma expressão R tal que L(R) = L.
Para Menezes (2000), as expressões regulares tratam-se de um formalismo 
denotacional e gerador, pois é possível tanto inferir como construir cadeias 
de uma dada linguagem. Sipser (2007) afirma que as expressões regulares e 
os autômatos finitos possuem equivalência. Vejamos.
Expressões regulares e autômatos finitos são equivalentes em seu poder descri-
tivo. Esse fato é surpreendente porque autômatos finitos e expressões regulares 
aparentam superficialmente ser bastante diferentes (SIPSER, 2007, p. 68).
Levando em consideração que tanto os autômatos finitos quanto as ex-
pressões regulares denotam linguagens regulares, é possível que haja a 
necessidade da conversão entre essas duas formas. Deste modo, a seguir 
vamos compreender como funciona a conversão de uma expressão regular 
para um autômato finito.
Convertendo expressões regulares 
para autômatos finitos
A realização da conversão de expressões regulares para autômatos finitos será 
apresentada a partir do algoritmo Thompson (1968), também conhecido como 
algoritmo de construção de Thompson. Para a conversão, faz-se necessário 
compreender os casos-base. Com esse conhecimento, é possível aplicar os 
casos-base a casos mais complexos e obter a solução desejada. Salienta-
-se que, como forma de tornar a conversão um processo mais simples, será 
explanada a conversão de uma expressão regular para um autômato finito 
não determinístico de movimentos vazios (AFNε), o qual pode ser facilmente 
convertido para um autômato finito não determinístico (AFN) ou para um 
autômato finito determinístico (AFD).
Iniciaremos entendendo o processo de conversão a partir das expressões-
-base, ou seja, do uso de símbolos isolados, ε e ∅. Posteriormente apresen-
taremos como fazer a combinação desses autômatos com o intuito de formar 
autômatos maiores e que aceitamas operações de união, concatenação e 
fechamento estrela. Vejamos.
Expressões regulares10
Caso-base 1
Para o primeiro caso, considere a a expressão R, apresentada na Figura 1.
Figura 1. R = a.
Note que a linguagem regular é composta apenas por a, ou seja, L(R) = {a}, 
assim, podemos representá-la com um autômato com apenas uma transição 
do estado inicial para o estado final fazendo a leitura do símbolo a.
Caso-base 2
Para o segundo caso, considere ε como a expressão R, assim, podemos 
representá-la de acordo com a Figura 2.
Figura 2. R = ε.
Neste caso, temos uma linguagem que aceita apenas a cadeia vazia, assim, 
deve possuir um estado inicial e estado de aceitação com ligação entre eles a 
partir de uma transição ε, podendo, ainda, como representando na Figura 2, 
fazer uso do mesmo estado como inicial e de aceitação.
Caso-base 3
Para o terceiro caso, a expressão R = ∅; podemos representá-la de acordo 
com a Figura 3.
Figura 3. R = ∅.
Expressões regulares 11
Para uma expressão vazia, representamos um autômato que não aceita 
nenhum símbolo, ou seja, não há um estado de aceitação.
Como visto, há três partes que representam a base da construção de um 
autômato. Neste momento, baseados nas partes citadas, iremos conhecer 
as três partes da indução. Vejamos.
Caso indutivo 1: Operação de união
Considere duas expressões regulares R1 e R2, denotadas por a e b, nas 
quais L(M1) = L(R1) e L(M2) = L(R2), representadas pelos autômatos finitos apre-
sentados na Figura 4.
Figura 4. R1 = a e R2 = b.
Ao aplicar a operação de união sob as duas expressões, R1 + R2, temos 
como resultado um autômato como o apresentado na Figura 5.
Figura 5. R1 + R2.
Atente-se ao fato de que é criado um novo estado inicial, o qual possui 
transições vazias para cada estado inicial anteriormente existente em R1 e R2.
Caso indutivo 2: Concatenação
Ainda sob as expressões R1 e R2, para concatená-las inserimos os autô-
matos, dispostos tal qual a expressão R1R2, e posteriormente os ligamos a 
partir de uma transição ε. O resultado dessa ação é apresentado na Figura 6.
Expressões regulares12
Figura 6. R1R2.
Note que para a concatenação é necessário seguir a ordem dos símbolos 
utilizados na expressão regular.
Caso indutivo 3: Fecho de Kleene (operação estrela) ou concatenação sucessiva
Nesta operação, ocorre uma transformação de modo a aceitar símbolos 
vazios ou uma concatenação encadeada do símbolo contido em R1. Na Figura 7 
é apresentada uma representação dessa operação.
Figura 7. Fecho estrela em a.
Perceba que nesta operação há a leitura vazia (ε) ou de um ou mais sím-
bolos a.
Após conhecidos os casos-base e os passos de indução, vejamos um 
exemplo de sua aplicação.
Considere a expressão regular (ab*) + a. Para construirmos um autômato 
para esta expressão, devemos inicialmente criar um autômato finito que 
represente as expressões a e b, conforme apresentado anteriormente na 
Figura 4.
Posteriormente, como sabemos, o operador estrela possui precedência 
mais alta, assim, seguindo o caso 6, aplicamos a operação estrela em b, tendo 
como resultado o disposto na Figura 8.
Expressões regulares 13
Figura 8. Fecho estrela em b.
Posteriormente aplicamos a operação de concatenação da expressão a 
com b*, formando a expressão ab*, dada pela Figura 9.
Figura 9. ab*.
E, por fim, aplicamos a operação de união à expressão ab* com a, isto é, 
(ab*) + a, representada na Figura 10.
Figura 10. (ab* ) + a.
Conforme apresentado, as conversões de expressões regulares para au-
tômatos finitos geram um AFNε, ou seja, não produzem um autômato finito 
Expressões regulares14
com o menor número de estados; para isto, após o processo de conversão, 
é possível converter o autômato resultante em um AFD ou AFN e, posterior-
mente, aplicá-lo a um processo de minimização de estados. 
Convertendo autômatos finitos em 
expressões regulares
Conforme Sipser (2007), o processo de conversão de autômatos finitos 
para expressões regulares requer a aplicação de algumas transformações, 
de forma que, ao final, tenhamos apenas dois estados: um estado inicial e um 
estado de aceitação. Ao final, a transição desse autômato conterá a expressão 
regular referente ao autômato inicial.
Para esta conversão, utilizaremos o método por eliminação de estados. 
Antes de começarmos a utilizar esse método, vejamos alguns casos que 
precisamos conhecer para realizar o processo de conversão.
Caso 1
Se um autômato finito possuir alguma transição com destino ao estado 
inicial, este estado não deverá ser mais o inicial; deste modo, será criado 
outro estado, que possuirá uma transição ao estado inicial anterior, a partir 
de uma transição vazia. Essa transformação é apresentada na Figura 11.
Figura 11. Inserção de um estado e alteração do estado inicial.
Caso 2
Se existir um estado final no qual existe uma transição saindo dele, deverá 
ser criado outro estado final, substituindo o anterior, com uma transição 
do estado final anterior para ele. Analise essa transformação na Figura 12.
Figura 12. Inserção de um estado e alteração do estado final.
Expressões regulares 15
Caso 3
Se existir um autômato finito com mais de um estado final, estes não 
deverão ser considerados estados finais; assim, outro estado de aceitação 
será criado, e os estados finais anteriores possuirão uma transição vazia até 
ele. Essa transformação é ilustrada na Figura 13.
Figura 13. Inserção de um estado e alteração no conjunto de estados finais.
Caso 4
Por fim, o procedimento de conversão consiste em remover todos os 
estados, com exceção dos estados inicial e final, de modo que a linguagem 
produzida se mantenha a mesma.
Vejamos um exemplo apresentado na Figura 14.
Figura 14. Transformação de um autômato finito para uma expressão regular.
Expressões regulares16
Ao analisar a Figura 14, perceba que a conversão consiste em seis etapas.
 � Etapa 1: temos o autômato original.
 � Etapa 2: retiramos o estado q1, e a transição do símbolo a passa a ser 
direcionada ao estado final, q5. 
 � Etapa 3: removemos o estado q3, e a transição de q2, com o símbolo 
b, passa a ser direcionada ao estado q5.
 � Etapa 4: retiramos o estado q4, e a transição de q2, com o símbolo a, 
passa a ser direcionada ao estado q5.
 � Etapa 5: removemos o estado q2, isto é, temos uma união de bb com 
ba, representada por bb + ba.
 � Etapa 6: por fim, unimos a transição a com a transição bb + ba, finali-
zando a construção da expressão regular com a + bb + ba.
Vejamos agora uma resolução, apresentada na Figura 15, que possui as 
operações de união, concatenação e fecho de Kleene.
Figura 15. Transformação de um autômato finito para uma expressão regular.
Vejamos nas cinco etapas a seguir o processo de conversão apresentado 
na Figura 15.
 � Etapa 1: o autômato é apresentado.
Expressões regulares 17
 � Etapa 2: verificou-se que o autômato possui dois estados de aceitação, 
sendo que um deles (q2) possui transição para si mesmo. Deste modo, 
é introduzido outro estado de aceitação q4 e retirada a função de 
aceitação dos anteriores (q2 e q3).
 � Etapa 3: é excluído o estado q2, assim, temos uma concatenação de b 
com b*, elaborando a expressão bb*.
 � Etapa 4: é retirado o estado q1, neste sentido, as transições referentes 
a b, a* e bb* são concatenadas, isto é ba*bb*.
 � Etapa 5: por fim, é retirado o estado q3, gerando a expressão a + 
(ba*bb*).
Neste capítulo você aprendeu um pouco sobre expressões regulares, 
exemplos de aplicação, sua equivalência com autômatos finitos e como fazer 
a conversão de expressões regulares para autômatos finitos e vice-versa. 
Referências
HOPCROFT, J. E.; MOTWANI, R.; ULLMAN, J. D. Introdução à teoria de autômatos, linguagens 
e computação. Rio de Janeiro: Campus; Elsevier, 2003. 560 p.
JARGAS, A. M. Expressões regulares: uma abordagem divertida. 5. ed. São Paulo: 
Novatec, 2016. 248 p.
LIMA, E. S. Expressões regulares: conceitos, usos e aplicações na web. Rio Branco: 
Edição do autor, 2020. 74 p. (Série AprendaSozinho, 1).
MENEZES, P. B. Linguagens formais e autômatos. 6. ed. Porto Alegre: Bookman, 2011. 
256 p. (Série Livros Didáticos Informática UFRGS, 3).
SIPSER, M. Introdução à teoria da computação. São Paulo: Cengage Learning, 2007. 459 p.
STUBBLEBINE, T. Regular expression pocket reference: regular expressions for Perl, 
Ruby, PHP, Python, C, Java and .NET. 2. ed. Sebastopol: O’Reilly, 2007. 117 p.
THOMPSON, K. Programming techniques: regular expression search algorithm. Com-
munications of the ACM, New York, v. 11, n. 6, p. 419–422, June 1968.
Leituras recomendadas
CRITCHLOW, C.; ECK, D. J. Regular expressions. In: CRITCHLOW, C.; ECK, D. J. Foundations 
of computation. Davis: LibreTexts; University of California, 2020. p. 100–101. Disponível 
em: https://eng.libretexts.org/Bookshelves/Computer_Science/Book%3A_Founda-
tions_of_Computation_(Critchlow_and_Eck)/03%3A_Regular_Expressions_and_
FSA's/3.02%3A_Regular_Expressions. Acesso em: 28 jan. 2021.
FITZGERALD, M. Introdução às expressões regulares: desvendando as expressões 
regulares, passo a passo. São Paulo: Novatec; O’Reilly, 2012. 160 p.
Expressões regulares18
GOYVAERTS, J.; LEVITHAN, S. Regular expressions cookbook: detailed solutions in eight 
programming languages. 2. ed. Sebastopol: O’Reilly, 2012. 612 p.
MENEZES, P. B. Linguagens regulares: expressões regulares. In: MENEZES, P. B. Linguagens 
formais e autômatos. 6. ed. Porto Alegre: Bookman, 2011. p. 93–106.
Os links para sites da web fornecidos neste capítulo foram todos 
testados, e seu funcionamento foi comprovado no momento da 
publicação do material. No entanto, a rede é extremamente dinâmica; suas 
páginas estão constantemente mudando de local e conteúdo. Assim, os editores 
declaram não ter qualquer responsabilidade sobre qualidade, precisão ou 
integralidade das informações referidas em tais links.
Expressões regulares 19
Dica do professor
Conforme Critchlow e Eck (2020), uma expressão regular é uma maneira de descrever uma 
estrutura gramatical de símbolos de determinado idioma fazendo uso de formalismos matemáticos. 
De um ponto de vista mais simples, pode-se afirmar que uma expressão regular faz uso de 
determinados símbolos de um alfabeto (Σ) que, a partir de operações de concatenação, união e 
fecho estrela, possibilitam a busca e o gerenciamento de textos de acordo com determinado 
padrão.
Na computação, as expressões regulares, também conhecidas como regex (regular wxpression), são 
muito úteis em diversos cenários de processamento de textos. Elas costumam ser utilizadas para 
uma série de funções, como é o caso de formulários da web para validar determinada entrada de 
dados, reconhecer padrões, realizar buscas e alterações em dados, entre outras.
Conforme Jargas (2016), as expressões regulares surgiram como parte de um editor de textos. No 
entanto, décadas depois, houve um crescimento em sua utilização, de modo que elas passaram a 
ser utilizadas em diversos outros programas, como é o caso dos editores de textos como Vim e 
Emacs, e na programação, em linguagens como Go, Java, C#, Python e Javascript.
Na Dica do Professor, você aprenderá como utilizar expressões regulares, a partir da linguagem de 
programação Javascript, com o intuito de buscar padrões em respostas a comentários em um 
formulário web produzido em HyperText Markup Language (HTML).
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
https://fast.player.liquidplatform.com/pApiv2/embed/cee29914fad5b594d8f5918df1e801fd/0da663fb453e39f3497903bf138602d7
Exercícios
1) Determinada empresa Z pretende criar os e-mails institucionais de seus funcionários. Para 
isso, ela visa a fazer uso de expressões regulares. Assim, considerando uma cadeia qualquer 
w, faz-se necessário elaborar e-mails do tipo w@empresaZ.com, de forma que |w| tem 
tamanho mínimo igual a 1 e máximo igual a 4.
Tendo em conta um alfabeto Σ = {a, b}, um funcionário da empresa elaborou, então, uma 
expressão regular da seguinte forma 
(a + b)(ε + a + b)(ε + a + b)(ε + a + b). Tendo em vista o alfabeto, 
a expressão e as orientações dadas, informe quantas possibilidades existem para criação de 
e-mails.
A) 36.
B) 48.
C) 30.
D) 26.
E) 46.
2) Existem diversas maneiras de representar determinada linguagem regular, seja por 
autômatos finitos, seja por expressões regulares. Ao optar pela segunda, ainda assim, há 
diversas possibilidades capazes de originar uma mesma linguagem.
Tendo em vista o informado e o alfabeto Σ = {0,1}, considere a expressão 0 * (100) * (0 * 
(100) *) * e informe qual das opções a seguir produz o mesmo conjunto de cadeias:
A) (0100)*
B) (0100)*(0100)*
C) 0*1*0*0*0*1*0*0*
D) (0100)*+(0100)*
E) (0 + 100)*
Laiane
Laiane
Laiane
Considerando 0 * (100) * (0 * (100) *) *, é possível perceber que a expressão basicamente consiste em operações de concatenação e fechamento.É possível alterar a expressão dada por.(0 * (100) *) + (0 * (100) *) *.Ao analisar a expressão alterada, pode-se perceber que (0 * (100) *) e (0 * (100) *) * produzem as mesmas cadeias; assim, é possível excluir uma das extremidades.Ao escolher (0 * (100) *) *, resta (0 * (100) *), que pode ser transformada em (0 +100) *, produzindo, ainda assim, o mesmo conjunto de cadeias.
Laiane
A partir da expressão (a + b)(ε + a + b)(ε + a + b)(ε + a + b), considerando 2 símbolos do alfabeto e, respectivamente, cadeias de tamanho 4, 3, 2 e 1, tem-se que:24 + 23 + 22 + 21 = 30Desse modo, é possível obter as seguintes cadeias: {a, b, aa, bb, ab, ba, aaa, aab, abb, aba, bbb, baa, bab, bba, aaaa, aaab, aabb, aaba, abbb, abab, abaa, abba, bbbb, bbba, bbaa, bbab, baaa, baba, babb, baab}.
3) As linguagens regulares podem ser denotadas por autômatos finitos ou expressões regulares. No 
primeiro caso, ou seja, com relação aos autômatos finitos, podem ser representadas por um 
conjunto de estados, um conjunto finito de símbolos, o qual chamamos de alfabeto, uma função de 
transição, um estado inicial e, por fim, apenas um ou um conjunto de estados finais. No segundo 
caso, as expressões regulares costumam ser representadas por um conjunto de símbolos de um 
alfabeto, símbolos que representam operações (concatenação, fecho estrela e união) e por 
parênteses, com o intuito de definir uma precedência.
Há casos em que a representação de uma linguagem regular a partir de um autômato finito se 
torna a melhor opção, pois, de acordo com o problema, ela apresenta um formato de interpretação 
mais simples. No entanto, há momentos em que a expressão regular se torna indispensável. Desse 
modo, é possível converter um autômato finito em uma expressão regular.
Tendo em vista o apresentado, analise o autômato a seguir e informe quais expressões regulares 
poderão denotar a mesma linguagem:
Considere: 
I. (ab*a+ba*b)a*baa +(ab*a+ba*b)a*bbb 
II. (a+b)(b+a)*(a+b)a*b(a+b)(a+b) 
III. (ab*a + ba*b)a*b(aa + bb) 
IV. (ab*a)+(ba*+b)*ab(aa)+(bb)
Entre as opções, estão corretas apenas:
A) I e II.
B) I e III.
C) II e III.
D) II e IV.
E) III e IV.
4) As expressões regulares são uma maneira formal de descrever linguagens regulares a partir 
de conjuntos de símbolos e/ou caracteres especiais que formam determinada regra a partir 
de operadores de concatenação, união e fecho estrela.
Dado o exposto, considerando um alfabeto Σ = {a, b} e uma linguagem L = {w ∈ Σ |(anbm) na 
qual n > 1 e m ≤ 1}, marque a alternativa que representa o complemento da linguagem dada 
por meio de uma expressão regular.
A) aa* + (b + ε).
B) (a + ε)*(b + ε).
C) (a*)bbb*.
D) (a + aa + aaa + ε)* b*.
E) (a + ε)bbb*.
5) As expressões regulares são utilizadas para denotar linguagens regulares. A partir delas, é 
possível fazer uso de operações de maneira bastante simples e sucinta. Quando utilizadas 
em linguagens de programação, normalmente são aplicadas com o intuito de verificar, por 
meio de determinada regra, se um conjunto de símbolos pertence a determinado padrão. 
Desse modo, pode-se inferir que estas podem ser utilizadas para verificarse determinada 
entrada corresponde a um padrão válido, como um e-mail.
Dado o exposto, considerando um alfabeto Σ = {a, b} e uma expressão regular (a + b) * a (a + 
b) * a (a + b) *, marque a alternativa que melhor representa a expressão apresentada.
A) Conjunto de todas as cadeias que têm ao menos um b.
B) O conjunto de todas as cadeias contendo a subcadeia aa.
C) O conjunto de todas as cadeias contendo no máximo dois a’s.
Laiane
Laiane
Laiane
O complemento é uma operação de fechamento sob linguagens regulares. Desse modo, quando aplicada a uma linguagem regular, essa expressão produz uma nova linguagem regular.Considerando n > 1 e m ≤ 1, o complemento são todos os valores que não correspondem a estes, ou seja n ≤ 1 e m > 1; assim, ao considerar a expressão anbm, temos inicialmente uma quantidade de a’s de no máximo 1 e uma quantidade de b’s de no mínimo 2.A partir do exposto, tem-se que:Para aa* + (b + ε), pode-se fazer uso da cadeia aaaaa, o que quebra a regra de n ≤ 1 e m > 1.Para (a + ε)*(b + ε), pode-se fazer uso da cadeia aaab, o que também quebra a regra n ≤ 1 e m > 1.Em (a*)bbb*, pode-se dispor de qualquer quantidade de a e, no mínimo, duas quantidades de b, o que também quebra a regra dada.Na expressão regular (a + aa + aaa + ε)* b*, pode-se fazer uso da cadeia bbbb, que também não corresponde à regra informada.Por fim, Para (a + ε)bbb*(a+ε), representa a leitura de apenas um ou nenhum a, ou seja, n ≤ 1 e bbb* torna obrigatória a leitura de ao menos dois b’s, isto é, m > 1.Desse modo, a opção correta é (a + ε)bbb*.
Laiane
Considerando o estado inicial do autômato, ao efetuar a leitura e ir para o estado q1 e, posteriormente, q5, tem-se que: ab*a.Em outro sentido, ao optar o caminho do estado q0 para q4 e, posteriormente, q5, temos que b*ab. Desse modo, obtém-se a primeira parte da expressão regular:(ab*a + ba*b).Dando sequência, no estado q5, temos a leitura de qualquer quantidade de a; assim, a* e, indo para q2, uma leitura obrigatória de b. Desse modo:(ab*a + ba*b)a*b.Nesse ponto, ao chegar a q2, há duas possibilidades. Seguir para o caminho q3 e posteriormente finalizar em q8, ou seguir a leitura para q6 e finalizar em q8. Desse modo, pode-se representar da seguinte maneira:(ab*a + ba*b)a*baa + (ab*a + ba*b)a*bbbou​​​​​​​(ab*a + ba*b)a*b(aa + bb).
D) O conjunto de todas as cadeias contendo pelo menos dois a’s.
E) O conjunto de todas as cadeias que começam e terminam com a ou b.
Laiane
Laiane
Quanto às opções, tem-se:Conjunto de todas as cadeias que têm ao menos um b — perceba que é possível a elaboração da cadeia babab deste, o que torna essa afirmativa incorreta.O conjunto de todas as cadeias contendo a subcadeia aa — realmente há a possibilidade de formar cadeias de modo a existir a subcadeia aa; no entanto, tal qual citado anteriormente, a cadeia babab faz parte da linguagem, o que torna essa opção incorreta.O conjunto de todas as cadeias contendo no máximo dois a’s — a partir da expressão dada, é possível obter a cadeia aaaa, o que a torna incorreta.O conjunto de todas as cadeias contendo pelo menos dois a’s — de fato, a expressão torna obrigatória a leitura de pelo menos dois a’s: perceba em (a + b) * a (a + b) * a (a + b) *.O conjunto de todas as cadeias que começam e terminam com a ou b — perceba que, a partir do momento que existe a obrigatoriedade do uso de no mínimo dois a’s, essa afirmativa já se torna falsa, pois não é possível gerar a cadeia ab, por exemplo.
Na prática
As expressões regulares caracterizam-se por compreenderem um 
fluxo de caracteres representando alguma regra. Desse modo, a partir 
de operações de concatenação, união e fechamento, é possível gerar diversas regras que permitem 
a busca e o gerenciamento de padrões 
em textos.
Nesse contexto, essas expressões podem ser utilizadas nas 
mais diversas aplicações, como bancos de dados, linguagens de programação, softwares editores de 
textos, prompts de comando, 
entre outras. Quanto ao gerenciamento que disponibilizam, é possível, por exemplo, fazer buscas 
com determinado padrão, substituições 
em textos, validações, entre outros.
Um exemplo prático consiste na verificação de datas, com o intuito 
de analisar se determinada entrada, inserida por um usuário qualquer, tem o padrão dia, mês e ano 
separados por barra (/) e que o atributo 
ano consiste em quatro caracteres. Desse modo, é possível obter qualquer dada existente em um 
conjunto de dados ou simplesmente transformá-los em outro padrão.
Neste Na Prática, você compreenderá como gerar uma expressão regular que identifique o 
Cadastro Nacional de Pessoa Física (CPF) e Cadastro Nacional da Pessoa Jurídica (CNPJ) de acordo 
com o padrão dado e, também, fazendo uso da linguagem de programação Javascript, uma das mais 
utilizadas atualmente quando falamos de desenvolvimento web. Salienta-se que neste Na Prática o 
uso das linguagens regulares tem o objetivo de apenas verificar o formato do CPF, e não a sua 
validação, a qual é obtida a partir de uma série de cálculos não realizáveis a partir das linguagens 
trabalhadas. 
 
Aponte a câmera para o 
código e acesse o link do 
conteúdo ou clique no 
código para acessar.
https://statics-marketplace.plataforma.grupoa.education/sagah/7ffcb374-b111-478a-a9c0-3562eb26d6f3/608cdbb7-29f8-40d0-8378-aefd8286feb7.png
Saiba +
Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do professor:
Linguagem de expressões regulares – referência rápida
Veja neste site algumas expressões usadas pelos programadores.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
RegExp (Expressões Regulares) // Dicionário do Programador.
Neste vídeo, são apresentados a história, o conceito e a maneira como as expressões regulares 
passaram a ser usadas em computação.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
Aprenda tudo sobre RegEx em menos de 10 minutos! Com 
exemplos práticos!
Neste vídeo, é apresentada a praticidade das expressões regulares em computação, 
necessariamente na programação de rotinas que buscam filtrar e definir padrões textuais em 
linguagem natural.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
https://docs.microsoft.com/pt-br/dotnet/standard/base-types/regular-expression-language-quick-reference
https://www.youtube.com/embed/IVcbytKjL4U
https://www.youtube.com/embed/d2uqo6PhdM4