ER - LFAC

a*

Expressões Regulares (ER)
AF e ER
Equivalências entre AFD, AFND, AF-, ER
1

Expressões Regulares (ER)
Uma ER sobre um alfabeto  é definida como:
a)  é uma ER e denota a linguagem vazia
b)  é uma ER e denota a linguagem contendo a palavra vazia, ie {}
c) Qualquer símbolo x   é uma ER e denota a linguagem {x}
d) Se r e s são ER denotando as linguagens R e S então:
•
•
•

(r+s) ou (r|s) é ER e denota a linguagem R  S
(rs) é ER e denota a linguagem RS = {w=uv | u
 R e v S}
(r*) é ER e denota a linguagem R*

2

Exemplos

• 00 é uma ER denotando a linguagem {00}

• (0+1)* denota a linguagem formada por todas as cadeias de 0´s e 1´s
• (0+1)* 00 (0+1)* denota todas as cadeias de
0´s e 1´s com ao menos dois 0´s consecutivos
• a+b*c denota um único a ou zero ou mais vezes b seguido de c
3

• (0+1)* 001 denota todas as cadeias de 0´s e
1´s terminadas em 001
• 0*1*2* denota qualquer número de 0´s seguido por qualquer número de 1´s seguido por qualquer número de 2´s
• 01* + 10* denota a linguagem consistindo de todas as cadeias que são um único 0 seguido por qualquer número de 1´s OU um único 1 seguido por qualquer número de 0´s.
4

Omissão de parênteses
• Para omitir parênteses devemos respeitar:
– O fecho (*) tem prioridade sobre a concatenação (rs), que tem prioridade sobre a união.
– A concatenação e a união são associadas da esquerda para a direita.
– Ex: 01* + 1 é agrupado como (0(1*)) + 1 => L = {1, 0, 01,
011,...}
• Usamos parênteses quando queremos alterar a prioridade:
• (01)* + 1 => L = {1 U (01)n | n >= 0} = {1,  , 01, 0101,...}
• 0(1* + 1) => L = {w  {0,1}* | w começa com 0 seguido de 1n | n>=0}  Lei distributiva à esq = 01* + 01 = {0,01,011,0111,...}
5

Escreva a ER equivalente a:

• O conjunto de cadeias sobre {0,1} que termine com três 1´s consecutivos.
• O conjunto de cadeias sobre {0,1} que tenha ao menos um 1.
• O conjunto de cadeias sobre {0,1} que tenha no máximo um