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

Expressões Regulares Básicas

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

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}:

Verificação algorítmica

Exemplos de cadeias descritas/geradas

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”

1. Analogia com um “while” de C, Java ou Python.
2. A quantidade de repetições é não-determinística – 0 ou mais

Exemplos no alfabeto {a, b, c}:

Operadores de Expressões Regulares