A maior rede de estudos do Brasil

Grátis
271 pág.
Apostila LF

Pré-visualização | Página 4 de 49

de 0’s.
(2) A palavra começa com uma quantidade arbitrária de 1’s, depois segue o
padrão do item anterior.
(3) A palavra começa com uma quantidade arbitrária de repetições da sequên-
cia 011 e continua como um dos padrões anteriores.
19
20 2. EXPRESSÕES REGULARES
Esta listagem de padrões ainda não descreve todas as palavras de L(A) e,
mesmo assim, já começa a ficar bastante extensa. É importante então buscarmos
uma notação uniforme e compacta que nos permita descrever exatamente a lingua-
gem aceita por um AFD.
2. Expressões Regulares
Seja Σ um alfabeto e seja
Σ˜ = Σ ∪ {∪, ·, ∗, (, ), ∅, ε}.
Consideraremos o conjunto Σ˜ como um outro alfabeto, uma extensão de Σ. Além
disso, ∪, ·, ∗, (, ), ∅, ε serão considerados apenas como símbolos (isto é, seu signi-
ficado será ignorado) quando estiverem posando de elementos de Σ˜.
DEFINIÇÃO 2.2. Uma expressão regular (abreviada como ER) sobre o alfa-
beto Σ é uma palavra no alfabeto Σ˜, construída recursivamente pela aplicação
sucessiva das seguintes regras:
(1) se σ ∈ Σ então σ é uma expressão regular;
(2) ∅ e ε são expressões regulares;
(3) se r1 e r2 são expressões regulares, então (r1 ∪ r2) e (r1 · r2) também
são;
(4) se r é uma expressão regular, então r∗ também é;
(5) Nada mais é considerado expressão regular.
EXEMPLO 2.3. Seja Σ = {0, 1}. Então, r1 = (((((0)∗.0).1).(1)∗) ∪ (0.0))
é uma expressão regular sobre Σ. Por outro lado, r2 = (1.(1)∗∪) não é uma
expressão regular, pois o operador ∪ deve conter expressões regulares de ambos os
lados, de acordo com a regra (3) acima.
Para diminuir o uso de parênteses que não sejam necessários, adotamos uma
convenção de precedência entre os operadores que podem aparecer nas expressões
regulares (∗,. e ∪). O operador ∗ é o de maior precedência, seguido do operador
., sendo o operador ∪ o de menor precedência. Outra convenção que adotamos
2. EXPRESSÕES REGULARES 21
é a omissão do operador . nas expressões regulares, assim como o operador . de
multiplicação é geralmente omitido em expressões algébricas.
EXEMPLO 2.4. A expressão regular r1 do exemplo acima pode ser re-escrita,
de acordo com nossas convenções, como r′1 = 0∗011∗ ∪ 00.
Uma expressão regular sobre Σ representa uma linguagem L ⊆ Σ∗. Se r é
uma ER, denotamos por L(r) a linguagem representada ou denotada ou gerada
por r.
DEFINIÇÃO 2.5. Dada uma expressão regular r sobre Σ, podemos definir a
linguagem L(r) recursivamente a partir das seguintes regras.
(1) Se σ ∈ Σ, então L(σ) = {σ};
(2) L(∅) = ∅;
(3) L(ε) = {ε};
(4) L(r1 ∪ r2) = L(r1) ∪ L(r2);
(5) L(r1.r2) = L(r1).L(r2);
(6) L(r∗) = L(r)∗
EXEMPLO 2.6. Voltando ao exemplo que utilizamos como motivação no iní-
cio deste capítulo, vamos descrever cada um daqueles três padrões de palavras que
foram escritos em português naquela seção utilizando agora a notação das expres-
sões regulares.
(1) Para descrever a ocorrência de um número arbitrário de 0’s, podemos
utilizar a expressão regular 0∗, uma vez que
L(0∗) = L(0)∗ = {0}∗ = {ε, 0, 00, 000, . . .}.
Analogamente, para descrever uma quantidade par qualquer de 0’s, pode-
mos utilizar a expressão regular (00)∗. Logo, para descrever uma quanti-
dade ímpar qualquer de 0’s, podemos utilizar a expressão regular (00)∗0.
Desta forma, o primeiro padrão descrito no início do capítulo pode ser
representado pela expressão regular r1 = (00)∗010∗.
22 2. EXPRESSÕES REGULARES
(2) O segundo padrão pode ser representado pela expressão regular r2 =
1∗(00)∗010∗.
(3) O terceiro padrão pode ser representado pela expressão regular r3 =
(011)∗1∗(00)∗010∗.
EXEMPLO 2.7. Seja Σ = {0, 1} e r4 = (01 ∪ 100)∗. Então
L(r4) = L((01 ∪ 100)
∗) = L(01 ∪ 100)∗ = (L(01) ∪ L(100))∗ =
= ({01} ∪ {100})∗ = {01, 100}∗ =
= {ε, 01, 100, 0101, 01100, 10001, 100100, 010101, 0101100, . . .}.
OBSERVAÇÃO. Repare que duas expressões regulares distintas podem deno-
tar a mesma linguagem, isto é, podemos ter duas expressões regulares r1 e r2 tais
que r1 6= r2, mas L(r1) = L(r2). Este é o caso, por exemplo, das expressões
(0 ∪ 1)∗ e ((0∗ · 1)∗ · 0∗).
É claro que qualquer conjunto que possa ser representado a partir dos conjuntos
unitários ε e σ ∈ Σ e das operações de união, concatenação e estrela pode ser
denotado por uma expressão regular. Resta-nos praticar um pouco a construção de
uma expressão regular que denote um conjunto dado, a partir da descrição deste
conjunto.
EXEMPLO 2.8. Suponhamos que Σ = {a, b, c}. Para obter todas as palavras
em um certo subconjunto de Σ devemos usar o operador estrela (∗). Assim,
Linguagem formada por todas as palavras Expressão regular
(vazias ou não) que só contêm a a∗
nos símbolos a, b e c (a ∪ b ∪ c)∗
que não contêm a (b ∪ c)∗
em a e cujo comprimento é par (a · a)∗
EXEMPLO 2.9. Outro exemplo interessante consiste na linguagem formada
pelas palavras que contêm exatamente um a. Isto significa que os outros símbolos
2. EXPRESSÕES REGULARES 23
da palavra têm que ser bs ou cs. Como estes símbolos tanto podem aparecer antes
como depois do a, uma tal palavra será da forma uav, onde u e v são palavras que
contêm apenas b e c. Isto nos remete à expressão regular (b ∪ c)∗ · a · (b ∪ c)∗.
EXEMPLO 2.10. Duas variações, dignas de nota, do último exemplo acima
são a linguagem formada por todas as palavras que contêm exatamente dois as,
que corresponde a
(b ∪ c)∗a(b ∪ c)∗a(b ∪ c)∗
e a linguagem formada por todas as palavras que contêm um número par de as, que
é denotada por
((b ∪ c)∗a(b ∪ c)∗a(b ∪ c)∗)∗
EXEMPLO 2.11. Um exemplo um pouco mais difícil é a linguagem formada
pelas palavras que contêm um número ímpar de as. Precisamos adicionar um a
extra à expressão acima. O problema é que este a pode aparecer em qualquer lugar
da palavra, de modo que não podemos simplesmente concatená-lo no início ou no
fim da expressão acima. A saída é tomar
((b ∪ c)∗a(b ∪ c)∗a(b ∪ c)∗)∗a((b ∪ c)∗a(b ∪ c)∗a(b ∪ c)∗)∗.
Agora que já conhecemos a notação das expressões regulares, que nos permite
descrever de forma uniforme e compacta algumas linguagens, resta-nos mostrar
que dado qualquer AFD A, podemos descrever L(A) através de uma expressão
regular. Isto é, precisamos resolver o seguinte problema.
PROBLEMA 2.12. Dado um AFD A = (Σ, Q, q0, F, δ), quero construir uma
expressão regular r tal que L(r) = L(A), isto é, tal que a linguagem gerada por r
seja exatamente a linguagem aceita por A.
Estudaremos um algoritmo que resolve este problema no próximo capítulo.
Encerramos com três exemplos de natureza mais prática. Um dos primeiros
passos do processo de compilação de uma linguagem de programação é conhecido
como análise léxica. Nesta etapa, o compilador identifica, por exemplo, quais
24 2. EXPRESSÕES REGULARES
foram os números inteiros e as variáveis utilizadas no programa. É claro que esta
é uma etapa necessária para que seja possível interpretar corretamente o programa.
Na prática, isto pode ser feito com um autômato finito. Assim, para identificar
as variáveis, construímos um autômato finito que aceita a linguagem que descreve
as variáveis de uma linguagem. Isto é feito em duas etapas. Primeiro obtemos
uma expressão regular que denote as variáveis da linguagem de programação. Em
seguida, construímos um autômato finito que aceite esta linguagem.
Contudo, pôr esta estratégia em prática depende de sermos capazes de resolver
algoritmicamente o seguinte problema, que é, de certa forma, o inverso do pro-
blema que já descrevemos acima.
PROBLEMA 2.13. Dada uma expressão regular r, construir um autômato fi-
nito que aceite a linguagem gerada por r.
Abordaremos este problema detalhadamente mais adiante nestas notas. Entre-
tanto, já estamos em condições de obter expressões regulares para as linguagens
que descrevem inteiros e variáveis de um programa, como veremos a seguir.

Crie agora seu perfil grátis para visualizar sem restrições.