Aula-2-Linguagens-e-Expressões-Regulares

Prévia do material em texto

Linguagens Expresso˜es Regulares Exercı´cios
Modelagem e CLP – Linguagens e
Expresso˜es Regulares
Rafael Garlet de Oliveira
Instituto Federal Catarinense - IFC
Caˆmpus Luzerna
5 de marc¸o de 2014
Rafael Garlet de Oliveira 1 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Suma´rio
1 Linguagens
Alfabetos
Cadeias
Linguagens
Operac¸o˜es Sobre Linguagens
2 Expresso˜es Regulares
Definic¸a˜o
Exemplos
Propriedades
Linguagem Regular
3 Exercı´cios
Rafael Garlet de Oliveira 2 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Alfabetos
Rafael Garlet de Oliveira 3 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Cadeias
Rafael Garlet de Oliveira 4 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Poteˆncias de um Alfabeto
Rafael Garlet de Oliveira 5 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Fechamento Kleene
Rafael Garlet de Oliveira 6 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Linguagens
Rafael Garlet de Oliveira 7 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Operac¸o˜es Sobre Linguagens
Sejam as linguagens A, B e L ⊆ Σ*
Concatenac¸a˜o:
AB := {s ∈ Σ∗/s = uv ,u ∈ A, v ∈ B}
Uma cadeia em AB e´ a concatenac¸a˜o de uma cadeia de A
com uma cadeia de B.
Prefixo-Fechamento:
L := {s/∃t ∈ Σ∗, st ∈ L}, em geral L ⊆ L.
L e´ composto de todas as cadeias de Σ∗ prefixos de L.
L e´ prefixo-fechada se qualquer prefixo de L e´ cadeia de L.
Fechamento-Kleene:
L∗ := ε ∪ L ∪ LL ∪ LLL ∪ ...
Uma cadeia de L∗ e´ formada pela concatenac¸a˜o de um
nu´mero de cadeias de L, incluindo ε.
Operac¸o˜es usuais sobre conjuntos.
Rafael Garlet de Oliveira 8 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Representac¸a˜o de SEDs por Linguagens
Uma linguagem pode especificar todas as sequeˆncias de
eventos em um SED.
O comportamento sequencial de um SED pode ser
descrito atrave´s de um par de linguagens: L e Lm.
L: comportamento gerado do sistema: todas as cadeias de
eventos fisicamente possı´veis;
Lm: comportamento marcado do sistema: conjunto de
cadeias que correspondem a tarefas completas;
Lm ⊆ L: o comportamento gerado conte´m o
comportamento marcado;
L = L: o comportamento gerado e´ prefixo-fechado.
Rafael Garlet de Oliveira 9 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Exercı´cios
Considere o alfabeto Σ = {α, β, γ} e as linguagens
L1 = {ε, α, αββ} e L2 = {γ} definidas sobre Σ.
L1 e L2 sa˜o prefixo fechadas?
L1L2 =
L1 =
L2 =
L1L2 =
L∗2 =
Rafael Garlet de Oliveira 10 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Suma´rio
1 Linguagens
Alfabetos
Cadeias
Linguagens
Operac¸o˜es Sobre Linguagens
2 Expresso˜es Regulares
Definic¸a˜o
Exemplos
Propriedades
Linguagem Regular
3 Exercı´cios
Rafael Garlet de Oliveira 11 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Convenc¸a˜o Utilizada
Se u e v sa˜o cadeias de eventos:
u = {u}
(u + v) = {u, v} = {u} ∪ {v}
u∗ = {ε,u,uu,uuu, ...}
uv = {uv}
Rafael Garlet de Oliveira 12 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Definic¸a˜o Recursiva
Uma expressa˜o regular para um dado alfabeto Σ pode ser
definida da seguinte maneira:
1 Sa˜o expresso˜es regulares:
φ: conjunto vazio;
ε : linguagem{ε};
σ : linguagem{σ},∀σ ∈ Σ.
2 Se r e s sa˜o expresso˜es regulares, enta˜o rs, r∗, s∗, (r + s)
sa˜o expresso˜es regulares;
3 Toda expressa˜o regular e´ obtida pela aplicac¸a˜o das regras
1 e 2 um nu´mero finito de vezes.
Rafael Garlet de Oliveira 13 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Exemplos
Seja o alfabeto Σ = {α, β, γ}, sa˜o exemplos de expresso˜es
regulares:
(α + β)γ∗ = {α, β, αγ, βγ, αγγ, βγγ, αγγγ, βγγγ, ...}
(αβ)∗ + γ = {ε, γ, αβ, αβαβ, αβαβαβ, ...}
Rafael Garlet de Oliveira 14 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Exemplo
Seja o alfabeto Σ = {α, β}, onde:
α : acesso de uma tarefa ao recurso 1;
β : acesso de outra tarefa ao recurso 1.
A = (αβ)∗;
B = (α + β)∗;
C = (αβ)∗ + (βα)∗;
Encontre uma expressa˜o regular que indique que a
diferenc¸a entre o nu´mero de acessos de cada tarefa ao
recurso 1 na˜o seja superior a 1.
Rafael Garlet de Oliveira 15 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Propriedades
Sejam R, S e T expresso˜es regulares:
R + φ = R
Rε = R = εR
Rφ = φ = φR
R + S = S + R
R + R = R
R + (S + T ) = (R + S) + T
R(ST ) = (RS)T
R(S + T ) = RS + RT
ε∗ = ε
φ∗ = ε
(R + S)∗ = (R∗ + S∗)∗
(R + S)∗ = (R∗S∗)∗
(R∗)∗ = R∗
(R)∗(R∗) = R∗
Rafael Garlet de Oliveira 16 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Linguagem Regular
Expresso˜es regulares fornecem um meio para descrever
linguagens:
Definic¸a˜o: Linguagem Regular
E´ qualquer linguagem que possa ser descrita por uma
expressa˜o regular.
Rafael Garlet de Oliveira 17 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Suma´rio
1 Linguagens
Alfabetos
Cadeias
Linguagens
Operac¸o˜es Sobre Linguagens
2 Expresso˜es Regulares
Definic¸a˜o
Exemplos
Propriedades
Linguagem Regular
3 Exercı´cios
Rafael Garlet de Oliveira 18 / 19
Linguagens Expresso˜es Regulares Exercı´cios
Rafael Garlet de Oliveira
rafael.oliveira@luzerna.ifc.edu.br
Sala de Professores 1
Rafael Garlet de Oliveira 19 / 19
	Linguagens
	Alfabetos
	Cadeias
	Linguagens
	Operações Sobre Linguagens
	Expressões Regulares
	Definição
	Exemplos
	Propriedades
	Linguagem Regular
	Exercícios