2.4 Expressões regulares (ERs)
Formam outro modelo computacional para representar linguagens. Porém, operam de
modo diferente dos autômatos – nas ERs não existe um processo de aceitação e rejeição.
Duas visões sobre ERs:
- Ao invés de aceitar, elas denotam/expressam as cadeias da linguagem (mas não
expressam diretamente as que não são da linguagem).
- Outra visão é que elas são como um tipo de modelo matemático de algoritmo
que não recebe entrada, mas gera alguma cadeia de saída de forma não-
determinística, a cada execução. Apenas as cadeias que podem ser geradas (em
alguma execução) são da linguagem.
Dada uma expressão regular r qualquer, representamos como L(r) o conjunto de cadeias
(linguagem) que ela gera.
Formamos expressões regulares para algum alfabeto usando:
- Três tipos de expressões básicas
- Três operadores
Vamos explicar cada um desses seis casos de duas formas: como representação de
cadeias e como um algoritmo que gera cadeias não-deterministicamente.
Expressões Regulares Básicas editar
Para evitar confusão entre essas duas últimas expressões, vamos chamar de expressão
vazia ou expressão cadeia vazia (pois ela descreve apenas esta cadeia) e vamos chamar
de expressão nula (pois ela não descreve nenhuma cadeia).
Operadores de Expressões Regulares editar
Assumindo que r e s são expressões regulares quaisquer. A partir delas, todas as
operações formadas com os operadores abaixo também são expressões regulares.
Operador de concatenação: r.s ou rs
- Representa todas as cadeias formadas pela concatenação de alguma
cadeia de r com alguma cadeia de s. Usando o operador o de
concatenação de linguagens (visto nas primeiras aulas), podemos
representar assim:
L(rs) = L(r) o L(s)
- Visão algorítmica: dá a idéia de “gere uma cadeia usando r, depois gere
uma cadeia usando s”. Neste caso, a cadeia de saída será a cadeia
produzida por r seguida (concatenada) da cadeia produzida por s.
Exemplos no alfabeto {a, b, c, d}:
Operador estrela: r*
Representa as cadeias expressas por r concatenada com ela mesma “zero
ou mais vezes” (ou seja, “nenhuma vez ou uma vez ou várias vezes”).
- Visão algorítmica: ela é como um comando “repita qualquer quantidade
de vezes (pode ser nenhuma): gere uma cadeia usando r”
- Analogia com um “while” de C, Java ou Python.
- A quantidade de repetições é não-determinística – 0 ou mais
Exemplos no alfabeto {a, b, c}:
