Sistemas a Eventos Discetos Linguagens Formais e Autmatos

Angelo Perkusich Departamento de Engenharia Eltrica Universidade Federal de Campina Grande Campina Grande, Paraba E-mail: perkusic@dee.ufcg.edu.br

Linguagens Definidas para um Conjunto de Eventos Ponto inicial para definir um SED: conjunto de eventos E ou : alfabeto da linguagem Exemplos:
verifique o leo, tanque cheio temperatura alta mensagem enviada mensagem recebida depsito cheio depsito vazio mquina ociosa mquina ocupa
Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-2

Definio de Linguagem
Uma linguagem definida sobre E um conjunto finito de cadeias ou palavras de elementos de E Exemplo: E = {a, b, g}
L1 = { , a, abb, abg}, onde a palavra vazia L2 = {todas as cadeias de comprimento 3 terminando com um a} L3 = {todas as possveis cadeias finitas que terminan com um a}

s: sequncia finita de eventos definida em E, palavra ou cadeia s1 = e2e3e1e1e10 (abb} (inclui repeties)

s = comprimento de s
Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-3

Operaes
Concatenao: s1 = e2e3e1e1e10 e s2 = e5e3 ento s1 s2 = e2e3e1e1e10 e5e3 E* denota o conjunto de todos as palavras finitas de E, incluindo a palavra vazia , a operao * denominada de fechamento de Kleene Por exemplo para E = {a, b, g}

E * = { , a, b, c, aa, ab, ac, ba, bb, ca, K}

Uma linguagem L um subconjunto de E*

Por exemplo: E *
E E*

(a linguagem vazia)

{ } E * (a linguagem que contm somente a palavra vazia)

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-4

Operaes
Para uma cadeia qualquer s = t u v
t o prefixo de s u uma sub-palavra de s v o sufixo de s

Observe que ambos e s so prefixos, subpalavras e sufixos de s

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-5

Operaes Sobre Linguagens

Concatenao: seja L , L E *, ento a b

La Lb :={s E (s = sasb ) (sa La) (sb Lb )}

*

Prefixo fechamento: seja L E *, ento

L := {s E * : t E * ( st L)}
Note que:

LL
L=L
, L E * ento

Uma linguagem prefixo fechada por definio se Fechamento de Kleene: seja

L := { } L LL LLL K
Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-6

Autmato
Dispositivo para representar uma linguagem com um conjunto de regras bem definidas Representado como um grafo direcionado: ns so estados e arcos rotulados so transies b f :X EX y a X = {x,y,z} E = {a, b, g } a f ( x, a ) = x f (x , g ) = z x a,g f ( y, a ) = x f ( y, b) = y g f (z , b ) = z f ( z, a ) = f ( z , g ) = y z b Estado inicial : x Estados marcados : x, z
Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-7

Automato Determinstico
G = ( X , E, f , , x 0 , X m ) X : conjunto de estados E : conjunto finito de eventos associados s transies f : X E X funo de transio de estados f ( x, e) = y Note que f uma funo parcialmen te definida (no precisa) ser sempre definida : X 2E funo de eventos realizvei s ( ativos ) (x) E, o conjunto de eventos ativos , para o qual f(x, ) definida. x 0 : estado inicial X m X : conjunto de estados marcados
Qual estado marcar: problema de modelagem
Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-8

Funcionamento
Inicie em x0. A ocorrncia do evento e (x0) E causa a transio para o estado f(x0,e) X O processo continua baseado em transies para as quais f definida a x (x0)={a,g} g z y b a,g Ocorre g b

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-9

Funcionamento
Extendendo o domnio de f de X E para X E * f ( x, ) = x f ( x, s ) = f ( f ( x, s ), ) para s E * , e E

a x g

y a,g z

b f ( y, ) = y f ( x, gba ) = f ( f ( x, gb ), a ) = f ( f ( f ( x , g ), b ), a ) = f ( f ( z, b ), a ) = f ( z , a ) = y
f ( x, ( aagb ) = z f z , b n = z , n 0 , onde b n denota n ocorrncia s consecutiv as do evento n
Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-10

Linguagem Gerada por um Autmato

Linguagem gerada pelo autmato: G = ( X , E , f , , x0 , X m)

L(G ) = {s E* : f (x0 , s )!} onde ! significa definida

Linguagem marcada pelo autmato: G = ( X , E , f , , x0 , X m)

Lm (G ) = {s L(G) : f ( x0 , s ) X m}
Dois autmatos G1 e G2 so equivalentes se:

L(G1 ) = L(G2 )

Lm (G1 ) = Lm (G2 )

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-11

Exemplos de Autmatos Equivalentes

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-12

Bloqueio
De modo geral, a partir da definio de G, temos: e

Prefixo fechada por definio Fechamento do prefixo

Note que se: Mas:

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-13

Autmato Bloqueante
autmato G pode alcanar o estado x, mas (x) = e x xm
Isto denominado de impasse (deadlock) pois no h mais eventos que possam ser executados O sistema bloqueia quando este estado alcanado

Quando temos um conjunto de estados no marcados formando um ciclo (componente fortemente conectado) temos um bloqueio vivo (livelock)
Estados no marcados so alcanveis uns dos outros pela ocorrncia de eventos mas no h como sair destes estados

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-14

Problemas com a execuo concorrente

Processos concorrentes geralmente precisam compartilhar dados (mantidos em memria ou arquivos compartilhados) Caso no ocorra acesso controlado aos dados compartilhados, alguns processos podem obter vises inconsistentes sobre os dados. Os resultados das aes executadas por Processos concorrentes dependero da ordem como tais operaes so entrelaadas
Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-15

Um Exemplo
Os processos P1 e P2 esto executando as computaes definidas abaixo e acessam a mesma varivel x e no instante inicial x=0
P1:x=x+1 P2:x=x+2

Os Processos podem ser interrompidos em qualquer instante de execuo Considere a seguinte sequncia de operaes indivisveis:
Carregue um registrador com o valor da varivel x Adicione ao valor do registrador 1 (P1) ou 2 (P2) Armazena o resultado em x

Resultado da execuo dos processos P1 e P1: x=3? Nem sempre, podemos obter: x=1, x=2, ou x=3
depende das sequncias de instrues indivisveis executada
Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-16

Condies de Corrida (Race Conditions)

Situaes como estas, onde os processos acessam concorrentemente os mesmos dados concorrentemente e o resultado da execuo depende de uma ordem de execuo particular para acesso aos dados so denominadas de condies de corrida

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-17

Exemplo de Deadlock e Livelock

g a 0 g 2 Estado de impasse: 5 Livelock: 3-4 1 a b 3 a b 4 g 5

O autmato G no bloqueante se Lm (G ) = L(G )

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-18

Exemplo: Verificao do Estado de uma Mquina

x0 = {0} X m = {4} 5 Estado de rro : livelock o corre no e stado 5

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-19

Exemplo: Sistema de Banco de Dados

Sistemas de gerenciamento de bancos de dados (SGBD) so sistemas a eventos discretos que supervisionam a execuo correta e regular de operaes concorrentes de mltiplos processos (transaes) que podem ocorrer devido a aplicaes acessando e interagindo com um recurso comum compartilhado. Tal mecanismo denomina-se controle de concorrncia Considere que h somente dois processos, denominados ler(read, r)) e escrever (write, w). Eventos do tipo r1(a), w2(b), denotam:
r1(a):= transao 1 lendo o registro a w2(a ):= transao 2 escrevendo no registro b

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-20

Exemplo: Sistema de Banco de Dados

Cadeias tpicas de eventos so:
r1(a) r1(b) r2(a) w1(a ) r2(b) w2(b)

Escalonamentos completos so todos aqueles onde uma leitura seguida de uma escrita correspondente Suponha agora que a cadeia de eventos :
sx=r2(a) w2(a ) r1(a) r1(b) r2(b) w2(b)

Suponha que a transao 1 est para obter o saldo de duas contas correntes acessando os registros a e b, enquanto a transao 2 est pronta para transferir R$ 100,00 das contas referentes aos registros a e b. O resultado retornado pela transao sx seria correto? Neste caso o resultado retornado seria incorreto pois r1(a) e r1(b) foram executadas antes de w2(b). Observe a sequncia:
sx=L2(registro a) Escreve2(registro a R$ 100,00) L1(registro a R$ 100,00) L1(registro b) L2(registro b) Escreve2(registro b+ R$ 100,00)

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-21

Exemplo: Sistema de Banco de Dados

Outro exemplo
sy=r2(a) w2(a ) r1(a) r2(b) w2(b) r1(b)

Este escalonamento admissvel. O resultado retornado pela transao 1 agora correto. Entretanto observe o escalonamento da transao:
sz=r1(a) r2(a) w2(a) r2(b) w2(b)

O que ocorre? Apesar de que nada errado acontece, esta transao no pode ser corretamente completada pois se r1(b) executada, o resultado seria de R$ 100,00 a mais. Logo temos um impasse! O papel do controle de sistemas a eventos discretos garantir a correta execuo de sequncias de eventos. Pudemos observar dois casos:
Execuo de operaes em sequncias incorretas Bloqueio
Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-22

Operaes com Autmatos

Todo autmato modela duas linguagens:

L(G) e Lm (G)
Noo de acessibilidade e co-acessibilidade Parte acessvel: apagar estados que no so alcanaveis a partir de x0

Ac(G) = { X ac , E, f ac , x0 , X ac ,m ) X ac = {x X : s E ( f ( x0 , s) = x)} X ac , m = X m X ac
*

f ac = f ac | X ac E X ac
Ac no afeta L(G), e Lm (G) Portanto, sempre assume-se que G = Ac(G)
Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-23

Operaes em Autmatos
Parte co-acessvel Um estado co-acessvel se a partir dele pode-se alcanar um estado marcado Tomar a parte co-acessvel significa contruir: CoAc(G) = { X coac , E , f coac , x0 , coac , X m )

X coac = {x X : s E * ( f ( x , s ) X m )} if x0 X coac x0 x0 , coac = caso contrrio indefinido f coac = f | X coac E X coac

A operao CoAc encolhe L(G) mas no Lm(G)

G = CoAc(G) G co acessvel L(G ) = Lm (G)

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-24

Operaes em Autmatos
Um autmato que co-acessvel e acessvel dito ser trim

Trim(G ) = CoAc[ Ac(G )] = Ac[CoAc(G )]

Co-acessibilidade est ligada a questo de bloqueio

Bloqueante L(G ) Lm (G )
No bloqueante co-acessvel
Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-25

Exemplo de Autmato Trim

a 0 g 1 b 2 G 1 b g 2 b 6 0 g 2 1 0 b g 2 a 1 b a,b a,g g a 5 3 a b 6 4 g 2. b 1. Complete a funo de transio f de G e torne-a total feito adicionando-se um estado morto (d) Troca o estados marcados por no marcados e vice versa, para todos os estados

a 0

CoAc(G)

Trim(G)

b,g a,b,g Complemento do Trim(G)

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-26

Composio de Autmatos
Duas formas
Produto: Paralelo: completamente sncrono sncrono

G1

E1E2

|| G1 G1 E1E2 G1 G1 || G2

G1 G2

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-27

Composio pelo Produto

G1 = ( X 1 , E 1 , f 1 , 1 , x01 , X m 1) e G2 = ( X 2 , E 2 , f 2 , 2 , x02 , X m 2 ) G1 G2 := Ac( X 1 X 2 , E 1 E 2 , f , 12 , ( x01 , x02 ), X m 1 X m 2 ) onde ( f 1 ( x1 , e), f 2 ( x 2 , e ) se e 1 ( x1) 2 ( x 2 ) f (( x 1 , x 2 ), e) := indefinido caso contrrio logo 1 2 ( x1 , x 2) = 1 ( x 1) 2 ( x2 ) Propriedad es : L(G1 G2 ) = L(G1 ) L( G2 ) Lm (G1 G2 ) = Lm (G1 ) Lm (G2 ) define como podemos fazer a intersec o de duas linguagens
Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-28

Exemplo: Composio pelo Produlo

Autmato produto

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-29

Composio Paralela
G1 = ( X 1 , E 1 , f 1 , 1 , x01 , X m 1) e G2 = ( X 2 , E 2 , f 2 , 2 , x02 , X m 2) G1 || G2 := Ac ( X 1 X 2 , E1 E 2 , f , 1||2 , ( x01 , x02), X m 1 X m 2) onde ( f 1 ( x1 , e), f 2 ( x 2 , e ) se e 1 ( x1) 2 ( x 2) se e 1 ( x1) \ E 2 ( f 1 ( x1 , e), x 2) f (( x 1 , x 2), e) := se e 2 ( x2) \ E1 ( x1 , f 2 ( x 2 , e) indefinido caso contrrio logo 1||2 ( x1 , x2) = [ 1 ( x 1) 2 ( x 2 )] [ 1 ( x 1) \ E 2 ] [2 ( x2 ) \ E1 ] Propriedad es : G1 || G2 = G2 || G1 G1 || (G2 || G2 ) = (G1 || G2 ) || G2

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-30

Complexidade da Composio Paralela

Um sistema com k componentes possui m estados. Se os conjuntos de eventos dos autmatos so distintos, ento o modelo completo do sistema ter mk estados (crescimento exponencial) Como tratar a complexidade?
Anlise incremental ou composicional Representaes simblicas (Symbolic Model Checking:
1020 States and Beyond, Burch, et al., Information and Computation, vol. 98, pp. 142-170, 1998.

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-31

Exemplo: Composio Paralela

b

Dois autmatos so sincronizados nos eventos comuns, E1 E2 Um autmato pode executar eventos privados sem a participao do outro autmato (E1 \ E2) (E2 \ E1) Se E1 = E2 ento a composio paralela ser reduz ao produto Se E1 E2 = ento G1 G2 o comportamento concorrente de G1 e G2 G1 G2 = G2G1 (G1 G2 ) G3= G1 (G2 G3)
Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-32

Eventos comuns {a,b} Evento privado {g}

Problema dos Filsofos (Mltiplos usurios e um recurso comum)

Composio dos quatro atutmatos Autmatos modelandos os filsofos (P1,P2), e dois palitos (F1,F2)

Filsofos: (i) pensam, (ii) comem Palitos: (i) disponveis, (ii) usados

P1 P2 a com posio paralela P F = P1 P2 F 1 F 2 P F C = C oA c ( P F )

Modelo incompleto Contm dois estados de impasse

- controlador adicionado para evita-los

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-33

Autmatos de Moore e Mealy

Autmato de Moore: autmato sadas associadas aos estados Mealy: autmato entrada/sida Autmatos de estados finitos Linguagens Regulares

Sistemas a Eventos Discretos: Linguagens Formais e Autmatos-Angelo Perkusich-DEE/CCT/UFCG-34