Sistemas a Eventos Discretos e Teoria do Controle

Prévia do material em texto

Universidade Federal do Rio Grande do Sul
Departamento de Sistemas Ele´tricos
de Automac¸a˜o e Energia
Apostila de Sistemas a Eventos Discretos
Autoˆmatos
&
Teoria do Controle Superviso´rio
Prof. Marcelo Go¨tz
Porto Alegre, Agosto de 2017
Apresentac¸a˜o
Este documento visa proporcionar ao aluno do Curso de Graduac¸a˜o intitulado Engenharia de
Controle e Automac¸a˜o, da Universidade Federal do Rio Grande do Sul, um material de consulta
para a disciplina ENG10021 - Sistemas a Eventos Discretos. Pore´m, este na˜o pretende ser um
material substituto a` bibliografia especificada (a qual consta no Plano de Ensino) para esta
disciplina. Recomenda-se, inclusive, que o aluno consulte a bibliografia indicada, a qual foi
utilizada como suporte para elaborac¸a˜o deste material, e que propicia um verificac¸a˜o mais
completa e abrangente do conteu´do. Este material pode ser utilizado como um resumo para
acompanhamento das explanac¸o˜es dos conteu´dos realizadas pelo professor em sala de aula.
Este material esta´ organizado da seguinte maneira:
Cap´ıtulo 1 introduz e conceitua os Sistemas Dinaˆmicos a Eventos Discretos, ou mais bre-
vemente chamado de Sistemas a Eventos Discretos (SED), fazendo tambe´m um breve
comparativo entre este sistema e os Sistemas Dinaˆmicos de Varia´veis Cont´ınuas (SDVC).
Este cap´ıtulo tem como refereˆncia o Cap´ıtulo 1 de [1] (fonte principal, um dos livros
texto da disciplina), mas tambe´m podem ser verificados adicionalmente os livros [2] e [3].
Este u´ltimo sendo bem mais abrangente, e tratando de va´rios assuntos de Controle e
Automac¸a˜o, ale´m de SEDs. Pore´m, de maneira resumida.
Cap´ıtulo 2 apresenta o modelo de Linguagens para SED, onde o foco esta´ na descric¸a˜o da
evoluc¸a˜o dos estados do SED por sequencias de eventos. Os conceitos aqui apresen-
tados servira˜o de base para o restante do documento, onde sa˜o discutidos modelos de
representac¸a˜o para Linguagens. O Cap´ıtulo 2 de [1] e´ a referencia principal para este
cap´ıtulo.
Cap´ıtulo 3 apresenta e discute o formalismo do modelamento por autoˆmatos, que sa˜o formas
enxutas de representac¸a˜o de Linguagens. Aqui esta˜o inclu´ıdas tambe´m as operac¸o˜es
realizadas com autoˆmatos, como as composic¸o˜es s´ıncronas, minimizac¸a˜o de autoˆmatos,
entre outras. Sa˜o discutidos exemplos de modelos aplicados a sistemas de automac¸a˜o e
manufatura. Fonte principal de consulta para este cap´ıtulo e´ o Cap´ıtulo 2 de [1].
Cap´ıtulo 4 a Teoria de Controle Superviso´rio (TCS), proposta por Ramadge e Wonham, e´ in-
troduzida neste cap´ıtulo, que e´ baseada na Teoria de Linguagens e Autoˆmatos mostrados
nos cap´ıtulos anteriores. Aqui e´ discutido o Controle Monol´ıtico, Controle Modular e
Controle Modular Local, sendo este u´ltimo proposto por Queiroz e Cury. O Cap´ıtulo 3
de [1] e´ a fonte prima´ria de refereˆncia, assim como pode ser consultada a fonte original
sobre TCS em [4, 5, 6]. Adicionalmente, o material de aula do Prof. Jose´ Eduardo
Ribeiro Cury [7] foi tambe´m consultado, assim como a proposta de Controle Modular
Local, de sua proposic¸a˜o como co-autor, dispon´ıvel em [8] e [9]. A maioria dos modelos e
exemplos aqui apresentados foram adaptados e/ou inspirados nas fontes acima citadas.
Cap´ıtulo 5 apresenta uma breve revisa˜o sobre Teoria dos Conjuntos, da matema´tica discreta,
que serve como base ferramental para o desenvolvimento e discussa˜o das teorias apre-
sentadas neste documento. Como refereˆncia a este cap´ıtulo pode-se citar os livros [10] e
[11].
iii
Suma´rio
Apresentac¸a˜o iii
1 Introduc¸a˜o 1
1.1 Preliminares e Definic¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Sistemas Dinaˆmicos de Varia´veis Cont´ınuas . . . . . . . . . . . . . . . . 2
1.2 Sistemas a Eventos Discretos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Modelagem e Ana´lise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Exemplos de SED . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.1 Sistema de Filas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 Sistemas de Manufatura . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.3 Sistema de Tra´fego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.4 Sistemas Hı´bridos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Linguagens 12
2.1 Linguagens em SED . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.1 Definic¸a˜o de Linguagem . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.2 Notac¸a˜o com Expoente . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.3 Operac¸o˜es sobre Linguagens . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Representac¸a˜o de Linguagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Modelagem de SED por Linguagens . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Estudo de Caso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Autoˆmatos Aplicados a Sistemas a Eventos Discretos 18
3.1 Autoˆmato Determin´ıstico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1.1 Definic¸a˜o de Autoˆmato . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1.2 Funcionamento do Autoˆmato . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.3 Linguagens Representadas pelo Autoˆmato . . . . . . . . . . . . . . . . . 20
3.2 Autoˆmato Na˜o-Determin´ıstico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2.1 Definic¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.2 Funcionamento do Autoˆmato Na˜o-Determin´ıstico . . . . . . . . . . . . . 23
3.2.3 Linguagens Gerada e Marcada por um AFND . . . . . . . . . . . . . . . 24
3.3 Propriedade Bloqueante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3.1 Definic¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 Expresso˜es Regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.5 Operac¸o˜es Una´rias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.5.1 Acess´ıvel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.5.2 Coacess´ıvel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.5.3 Trim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.6 Minimizac¸a˜o do Espac¸o de Estados . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.6.1 Equivaleˆncia de Estados . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.6.2 Algoritmo para Minimizac¸a˜o de Estados . . . . . . . . . . . . . . . . . . 33
iv
Suma´rio v
3.7 Composic¸a˜o de Autoˆmatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.7.1 Produto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.7.2 Composic¸a˜o Paralela . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.8 Modelagem de Sistema a Eventos Discretos . . . . . . . . . . . . . . . . . . . . 41
3.9 Modelagem das Especificac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.9.1 Exemplos de Especificac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . 45
4 Controle Superviso´rio 47
4.1 Introduc¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2 Controle de Sistemas a Eventos Discretos . . . . . . . . . . . . . . . . . . . . . 48
4.2.1 Sistema controlado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2.2 Eventos Na˜o Controla´veis . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3 Representac¸a˜o do Superviso´rio . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3.1 Demonstrac¸a˜o . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 51
4.3.2 Funcionamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3.3 Superviso´rio induzido . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.4 Controle com Eventos Na˜o-Controla´veis . . . . . . . . . . . . . . . . . . . . . . 53
4.4.1 Controlabilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.4.2 Controlabilidade na˜o-Bloqueante . . . . . . . . . . . . . . . . . . . . . . 54
4.4.3 Problema do Controle Superviso´rio . . . . . . . . . . . . . . . . . . . . . 55
4.4.4 Ca´lculo de supC(Lam) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.5 Controle Modular Cla´ssico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.5.1 Propriedades entre Linguagens . . . . . . . . . . . . . . . . . . . . . . . 60
4.5.2 Verificac¸a˜o de supC para Controle Modular . . . . . . . . . . . . . . . . 60
4.5.3 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.6 Controle Modular Local . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.6.1 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.7 Conclusa˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5 Breve Revisa˜o de Conjuntos 66
5.1 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.1.1 Conjuntos Finitos e Infinitos . . . . . . . . . . . . . . . . . . . . . . . . 66
5.1.2 Igualdade de Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.1.3 Conjunto Poteˆncia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.1.4 Operac¸o˜es em Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
1 Introduc¸a˜o
Os sistemas a eventos discretos, objeto de estudo deste material, se diferem consideravelmente
em termos de modelagem e natureza, dos sistemas tradicionais de controle de varia´vel cont´ınua.
Sistemas a eventos discretos tem tido grande atenc¸a˜o nos u´ltimos anos, especialmente em
sistemas de automac¸a˜o e manufatura. Com sua evoluc¸a˜o e n´ıveis de crescimento recentes, a
demanda por metodologias mais sistema´ticas para sua analise e controle tem tido um maior
apelo.
1.1 Preliminares e Definic¸o˜es
1.1.1 Sistema
De acordo com o IEEE (Instituto de Engenheiros Eletricistas e Eletroˆnicos), em seu Standard
Dictionary of Electrical and Electronic Terms, ou Diciona´rio Padra˜o de Termos Ele´tricos e
Eletroˆnicos, a definic¸a˜o de sistema e´: “Conjunto de elementos que interagem para a realizac¸a˜o
de uma func¸a˜o na˜o realiza´vel por nenhuma dos elementos individuais”. Ou seja, do ponto
de vista externo, um sistema pode ser visto como uma entidade (mesmo que formada por
sub-entidades) que manipulam a entrada para gerar a sa´ıda. A Figura 1.1 mostra esta ideia.
Para que se possa realizar a analise quantitativa de um sistema, assim como permitir o projeto
e desenvolvimento de sistemas de controle para este sistema utilizando crite´rios bem definidos,
e´ necessa´rio que se obtenha um modelo do sistema. Um modelo matema´tico permite que se
realize a analise quantitativa do sistema.
Geralmente, e´ interessante que se obtenha uma relac¸a˜o entre entrada e sa´ıda do sistema, ou seja,
a func¸a˜o deste sistema. Sejam p entradas descritas pelo vetor u(t) = [u1(t), u2(t), . . . , up(t)]
T .
Sejam tambe´m m sa´ıdas descritas pelo vetor y(t) = [y1(t), y2(t), . . . , ym(t)]
T . Define-se enta˜o
que a relac¸a˜o entre a entrada e sa´ıda seja descrita por uma func¸a˜o: y = g(u). Esta relac¸a˜o
considera apenas os sistemas invariantes no tempo, onde g(.) na˜o depende do tempo. Utilizando
estas definic¸o˜es, a Figura 1.1 pode ser redesenhada, como mostrado na Figura 1.2.
O modelo de um sistema pode ser bastante simples, como por exemplo, um divisor resistivo,
SistemaEntradas Saídas
Figura 1.1: Modelo conceitual de Sistema.
1
1.1. PRELIMINARES E DEFINIC¸O˜ES 2
y=g(u)g(.)u(t)
Figura 1.2: Modelo de relac¸a˜o entrada/sa´ıda de um sistema.
onde a entrada e´ uma tensa˜o e a sa´ıda e´ uma frac¸a˜o da tensa˜o de entrada. Este tipo de sistema
e´ um exemplo de sistema dito esta´tico, onde a sa´ıda so´ depende do valor atual da entrada, e
na˜o depende dos valores passados da entrada. Pore´m, na pra´tica outros tipos de sistemas, ditos
sistemas dinaˆmicos, sa˜o de maior interesse, e por consequeˆncia estes sera˜o estudados aqui.
1.1.2 Sistemas Dinaˆmicos de Varia´veis Cont´ınuas
O termo Teoria de Controle geralmente refere-se geralmente a sistemas de varia´vel cont´ınua,
onde o seu modelamento e analise esta˜o bastante consolidados e aceitos, tanto no meio acadeˆmico,
quanto no meio industrial. Os sistemas considerados por esta teoria possuem certas carac-
ter´ısticas, como: serem dinaˆmicos, possuirem varia´veis continuas e sa˜o orientados no tempo (o
tempo e´ a varia´vel independente), dentre outras. Assim, sa˜o chamados de Sistemas Dinaˆmicos
de Varia´veis Cont´ınuas (SDVC).
Em um sistema esta´tico, a sa´ıda em um instante de tempo t depende apenas da entrada
neste instante t. Diferentemente, um sistema dinaˆmico tem sua sa´ıda no instante t definida
pela entrada nesse instante t e tambe´m pelos valores passados da entrada. Ou seja, o sistema
apresenta uma certa “memo´ria”. Os sistemas dinaˆmicos apresentam os casos de maior interesse,
tanto na Teoria Cla´ssica e Teoria de Controle Moderno, quanto para os sistemas a eventos
discretos aqui estudados.
Em sistema dinaˆmico surge o conceito de estado. O estado de um sistema no tempo t0 e´ a
informac¸a˜o requerida em t0 tal que a sa´ıda y(t), para todo t ≥ t0, seja univocamente determi-
nada por esta informac¸a˜o (estado) e por u(t) (entrada) para t ≥ t0. O estado e´ representado
por varia´veis de estado, que e´ o conjunto mı´nimo de varia´veis que determinam o estado do
sistema. Considerando que o sistema possua n varia´veis de estado, tem-se o vetor de estado
x(t) = {x1(t), x2(t), . . . , xn(t)} que descreve o sistema modelado.
O espac¸o de estados de um sistema, geralmente denotado por X, e´ o conjunto de todos os
poss´ıveis valores que um estado pode ter. A representac¸a˜o de um espac¸o de estados de dimensa˜o
n, se da´ por um sistema de coordenadas onde cada eixo corresponde a uma varia´vel de estado.
Ou seja, um estado qualquer do sistema pode ser representado por um ponto neste espac¸o de
estados.
A evoluc¸a˜o dos estados de um sistema dinaˆmico modelado desta forma e´ chamado de trajeto´ria
dos estados, determinada pela evoluc¸a˜o dos estados ao longo do tempo. Esta trajeto´ria e´ regida
pelas equac¸o˜es de estado. Em SDVC as equac¸o˜es de estado sa˜o equac¸o˜es diferenciais de primeira
ordem que descrevem a dinaˆmica do sistema. Assim, um sistema pode ser modelado pelo seu
espac¸o de estados quando o mesmo e´ descrito da seguinte maneira:
x˙(t) = f(x(t),u(t), t) (1.1)
y(t) = g(x(t),u(t), t) (1.2)
onde a Equac¸a˜o 1.1 representa o conjunto de equac¸o˜es de estado, e a Equac¸a˜o 1.2 representa o
1.2. SISTEMAS A EVENTOS DISCRETOS 3
y=g(x,u,t)x=f(x,u,t)u(t)
.
Figura 1.3: Relac¸a˜o entrada/sa´ıda de um sistema modelado por estados.
conjunto de equac¸o˜es e sa´ıda para este sistema. Estas equac¸o˜es relacionam os estados, entradas
e sa´ıdas do sistema. A Figura 1.3 mostra a relac¸a˜o de entradas/sa´ıdas de um sistema modelado
por espac¸o de estados.
Para sistemas Lineares Invariantes no Tempo (LIT), as equac¸o˜es do modelo de espac¸o de
estados sa˜o descritas da seguinte maneira:
x˙(t) = Ax(t) +Bu(t) (1.3)
y(t) = Cx(t) +Du(t) (1.4)
Em um sistema SDVC o espac¸o de estados e´ cont´ınuo. Ou seja, os estados podem assumir
qualquer valor em R. Ainda, verifica-se que o sistema tem o tempo como sua varia´vel inde-
pendente.
O sistema pode tambe´m ser modelado por equac¸o˜es de diferenc¸as. Isto e´ feito quando se
realiza a discretizac¸a˜o do tempo. Ou seja, em intervalosregulares T de tempo, chamado de
intervalo de amostragem, o sinal e´ amostrado. Assim, ao inve´s de ter-se o tempo cont´ınuo,
tem-se o tempo discreto, dado por nT , sendo nestes instantes o valor x(nT ) o sinal amostrado.
Utilizando a notac¸a˜o [k] para representar (nT ), as equac¸o˜es do modelo por espac¸o de estados
amostrado podem ser representados pelas equac¸o˜es de diferenc¸as:
x[k + 1] = Ax[k] +Bu[k] (1.5)
y[k] = Cx[k] +Du[k] (1.6)
1.2 Sistemas a Eventos Discretos
Definic¸a˜o de SED
O tipo de sistema alvo de estudo deste documento sa˜o os denominados Sistemas Dinaˆmicos a
Eventos Discretos (SDED), ou simplesmente Sistemas a Eventos Discretos (SED). Fundamen-
talmente, o SED diferencia-se de um SDVC por possuir um espac¸o de estados discreto. Ou
seja, o espac¸o de estados que um sistema SED possui e´ naturalmente descrito por um conjunto
de valores discretos, como por exemplo {0, 1, 2, . . .}. Em um sistema de fila de pessoas, por
exemplo, que recebe pessoas para serem atendidas por um servic¸o, e pessoas que saem quando
atendidas, pode ser modelado como um sistema SED. O nu´mero de pessoas em um dado mo-
mento, nesta fila, e´ o estado do sistema, sendo N o nu´mero de pessoas na fila, enta˜o N ∈ X,
onde X ⊂ N. Claramente, o espac¸o de estados X e´ um conjunto discreto de valores.
Outra caracter´ıstica importante, e´ que a evoluc¸a˜o, ou trajeto´ria de um estado, e´ dirigida por
eventos, e na˜o pelo tempo, como em SDVC. Ou seja, a varia´vel independente de um SED e´
o evento. Um evento e´ modelado como um sinal que ocorre instantaneamente e que causa a
transic¸a˜o de um estado para outro estado. Um evento pode representar, por exemplo, uma
1.2. SISTEMAS A EVENTOS DISCRETOS 4
pessoa que entra na fila; uma pessoa que sai da fila; o pressionar de um bota˜o; a transic¸a˜o
de um sinal digital, de “0” para “1”; a sinalizac¸a˜o de um sensor de fim de curso, o sinal de
acionamento de uma esteira, o n´ıvel de um tanque que chegou no limite, a temperatura que
excedeu um valor cr´ıtico, um produto que chegou em uma esteira, entre outros.
Para a modelagem de eventos sera´ utilizado o s´ımbolo e para denotar um evento qualquer.
Considerando que um sistema possa ser afetado por um conjunto de eventos distintos, sera´
definido um conjunto E de eventos, cujos elementos deste conjunto sa˜o todos estes eventos.
Notadamente, E e´ tambe´m um conjunto discreto.
Alguns exemplos de sistemas com espac¸o de estados discretos:
• Os estados de funcionamento de uma esteira, que podem ser: { FUNCIONANDO, PA-
RADA}. A ac¸a˜o de ligar, ou parar a esteira por um CLP (Controlador Lo´gico Pro-
grama´vel) podem ser vistos como sendo os eventos destes sistema;
• Um computador executando um programa pode ser modelado como estando em um dos
treˆs poss´ıveis estados: { ESPERANDO POR ENTRADA, EXECUTANDO, FINALI-
ZADO}. As ac¸o˜es do usua´rio, em acionar, parar, etc, pode ser modelados como sendo
eventos do sistema;
• O estado EXECUTANDO, do exemplo anterior, pode, por sua vez, estar em outro sub-
estado individual, como por exemplo, em qual linha de co´digo ele se encontra. O avanc¸o
do relo´gio do sistema digital pode ser visto como a fonte de eventos;
• Uma fila de supermercado, ou de atendimento para pessoas, como nos exemplos anteri-
ores. Uma pessoa entrando ou saindo da fila, pode ser visto como um evento;
• Um jogo de xadrez pode, por exemplo, ter cada poss´ıvel disposic¸a˜o de pec¸as modelado
como sendo um estado individual. Cada movimento de uma pec¸a pode levar o jogo de
um estado a outro. Notadamente o espac¸o de estados sera´ enorme, pore´m ainda discreto;
A Figura 1.4 mostra o espac¸o de estados e da evoluc¸a˜o dos estados para um sistema SED e
SDVC, para uma melhor visualizac¸a˜o do comparativo entre os mesmos.
A Figura 1.4a mostra a evoluc¸a˜o do estado de um sistema cont´ınuo, sendo que x(t) e´ geralmente
a soluc¸a˜o da equac¸a˜o diferencial x˙(t) = f(x(t), u(t), t), onde u(t) e´ o sinal de entrada. Ou seja,
o espac¸o de estados e´ cont´ınuo, e´ um conjunto de nu´meros reais, e o valor de x pode assumir
qualquer valor deste conjunto. Percebe-se neste caso que a evoluc¸a˜o e´ cont´ınua e regida pelo
tempo.
A Figura 1.4b mostra a evoluc¸a˜o dos estados em um sistema a eventos discretos, sendo que o
espac¸o de estados e´ um conjunto discreto X = {s1, s2, s3, s4, s5, s6}. A evoluc¸a˜o dos estados
se da´ de maneira discreta, e na ocorreˆncia de um evento, ocorre a troca de um estado para
outro. Sera´ visto que para certos modelos sera´ definida a func¸a˜o f(.) de transic¸a˜o de estado,
que dependendo do estado x atual, e da ocorreˆncia de um evento e, o sistema trocara´ para o
novo estado x′, ou: x′ = f(x, e).
Nota-se tambe´m que a ocorreˆncia de um evento na˜o necessariamente realiza a troca de um
estado. No exemplo da Figura 1.4b, a ocorreˆncia do evento e3 em t3 e´ um exemplo desta
situac¸a˜o. Ja´ em t6, o mesmo evento e3 causa a troca do estado s3 para o estado s4. Ou seja,
o mesmo evento pode ter efeitos diferentes no sistema, dependendo do estado corrente. Esta
situac¸a˜o e´ caracter´ıstica de sistemas dinaˆmicos.
Verifica-se aqui que a evoluc¸a˜o dos estados e´ dirigida por eventos. Independentemente do
1.2. SISTEMAS A EVENTOS DISCRETOS 5
t
x(t)
(a) Trajeto´ria do estado em um SDVC. x(t) ∈ R.
s2
s1
s3
s4
s5
s6
tt1 t2 t3 t4 t5 t6 t7
e1 e2 e3 e4 e4 e3 e1 e
(b) Trajeto´ria dos estados em um SED. x ∈ {s1, s2, s3, s4, s5, s6}.
Figura 1.4: Trajeto´ria de estados para SDVC e SED.
1.2. SISTEMAS A EVENTOS DISCRETOS 6
tempo t em que um evento e ocorra, e´ o evento que determina a troca de estados de um SED.
Um SED pode permanecer em um estado durante um tempo arbitrariamente longo. Assim,
a sequencia de eventos e´ que determina o comportamento do sistema (evoluc¸a˜o dos estados).
No exemplo da Figura 1.4b, o comportamento (evoluc¸a˜o dos estados) e´ dado pela sequencia
e1e2e3e4e4e3e1. Mesmo que o tempo seja uma varia´vel secunda´ria para SEDs, esta informac¸a˜o
pode ser u´til dependendo do tipo de modelamento e ana´lise que se pretende realizar, como sera´
visto adiante.
1.2.1 Modelagem e Ana´lise
As ferramentas de modelagem e analise ja´ consolidadas e conhecidas para SDVC, na˜o se aplicam
para SED. Procura-se aqui um modelamento para se obter equac¸o˜es que regem a evoluc¸a˜o dos
estados em func¸a˜o da ocorreˆncia de eventos. Notadamente, equac¸o˜es diferenciais, ou equac¸o˜es
de diferenc¸as, na˜o servem para descrever este comportamento. Por vezes, e´ suficiente que um
SED seja modelado apenas pela sequencia de eventos, sendo neste caso chamado de modelo
atemporal. Isto e´ suficiente quando se pretende analisar se existe bloqueio no sistema, se um
estado pode ser alcanc¸ado, se um estado proibido e´ alcanc¸ado, se a lo´gica do controle e suas
restric¸o˜es sa˜o atendidas, entre outras.
Existe tambe´m modelos que adicionam a informac¸a˜o temporal, ou seja, em que instante de
tempo o evento ocorre. Isto se torna interessante quando se pretende analisar, por exemplo, o
tempo me´dio de espera em uma fila, taxa de produc¸a˜o de um sistema de manufatura, eficieˆncia
temporal do sistema, taxa de ocupac¸a˜o de equipamentos, a caracter´ıstica de desempenho do
sistema, entre outros. Modelos mais completos podem ainda incorporar modelos estat´ısticos
para cada evento temporal (vide, por exemplo, [2]). Quando se define uma func¸a˜o de distri-
buic¸a˜o de probabilidades para cada evento, tem-se um modelo temporal estoca´stico do sistema.
Isto se torna interessante para simulac¸o˜es, por exemplo, para se refinar as informac¸o˜es em um
sistema temporal.
Modelos e ferramental de analise de SEDs utilizam conceitos provenientes da Cieˆncia da Com-
putac¸a˜o, Pesquisa Operacional, assim como da Teoria de Controle. Diferentemente da Teoria
de Controle para SDVC, existem va´rias propostas de modelagem de SEDs, sem entretanto que
se tenha umadefinic¸a˜o de que uma destas seja universal e bem aceita. Alguns modelos sa˜o
mais apropriados para certos sistemas, e outros modelos mais adequados para outros tipos de
sistemas. Os principais modelos utilizados na atualidade sa˜o:
• Redes de Petri;
com ou sem temporizac¸a˜o;
• Teoria de Linguagem e Autoˆmatos;
base para a Teoria do Controle Superviso´rio - TCS;
• Cadeias de Markov;
• Teoria de Filas;
• A´lgebra de Processos;
• A´lgebra Max-Plus;
• Lo´gica Temporal e Lo´gica Temporal de Tempo-Real;
Neste documento sera˜o estudados a Teoria de Linguagem e Autoˆmatos, que servira´ como base
1.3. EXEMPLOS DE SED 7
ServidorFila
Partidas
de
clientes
Chegada
de 
clientes
Figura 1.5: Modelo de um sistema de fila simples.
para a Teoria do Controle Superviso´rio, tema que tambe´m sera´ aqui estudado.
1.3 Exemplos de SED
Para um melhor entendimento dos sistemas aqui definidos, nesta sec¸a˜o sera˜o apresentados
alguns tipos de SED, com definic¸a˜o de seu espac¸o de estados discreto e conjunto de eventos.
1.3.1 Sistema de Filas
Um modelo bastante gene´rico e bastante comum no modelamento de SEDs, e´ baseado na Teoria
de Filas. E´ utilizado para representar recursos que sa˜o compartilhados, em que as entidades
que usam o recurso devem esperar para ocupa´-lo. Por exemplo, um recurso pode ser visto
como um caixa de supermercado ou banco, um roboˆ ou estac¸a˜o de trabalho em uma fa´brica,
um cruzamento de uma avenida, etc.
Outro componente deste modelo e´ a fila, onde as entidades que esperam pelo recurso devem
permanecer. Por exemplo, uma fila de supermercado ou banco, um buffer ou pallet em uma
fa´brica, um armaze´m para estoque de pec¸as, uma fila de carros esperando o cruzamento, etc.
O terceiro componente deste modelo e´ a pro´pria entidade que espera e utiliza o recurso.
O diagrama ba´sico de um sistema de fila e´ o mostrado na Figura 1.5. Nesta figura esta˜o
representados o servidor (o recurso que e´ ocupado), a fila, e os eventos de entrada e sa´ıda
do sistema, geralmente modelados por eventos. Aqui, servidor e clientes sa˜o nomes gene´ricos
para representar o recurso e as entidades que o utilizam.
O modelo e´ definido completamente quando se define tambe´m:
a capacidade da fila geralmente este e´ visto como o estado deste sistema. E´ definido pelo
conjunto que este estado X pode assumir. Assim, X = {0, 1, 2, . . . , C + 1}, onde C e´ a
capacidade ma´xima da fila, e C + 1 representa a fila cheia e mais um elemento ocupado
o servidor;
a pol´ıtica de atendimento da fila define qual a pol´ıtica em que os clientes sera˜o atendidos
pelo servidor. Por exemplo, esta politica pode ser do tipo FIFO (First-In First-Out),
LIFO (Last-In First-Out), ou outra;
o processo executado pelo servidor define o que e´ realizado pelo servidor no cliente;
eventos de entrada e sa´ıda Seja por exemplo, o conjunto de eventos E = {c, p}, onde c denota
a chegada de um cliente no sistema, e p denota a partida de um cliente.
Logicamente, um sistema mais complexo pode ser modelado pela combinac¸a˜o de va´rios sistemas
como o da Figura 1.6.
1.3. EXEMPLOS DE SED 8
1
Saída de
peças
Chegada 
de peças 2
Figura 1.6: Modelo de filas para um sistema de manufatura.
A ferramenta MATLAB permite a simulac¸a˜o de modelos de sistemas a eventos discretos ba-
seados em filas. O pacote SimEvents, para o Simulink, permite especificar o modelo de um
sistema a evento discreto atrave´s de filas, servidores, chaves, e outros componentes. Permite
tambe´m a integrac¸a˜o com outras ferramentas de modelagem, como o StateChartFlow.
1.3.2 Sistemas de Manufatura
Linhas de produc¸a˜o de um sistema de manufatura e´ um dos exemplos em que o modelo de filas
pode ser utilizado, como mostrado na Figura 1.6. Os clientes podem ser vistos como pec¸as,
itens, ou ate´ pallets. Os servidores podem ser vistos como as estac¸o˜es onde a operac¸a˜o sobre a
pec¸a e´ realizada, os roboˆs, ou ferramentas que sa˜o utilizadas. A fila representa um buffer, um
armaze´m, ou os esta´gios intermedia´rios entre as estac¸o˜es de trabalho para armazenamento das
pec¸as em trabalho.
Neste exemplo em espec´ıfico, as pec¸as passam pelas duas estac¸o˜es, sendo que na entrada do
sistema existe um buffer, ale´m de outro buffer entre as duas ma´quinas, o qual tem tem uma
capacidade para armazenar ate´ duas pec¸as. Seja x2 a varia´vel de estado que indica a quantidade
atual de pec¸as no segundo buffer, e analogamente x1 para o segundo buffer. O vetor de estado
pode enta˜o ser escrito como x = [x1, x2]
T .
Seguindo o modelamento de filas, a varia´vel x2 pode assumir qualquer valor entre {0, 1, 2, 3}.
Quando o segundo buffer estiver cheio, a estac¸a˜o 2 estiver ocupada, e a estac¸a˜o 1 terminar seu
processo, a pec¸a na˜o podera´ seguir e o sistema estara´ em bloqueio ate´ que a segunda estac¸a˜o
termine seu processo e uma pec¸a seja retirada do segundo buffer. Para que este estado do
sistema seja modelado, define-se enta˜o o estado B para x2. Assim, o espac¸o de estados pode
ser definido como:
X = {(x1, x2) : x1 ≥ 0, x2 ∈ {0, 1, 2, 3, B}}
Um poss´ıvel conjunto de eventos que orienta a evoluc¸a˜o dos estados pode ser definido como:
E = {a, c1, d2}
onde:
a e´ a chegada de uma pec¸a para dentro do sistema, colocando a mesma no primeiro buffer ;
c1 e´ o te´rmino do processo executado pela primeira estac¸a˜o;
d2 e´ a sa´ıda de uma pec¸a do sistema, pela segunda estac¸a˜o.
1.3. EXEMPLOS DE SED 9
G
R
1
2
3
Figura 1.7: Uma intersecc¸a˜o controlada por um sema´foro. Adaptado de [1]
1.3.3 Sistema de Tra´fego
Em um sistema de tra´fego, um cruzamento controlado por um sema´foro pode ser visto como
um recurso (servidor) que e´ utilizado por ve´ıculos. No exemplo mostrado na Figura 1.7 existem
4 tipos de ve´ıculos que podem acessar o cruzamento. Estes ve´ıculos sa˜o tipificados em func¸a˜o
do caminho que desejam seguir pelo cruzamento:
(1,2) ve´ıculos vindos de 1 e viram a direita em direc¸a˜o a 2;
(1,3) ve´ıculos vindos de 1 e viram a esquerda em direc¸a˜o a 3;
(2,3) ve´ıculos que seguem de 2 para 3;
(3,2) ve´ıculos que seguem de 3 para 2.
O sema´foro pode estar em dois estados:
R Sinal vermelho para os ve´ıculos do tipo (1,2) e (1,3), e verde para os ve´ıculos (2,3) e
(3,2);
G Sinal verde para os ve´ıculos do tipo (1,2) e (1,3), e vermelho para os ve´ıculos (2,3) e
(3,2).
O conjunto de eventos que o sistema possui pode ser definido como:
E = {a12, a13, a23, a32, d12, d13, d23, d32, g, r}
onde:
aij indica a chegada de um ve´ıculo do tipo (i,j);
dij indica a partida de um ve´ıculo do tipo (i,j);
g indica que o sema´foro torna-se verde;
r indica que o sema´foro torna-se vermelho.
Um poss´ıvel espac¸o de estados pode ser definido como o conjunto de valores que indicam o
1.3. EXEMPLOS DE SED 10
Controle Supervisório
Interface
Controle de
Variáveis Contínuas
Sistema a ser controlado
(planta)
Eventos 
Observáveis
Comandos
(eventos)
Figura 1.8: Modelo conceitual da arquitetura de um sistema h´ıbrido. Adaptado de [1].
tamanho de cada fila de ve´ıculos, e pelo estado do sema´foro:
X = {(x12, x13, x23, x32, y) : x12, x13, x23, x32 ≥ 0, y ∈ {G,R}}
onde xij denota o valor do tamanho da fila de ve´ıculos do tipo (ij), e y indica o estado do
sema´foro.
1.3.4 Sistemas H´ıbridos
Geralmente, sistemas presentes em industrias exigem a presenc¸a de sistemas do tipo SDVC
e SED. Em um sistema de manufatura, ou sistema de automac¸a˜o, estes necessitam controlar
a sequencia de eventos, assim como controlar o fluxo de l´ıquidos, temperatura, vaza˜o, n´ıvel,
entre outras varia´veis.
Como exemplo, considera-se o sistema a ser controlado como sendo a planta. Em um n´ıvel
mais operacional, o controle atua no gerenciamento do fluxo e sequenciamento das atividades
e processos no sistema. Ele atua por comandosenviado ao sistema (liga, desliga, sinaliza,
habilita, etc), e recebe sinais pelos sensores (fim de curso, temperatura no ma´ximo, tanque
cheio, etc.).
Para o seu projeto, os subsistemas de espac¸o de estados discretos sa˜o modelados por SEDs, e
seu controle e´ enta˜o projetado. Este n´ıvel operacional interage com a planta, mas tambe´m com
o SDVC que controla os subsistemas de varia´veis cont´ınuas. Para o perfeito acoplamento entre
os sistemas SED e SDVC, pode ser necessa´ria uma interface. A Figura 1.8 mostra a arquitetura
conceitual para o monitoramento e controle h´ıbrido da planta (sistema sob controle).
A partir da de´cada de 90, houve um aumento de interesse por parte da comunidade cient´ıfica
1.3. EXEMPLOS DE SED 11
para modelamento e soluc¸a˜o de problemas deste tipo. Para a abordagem de sistemas h´ıbridos
existem extenso˜es de formalismos cont´ınuos, extensa˜o de formalismos discretos, e formalismos
mistos, sem ainda um consenso da comunidade cient´ıfica e industrial. Assim, dependendo de
certas condic¸o˜es, SDVC podem ser vistos e modelados como SED, ou vice-versa. E como pode
ser intu´ıdo, sistemas h´ıbridos e´ um assunto extenso e de interesse, por ainda carecer de soluc¸o˜es
de modelagem e analise. Mais material sobre este to´pico pode ser consultado, por exemplo,
em [3] (em seu Cap´ıtulo 13) e [1] (em seu Cap´ıtulo 5).
2 Linguagens
Como ja´ verificado, o comportamento de um Sistema a Eventos Discretos (SED) e´ descrito em
termos de uma sequeˆncia de eventos na forma e1e2e3...en. Uma sequeˆncia deste tipo define a
ordem em que os eventos ocorrem, mas na˜o possuem a informac¸a˜o temporal destes eventos.
Ou seja, neste caso analisa-se em um n´ıvel atemporal, apenas a n´ıvel lo´gico, o sistema. Para
tanto, as linguagens sera˜o utilizadas para modelar o sistema.
2.1 Linguagens em SED
Em SED a sequeˆncia de eventos descreve o comportamento deste sistema. Em uma ce´lula de
trabalho de um sistema de manufatura composta por esteiras, roboˆs, ma´quinas que realizam
operac¸o˜es, pode-se observar va´rios eventos, onde a sequeˆncia de ocorreˆncia destes eventos
descreve a evoluc¸a˜o e o comportamento deste sistema. A esteira, por exemplo, pode conter
um evento “liga esteira”, ou “pec¸a presente na esteira”. O roboˆ pode ser regido pelos eventos
“aciona operac¸a˜o”, e “operac¸a˜o realizada”, que indicam, respectivamente, que o roboˆ iniciara´
sua operac¸a˜o e tambe´m quando o roboˆ terminou a operac¸a˜o.
Logicamente, a sequeˆncia em que estes eventos ocorrem especificam a evoluc¸a˜o deste sistema.
Da´ı conclui-se tambe´m que certos eventos devem ser manipulados com o intuito de “guiar” o
sistema conforme desejado. Ou seja, que a evoluc¸a˜o deste sistema ocorra de maneira controlada,
evitando assim situac¸o˜es indesejadas, como por exemplo, evitar o acionamento do roboˆ quando
na˜o ha´ pec¸a a ser processada, ou enta˜o para evitar a colisa˜o de roboˆs. O estudo sobre o controle
do SED sera´ alvo de outro cap´ıtulo. Primeiramente e´ necessa´rio que se fac¸a o modelamento
deste sistema atrave´s de linguagens.
2.1.1 Definic¸a˜o de Linguagem
Uma linguagem e´ definida como sendo o conjunto de sequeˆncia de eventos que podem ocorrer
(fisicamente poss´ıvel) em um SED. Cada sequeˆncia de eventos e´ formada por eventos que esta˜o
definidos para este sistema. Assim, define-se E como o conjunto de todos os eventos que um
SED possui, que pode ser entendido como o alfabeto deste sistema. Cada sequeˆncia de eventos,
pode ser interpretada como uma palavra que o SED pode entender (poss´ıvel de ocorrer neste
sistema). O conjunto destas palavras representa a linguagem falada pelo sistema.
Formalmente, define-se a linguagem L sobre o conjunto E como sendo o conjunto de sequencias
(de tamanho finito) de eventos contidos em E. Por exemplo, seja E = {a, b, g} o conjunto de
eventos. A partir deste conjunto pode-se definir a linguagem
L1 = {ε, a, abb}
a qual consiste de treˆs elementos somente (|L1| = 3).
12
2.1. LINGUAGENS EM SED 13
Ou enta˜o a linguagem
L2 = {todas as sequencias poss´ıveis de tamanho 3 que comec¸am com o evento a}
a qual consiste de nove elementos (|L2| = 9).
Ou ainda a linguagem
L3 = {todas as sequencias de tamanho finito que comec¸am com o evento a}
a qual contem um tamanho infinito de elementos (|L3| =∞).
Assim como o tamanho da linguagem, pode-se determinar o tamanho da sequeˆncia de eventos.
O elemento abb da linguagem L1 formada sobre o conjunto de eventos E definido anterior-
mente, possui tamanho treˆs: |abb| = 3. A sequeˆncia com nenhum elemento (sequeˆncia vazia)
e´ denotada por ε. Ou seja, |ε| = 0. E´ importante notar que {ε} 6= ∅ pois |{ε}| = 1, ou seja,
o conjunto {ε} possui um elemento, que e´ o elemento de cadeia vazia. A importaˆncia deste
elemento sera´ vista adiante na discussa˜o sobre o modelamento de SED.
A operac¸a˜o ba´sica e essencial envolvida na criac¸a˜o das sequencias de eventos, e por con-
sequeˆncia, na criac¸a˜o das linguagens, a partir de um conjunto E de eventos, e´ a concatenac¸a˜o.
A sequeˆncia abb, um dos elementos do conjunto L1, e´ formada pela concatenac¸a˜o da sequeˆncia
ab com o evento b. A sequeˆncia ab, por sua vez, e´ formada pela concatenac¸a˜o dos eventos
a e b. O termo cadeia sera´ utilizado neste documento como um sinoˆnimo para sequeˆncia de
eventos. A concatenac¸a˜o uv de duas cadeias u e v e´ uma nova cadeia que consiste dos eventos
em u seguidos imediatamente pelos eventos em v. Observa-se tambe´m que uε = εu = u para
qualquer cadeia u.
Se tuv = s (s e´ a concatenac¸a˜o de t, u, v, onde t, u, v ∈ E∗, enta˜o:
• t e´ chamado de prefixo de s;
• u e´ chamado de subcadeia de s;
• v e´ chamado de sufixo de s.
Seja um conjunto de eventos E. A linguagem constitu´ıda de todas as poss´ıveis cadeias formadas
pelos elementos contidos em E e´ denotada por E∗, o que inclui tambe´m a cadeia vazia ε. O
operador ∗ e´ chamado de operador Fechamento Kleene1. O tamanho de E∗ e´ infinito, pois este
conjunto possui cadeias de tamanhos arbitra´rios. Por exemplo, se E = {a, b, c}, enta˜o
E∗ = {ε, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, . . .}
Qualquer outra linguagem formada sobre E e´ consequentemente um subconjunto de E∗. Em
particular, ∅, E, {ε}, e E∗ sa˜o tambe´m linguagens.
A linguagem E∗ tambe´m pode ser escrita como
E∗ = E0 ∪ E1 ∪E2 ∪ . . . ∪En ∪ . . .
onde
En = {e1e2 . . . en | ei ∈ E para cada i}
1Kleene-closure
2.1. LINGUAGENS EM SED 14
Em particular, define-se
E0 = {ε} e E1 = E
2.1.2 Notac¸a˜o com Expoente
Como ocorre com o conjunto de eventos, convenciona-se que a notac¸a˜o σi representa a cadeia
formada pela concatenac¸a˜o de “i” eventos σ. E por definic¸a˜o, σ0 = ε. Assim, aplicando-se
esta convenc¸a˜o sobre o evento a, tem-se que
a0 = ε, a1 = a, a2 = aa, a3 = aaa, e assim por diante.
E´ poss´ıvel enta˜o utilizar esta notac¸a˜o com expoentes para permitir a representac¸a˜o de lingua-
gens de uma maneira mais concisa e elegante. Na sequeˆncia sa˜o dados alguns exemplos de
linguagens utilizando-se esta notac¸a˜o:
{an | n ∈ N} = {ε, a, aa, aaa, . . .}.
{abn | n ∈ N} = {a, ab, abb, abbb, . . .}.
{anbn | n ∈ N} = {ε, ab, aabb, aaabbb, . . .}.
{(ab)n | n ∈ N} = {ε, ab, abab, ababab, . . .}.
2.1.3 Operac¸o˜es sobre Linguagens
Sendo a linguagem um conjunto, as operac¸o˜es usuais definidas para conjuntos tambe´m se
aplicam a`s linguagens. Existem, entretanto, operac¸o˜es adicionais definidas para linguagens:
Concatenac¸a˜o Seja La, Lb ⊆ E
∗, enta˜o
LaLb := {s ∈ E
∗ : (s = sasb) e (sa ∈ La) e (sb ∈ Lb)}
Ou seja, uma cadeia s esta´ contida em LaLb se esta pode ser escrita como a concatenac¸a˜o
de uma cadeia sa de La com uma cadeia sb de Lb.
Prefixo-fechamento Seja L ⊆ E∗, enta˜o
L := {s ∈ E∗ : (∃t ∈ E∗) [st ∈ L]}
Ou seja, o Prefixo-fechamento de L e´ a linguagem denotada por L e consiste de todos
os prefixos de todas as cadeiascontidas em L. Geralmente L ⊆ L. Mas quando L = L
diz-se que L e´ prefixo-fechado. Neste caso, isto significa que qualquer prefixo de qualquer
cadeia contida em L tambe´m e´ um elemento de L.
Fechamento-Kleene Seja L ⊆ E∗, enta˜o
L∗ := L0 ∪ L1 ∪ L2 ∪ . . . ∪ Ln ∪ . . .
ou ainda:
L∗ := {ε} ∪ L ∪ LL ∪ LLL ∪ . . .
Esta operac¸a˜o e´ similar a`quela definida para o conjunto E de eventos. A diferenc¸a agora
e´ que esta operac¸a˜o e´ aplicada ao conjunto L que conte´m cadeias de tamanho maior ou
igual a um.
2.2. REPRESENTAC¸A˜O DE LINGUAGENS 15
Fechamento-positivo Seja L ⊆ E∗, enta˜o
L+ := L1 ∪ L2 ∪ L3 . . .
Das definic¸o˜es anteriores segue que L∗ = L+ ∪ {ε}.
O exemplo seguinte exemplifica a aplicac¸a˜o das operac¸o˜es definidas anteriormente sobre algu-
mas linguagens. Seja E = {a, b, g} e considere as duas linguagens formadas sobre o alfabeto E:
L1 = {ε, a, abb} e L2 = {g}. Primeiramente observa-se que nenhuma das linguagens, L1 e L2,
sa˜o linguagens prefixo-fechadas, pois a cadeia ab /∈ L1 e ε /∈ L2. Considerando-se as definic¸o˜es
vistas anteriormente, o seguinte pode ser observado:
L1L2 = {g, ag, abbg}
L1 = {ε, a, ab, abb}
L2 = {ε, g}
L1L2 = {ε, a, abb, g, ag, abbg}
L∗1 = {ε, a, abb, aa, aabb, abba, abbabb, . . .}
L∗2 = {ε, g, gg, ggg, . . .}
Baseado no verificado ate´ enta˜o, e tambe´m para uma precisa˜o te´cnica, ressalta-se adicional-
mente que:
• ε /∈ ∅;
• {ε} e´ uma linguagem na˜o vazia que conte´m somente uma cadeia vazia;
• Se L = ∅ enta˜o L = ∅, e se L 6= ∅ enta˜o necessariamente ε ∈ L;
• ∅∗ = {ε} e {ε}∗ = {ε};
• ∅L = L∅ = ∅.
2.2 Representac¸a˜o de Linguagens
Como sera´ verificado, a teoria de linguagens e´ utilizada para modelamento de SEDs. Uma
linguagem L especifica todas as cadeias (sequeˆncias de eventos) aceita´veis pelo sistema. Pore´m,
nem sempre o uso direto das linguagens e´ a maneira mais pra´tica de modelar SEDs. No in´ıcio
deste cap´ıtulo, por exemplo, a linguagem L1 e´ facilmente definida pois consiste de apenas treˆs
elementos. Ja´ a linguagem L2 apresenta um certo grau de dificuldade em sua escrita, ainda
que sua definic¸a˜o seja simples. Existe a necessidade de escrever todos os nove elementos do
conjunto L2 para defini-la completamente.
Para a linguagem L3, no entanto, existe uma dificuldade na sua definic¸a˜o completa pois seu ta-
manho e´ infinito. Ainda que seja poss´ıvel sua definic¸a˜o descritiva, elencar explicitamente todos
os seus elementos e´ uma tarefa imposs´ıvel. Ainda mesmo com a notac¸a˜o por expoente, mos-
trado na Sec¸a˜o 2.1.2, muitas vezes na˜o e´ suficiente para que uma linguagem seja representada
adequadamente.
Conclui-se enta˜o que o uso direto de linguagens apenas, pode na˜o ser a maneira mais pra´tica de
se modelar e de se manipular estes modelos, haja visto o exposto anteriormente. Nos pro´ximos
cap´ıtulos sera˜o estudadas duas maneiras de se representar uma linguagem de maneira mais
2.3. MODELAGEM DE SED POR LINGUAGENS 16
compacta. Estas maneiras permitem uma maneira mais adequada de manipular estes modelos
atrave´s de operac¸o˜es bem definidas, permitindo assim sua ana´lise e verificac¸a˜o de propriedades.
2.3 Modelagem de SED por Linguagens
A modelagem de SED com o uso de linguagens e´ feito pela definic¸a˜o de duas linguagens, L e
Lm. Por vezes utiliza-se a notac¸a˜o SED = (L,Lm) como modelo do SED. Estas linguagens sa˜o
definidas como:
L modela o comportamento poss´ıvel que o SED pode ter. As cadeias desta linguagem sa˜o todas
as poss´ıveis sequencias de eventos que o SED aceita fisicamente. Ou seja, todas sequencias
poss´ıveis de ocorrerem neste sistema. Esta linguagem e´ denominada Linguagem Gerada
pelo sistema, cuja motivac¸a˜o desta denominac¸a˜o sera´ melhor entendida no estudo de
autoˆmatos.
Lm modela o comportamento marcado do sistema, denominada por este motivo de Linguagem
Marcada. Esta linguagem conte´m todas as sequencias de eventos que representam tarefas
completas (ou operac¸o˜es completas) pelo sistema SED. A definic¸a˜o de tarefas completas
e´ uma questa˜o de modelamento e depende do problema de interesse.
Ambas as linguagens L e Lm sa˜o constru´ıdas sobre um mesmo conjunto E de eventos. Ou
seja, L ⊆ E∗ e Lm ⊆ E
∗. Em um modelo SED pode-se ainda verificar o seguinte:
L = L: a Linguagem Gerada e´ prefixo fechada;
Lm ⊆ L: a Linguagem Marcada e´ um subconjunto da Linguagem Gerada.
2.4 Estudo de Caso
Seja o sistema de envase automatizado mostrado na Figura 2.1, composto por quatro subsis-
temas:
• Esteira: transporta as garrafas, da direita para a esquerda, na Figura;
• Enchimento: enche da garrafa vazia;
• Fechamento: tampa a garrafa cheia;
• Rotulac¸a˜o: coloca o ro´tulo na garrafa cheia e tampada;
Considerando-se apenas o subsistema de Enchimento, sejam dois eventos, a1 e b1, que indicam
o inicio e o fim do enchimento, respectivamente. Para este subsistema, o conjunto E de eventos
pode ser definido como:
E = {a1, b1}
Ainda para este subsistema, a linguagem L que descreve o seu comportamento pode ser escrito
como:
L = {ε, a1, a1b1, a1b1a1, a1b1a1b1, . . .}
Considerando que uma tarefa completa deste subsistema seja o enchimento completo da gar-
rafa, apenas as cadeias de L que representam ciclos completos (in´ıcio e finalizac¸a˜o do enchi-
mento) sa˜o consideradas cadeias marcadas. Assim, a linguagem marcada Lm pode ser escrita
2.4. ESTUDO DE CASO 17
sentido
EnchimentoFechamentoRotulação
P3 P2 P1
Esteira
Figura 2.1: Sistema de envase automatizado.
como:
Lm = {ε, a1b1, a1b1a1b1, a1b1a1b1a1b1, . . .}
Para este caso e´ poss´ıvel verificar as propriedades anteriormente mencionadas: L = L e L ⊃ Lm.
3 Autoˆmatos Aplicados a Sistemas a Eventos
Discretos
No cap´ıtulo anterior foi apresentada a utilizac¸a˜o de linguagens como uma forma de modelagem
de SEDs. Neste cap´ıtulo sera´ mostrada a utilizac¸a˜o de autoˆmatos como outra forma de modelar
o sistema, e que tambe´m esta´ relacionado com as linguagens. Autoˆmatos sa˜o dispositivos
capazes de aceitar ou rejeitar linguagens. Assim, e´ poss´ıvel estabelecer uma relac¸a˜o entre um
autoˆmato e a linguagem por ele aceita. Diz-se tambe´m que o autoˆmato e´ capaz de gerar uma
linguagem, e que torna o autoˆmato uma maneira de representa´-la.
Nas pro´ximas sec¸o˜es sera´ apresentado o formalismo relacionado a autoˆmatos para que seja
poss´ıvel representar, manipular e resolver problemas relacionados ao comportamento lo´gico
de SEDs. Os autoˆmatos podem ser determin´ısticos e na˜o-determin´ısticos, com transic¸o˜es a
vazio ou na˜o. Ambos estes casos, e sua relac¸a˜o direta com Sistemas a Eventos Discretos, sera˜o
estudados aqui.
3.1 Autoˆmato Determin´ıstico
Um autoˆmato e´ um dispositivo utilizado para representar uma linguagem atrave´s de regras
bem definidas. Primeiramente sera´ definido o autoˆmato, suas regras, e depois sera´ apresentada
a sua relac¸a˜o com a linguagem associada a este autoˆmato.
Uma maneira apropriada de se representar um autoˆmato e´ atrave´s de um grafo direcionado,
chamado neste caso de diagrama de transic¸a˜o de estados1. Um autoˆmato de estados finitos
sobre um conjunto finito de eventos E pode ser representado como um grafo direcionado com a
propriedade de que cada no´ do grafo emita um arco rotulado com cada evento contido em E. Os
no´s deste grafo sa˜o chamados de estados e representa o conjunto de estados do autoˆmato. Ha´
um estado especial chamado de estado inicial. Este estado e´ marcado por uma seta apontando
para este estado.
Ha´ tambe´m um conjunto de estados (possivelmente vazio) chamados de estados marcados2. A
definic¸a˜o dos estados marcados e´ uma decisa˜o de modelagem do sistema. Um estado marcado
pode representar a finalizac¸a˜o de uma tarefa, ou enta˜o o estado de repouso de um roboˆ que esta´
esperando a execuc¸a˜o da pro´xima tarefa, por exemplo. No decorrer deste documento ficara´
mais evidente,atrave´s de exemplos, a necessidade de especificac¸a˜o deste tipo de estados. Neste
documento, os estados marcados sa˜o identificados pela linha dupla utilizada no seu desenho.
A Figura 3.1 mostra um exemplo de um autoˆmato de treˆs estados. Os eventos do conjunto
E = {a, b, g} marca as transic¸o˜es entre os estados do conjunto X = {x, y, z}. O estado inicial,
denotado por x0, e´ o estado x. O conjunto de estados marcados Xm e´ o conjunto {x, z}.
1Diagrama de Estados, ou tambe´m conhecido como Ma´quina de Estados.
2Na definic¸a˜o formal de Autoˆmatos estes estados sa˜o chamados de estados finais
18
3.1. AUTOˆMATO DETERMINI´STICO 19
x y
z
a
g a, g
a
b
b
Figura 3.1: Autoˆmato com treˆs estados.
3.1.1 Definic¸a˜o de Autoˆmato
Formalmente, um autoˆmato determin´ıstico, denotado por G3, e´ definido como a seˆxtupla
G = (X,E, f,Γ, x0,Xm)
onde:
X representa o conjunto de todos os estados;
E representa o conjunto de todos os eventos definidos para o sistema e associados a G;
f representa a func¸a˜o de transic¸a˜o f : X × E → X. Ou seja, f e´ a func¸a˜o que mapeia
a combinac¸a˜o de dois elementos (um estado e um evento) a outro estado (elemento do
conjunto dos estados). Assim, f(x, e) = y significa que existe uma transic¸a˜o rotulada
com o evento e do estado x ao estado y. Quando para o estado x existir transic¸o˜es
associadas a todos os eventos contidos em E, diz-se enta˜o que a func¸a˜o f e´ completa
sobre seu domı´nio. Caso contra´rio, e´ uma func¸a˜o parcial sobre seu domı´nio.
Γ e´ a func¸a˜o de estado ativado (ou eventos executa´veis). Γ : X → 2E . Γ(x) e´ o conjunto
de todos os eventos e para os quais f(x, e) esta´ definida. Este conjunto e´ chamado de
conjunto de eventos ativos (ou eventos executa´veis) de G no estado x.
x0 e´ o estado inicial;
Xm e´ o conjunto de estados marcados. Observa-se que Xm ⊆ X.
O Autoˆmato G da Figura 3.1 tem as seguintes definic¸o˜es: X = {x, y, z}, E = {a, b, g}, x0 = z,
Xm = {x, z}. A func¸a˜o de transic¸a˜o f e´ assim definida:
f(x, a) = x f(x, g) = z
f(y, a) = x f(y, g) = y
f(z, b) = z f(z, g) = f(z, g) = y
A func¸a˜o Γ e´ assim definida: Γ(x) = {a, g}, Γ(y) = {a, b}, Γ(z) = {a, b, g}. Nota-se neste caso
que f e´ uma func¸a˜o parcial em seu domı´nio X × E pois f(x, b) e f(y, g) na˜o esta˜o definidas.
Quando o conjunto de estados X e´ finito, o autoˆmato G recebe o nome Autoˆmato Finito.
Adicionalmente, a func¸a˜o f e´ uma func¸a˜o do domı´nio X × E para a imagem X. Assim na˜o
3A raza˜o de um autoˆmato ser denotado pela letra G e´ o fato de o autoˆmato ser tambe´m chamado de “Gerador”,
pois ele e´ capaz de “gerar” linguagens, a linguagem gerada.
3.1. AUTOˆMATO DETERMINI´STICO 20
pode haver duas ou mais transic¸o˜es com o mesmo evento saindo do mesmo estado. O autoˆmato
com esta caracter´ıstica e´ dito Autoˆmato Determin´ıstico.Quando o conjunto de estados e´ finito
e a func¸a˜o f e´ definida da maneira mostrada anteriormente, da´-se o nome de Autoˆmato De-
termin´ıstico de Estados Finitos, ou Autoˆmato Finito Determin´ıstico (AFD). Esta categoria
de autoˆmatos e´ a mais usual para o estudo de SED. Pore´m, um autoˆmato pode ser na˜o-
determin´ıstico, que tambe´m tem sua importaˆncia no modelamento para SED. Esta caso sera´
estudado mais adiante.
3.1.2 Funcionamento do Autoˆmato
O autoˆmato funciona da seguinte maneira. Comec¸ando no estado inicial x0, e da ocorreˆncia de
um evento e, tal que e ∈ Γ(x0), e que Γ(x0) ⊆ E, sera´ executada uma transic¸a˜o do estado x0
para o estado f(x0, e) (onde f(x0, e) ∈ X). Este processo continua a partir deste novo estado,
na espera da ativac¸a˜o dos eventos habilitados neste novo estado.
Por convenieˆncia, a func¸a˜o f e´ definida recursivamente da seguinte maneira:
f(x, se) := f(f(x, s), e) para s ∈ E∗ e e ∈ E
Ou seja, as transic¸o˜es provocadas pela cadeia se pode ser calculada realizando-se a transic¸a˜o
f(x, s), e a partir desta transic¸a˜o, calcula-se a transic¸a˜o seguinte provocada por e. Sendo e
tambe´m uma cadeia, enta˜o aplica-se a regra anterior novamente para e.
Para precisa˜o te´cnica, define-se tambe´m a transic¸a˜o provocada pela cadeia vazia ǫ:
f(x, ε) := x
Utilizando-se ainda o exemplo da Figura 3.1 tem-se que:
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(z, aagb) = z
f(z, bn) = z para todo n ≥ 0
Esta evoluc¸a˜o de estados a partir do estado inicial e´ perfeitamente verifica´vel no autoˆmato da
Figura 3.1. Vale ressaltar aqui tambe´m que na˜o se esta´ interessado no instante de tempo em
que o evento ocorre, mas sim na transic¸a˜o de estado que este evento provoca no sistema. Neste
sentido, as transic¸o˜es de estado sera˜o consideradas instantaˆneas.
A evoluc¸a˜o do autoˆmato a partir da entrada de uma sequeˆncia de eventos ira´ determinar o
comportamento deste sistema. Assim como o instante de tempo, a causa do evento e´ irre-
levante neste momento, o qual pode ser uma entrada externa ao sistema, ou pode ser um
evento“espontaˆneo”gerado pelo sistema.
3.1.3 Linguagens Representadas pelo Autoˆmato
Aqui sera´ estudada a relac¸a˜o entre as linguagens (estudadas anteriormente) e autoˆmatos.
Partindo-se sempre do estado inicial x0, anota-se todos os poss´ıveis caminhos (sequeˆncia de
estados) que podem ser seguidos no autoˆmato, e a sequeˆncia de eventos que gera este caminho.
3.1. AUTOˆMATO DETERMINI´STICO 21
0 1
a
b
b
a
Figura 3.2: Autoˆmato que marca a linguagem Lm do Exemplo 3.1.
A concatenac¸a˜o dos eventos de cada sequeˆncia formam cadeias. Estas cadeias formam enta˜o
o conjunto chamado de linguagem gerada pelo autoˆmato G. Deste conjunto, anota-se todas
aquelas cadeias que fazem o caminho terminar em um estado marcado. Estas cadeias formam
a linguagem marcada pelo autoˆmato G.
Formalmente, a linguagem gerada L(G) por um autoˆmato G e´ definida como
L := {s ∈ E∗ : f(x0, s) e´ definida }
A linguagem marcada Lm(G) pelo autoˆmato G e´ definida como
Lm := {s ∈ L(G) : f(x0, s) ∈ Xm}
Enta˜o, uma cadeia s pertence a L(G) se, e somente se, ela corresponde a um caminho poss´ıvel
no diagrama de transic¸a˜o de estados do autoˆmato, comec¸ando pelo estado inicial x0. Isto e´
equivalente a dizer que a cadeia s pertence a L(G) se, e somente se, a func¸a˜o f e´ definida para
(x0, s).
Observa-se tambe´m que quando f e´ uma func¸a˜o total sobre seu domı´nio, enta˜o necessariamente
L(G) = E∗. Por definic¸a˜o verifica-se tambe´m que a linguagem L(G) e´ prefixo-fechada, pois um
caminho no autoˆmato e´ poss´ıvel somente se seu prefixo tambe´m o e´. Ou seja, formalmente:
L(G) = L(G)
A linguagem marcada Lm(G), e´ um subconjunto de L(G) e consiste somente das cadeias s para
as quais f(x0, s) ∈ Xm. Como todos os estados em X na˜o precisam estar marcados, Lm(G) na˜o
e´ necessariamente prefixo-fechada. A linguagem marcada e´ tambe´m conhecida como linguagem
reconhecida pelo autoˆmato. Neste caso e´ poss´ıvel dizer que o autoˆmato G e´ o reconhecedor de
uma dada linguagem.
Exemplo 3.1. Seja E = {a, b} o conjunto de eventos. Considere a linguagem
Lm = {a, aa, ba, aaa, aba, baa, bba, . . .}
Esta linguagem consiste de todas as cadeias de a’s e b’s sempre seguidas por um evento
”a”. O autoˆmato que marca esta linguagem e´ mostrado na Figura 3.2, que e´ definido como
G = {E,X, f,Γ, x0,Xm}, onde X = {0, 1}, x0 = 0, Xm = 1, e f e´ definida como segue:
f(0, a) = 1, f(0, b) = 0, f(1, a) = 1, f(1, b) = 0. A linguagem Lm pode ser facilmente verifi-
cada neste autoˆmato. Comec¸ando com o estado inicial 0, a u´nica maneira de alcanc¸ar o estado
marcado 1 e´ se ocorrer um evento a (quando f(0, a) = 1), pois se apenas o evento b ocorrer
quando no estado 0, na˜o havera´ a transic¸a˜o de estado. Neste ultimo caso, quando o evento b
ocorrer, necessita-se novamente de um evento a para que o estado marcado 1 seja novamente
atingido. Ou seja, qualquer cadeia deLm executada no autoˆmato da Figura 3.2, comec¸ando no
estado 0, terminara´ no estado marcado 1. Neste exemplo verifica-se tambe´m que a func¸a˜o f e´
completa. Assim, a linguagem gerada por este autoˆmato e´ o conjunto E∗. Ou seja, L = E∗.
3.2. AUTOˆMATO NA˜O-DETERMINI´STICO 22
0 1
a
b a
Figura 3.3: Autoˆmato que marca a linguagem Lm do Exemplo 3.2.
Exemplo 3.2. Seja agora o autoˆmato mostrado na Figura 3.3. Este autoˆmato e´ semelhante ao
anterior, com a diferenc¸a que a func¸a˜o f e´ parcial. Isto porque f(0, b) na˜o esta´ mais definida
neste autoˆmato. A linguagem L gerada L(G) por este autoˆmato e´ o composto pela cadeia
vazia ε, juntamente com: (i)as cadeias a de tamanho arbitra´rio; (ii) as cadeias anteriores
concatenadas com b; (iii)o fechamento-positivo aplicado ao conjunto anterior; (iv) as cadeias
do item anterior concatenadas com cadeias a de tamanho arbitra´rio. Formalmente pode-se
escrever:
L = {ε} ∪ {an | n ∈ N∗} ∪ {anb | n ∈ N∗}+ ∪ {anb | n ∈ N∗}+{a}
A linguagem Lm marcada Lm(G) corresponde ao subconjunto de L cujas cadeias terminam
sempre com o evento a. Formalmente:
Lm = {a
n | n ∈ N∗} ∪ {anb | n ∈ N∗}
Exemplo 3.3. Retomando-se o sistema de envase automatizado apresentado na Sec¸a˜o 2.4, as
linguagens que modelam o subsistema de enchimento podem ser representadas pelo autoˆmato
da Figura 3.4. Perceba que este autoˆmato gera as mesmas linguagens verificada para aquele
exemplo.
a1
b1
Figura 3.4: Autoˆmato de modelo do Subsistema de Enchimento do Exemplo 3.3.
Pelo que foi visto ate´ este ponto, e pelos exemplos anteriores, pode-se verificar que um autoˆmato
G e´ representado por duas linguagens: Lm(G) e L(G). O diagrama de transic¸a˜o de estados de
G conte´m toda a informac¸a˜o necessa´ria para caracterizar estas duas linguagens. Estas duas
linguagens, ou o autoˆmato, sa˜o suficientes para que um SED seja modelado.
Ao longo do estudo a ser visto neste documento, sera´ verificado que um SED real geralmente
possui a func¸a˜o f parcial. Isto se deve basicamente ao fato de que um sistema pode na˜o ser
capaz de produzir (ou executar) todas as cadeias de E∗.
3.2 Autoˆmato Na˜o-Determin´ıstico
No estudo de autoˆmatos ate´ o momento, considera-se a existeˆncia de apenas um estado inicial,
todas as transic¸o˜es sa˜o rotuladas com eventos e ∈ E, e que a func¸a˜o de transic¸a˜o seja deter-
min´ıstica, no sentido de que se e ∈ Γ(x) enta˜o e causa uma transic¸a˜o do estado x para um
u´nico estado y = f(x, e).
3.2. AUTOˆMATO NA˜O-DETERMINI´STICO 23
0 1
a
b
a
Figura 3.5: Autoˆmato Na˜o Determin´ıstico do Exemplo 3.4.
Pore´m, para fins de modelagem e analise, pode ser necessa´rio que estas considerac¸o˜es sejam
menos restritivas. Ou seja, em um Autoˆmato Finito Na˜o-Determin´ıstico (AFND) considera-se
que f(x, e) na˜o seja apenas um estado, mas um conjunto de poss´ıveis estados. Assim, e pode
causar a transic¸a˜o do estado x para um dos poss´ıveis estados representados por f(x, e). Pode-
se ainda considerar que o evento ε cause uma transic¸a˜o de estado. Este tipo de modelamento
pode representar a situac¸a˜o em que ocorra uma troca do estado interno do sistema por um
evento na˜o observa´vel, ou ainda por falta de informac¸o˜es do sistema para seu modelamento
completo. Por fim, tem-se ainda que um AFND possa ter na˜o apenas um estado considerado
inicial, mas que o estado inicial possa ser um de um conjunto de estados.
A raza˜o pela utilizac¸a˜o destas considerac¸o˜es menos restritivas pode ser motivada pela falta
de conhecimento do sistema para que enta˜o se fac¸a o modelo, ou em esta´gios iniciais do mo-
delamento, quando ainda na˜o se tem informac¸a˜o suficiente. Este pode tambe´m ser motivado
pela situac¸a˜o em que ocorram trocas de estados iniciadas por eventos na˜o observa´veis, como
ja´ mencionado anteriormente. De qualquer forma, uma AFND pode, por transformac¸a˜o, ser
representada por um Autoˆmato Finito Determin´ıstico (AFD), como sera´ visto adiante.
3.2.1 Definic¸a˜o
Formalmente um Autoˆmato Na˜o Determin´ıstico, denotado por Gnd, e´ definido pela seˆxtupla:
Gnd = (X,E ∪ {ε}, fnd,Γ, x0,Xm)
onde os componentes da equac¸a˜o acima sa˜o os mesmos ja´ definidos para o Autoˆmato Deter-
min´ıstico (sec¸a˜o 3.1.1), com excec¸a˜o de:
• fnd e´ a func¸a˜o de transic¸a˜o fnd : X×E∪{ε} → 2
X . Ou seja, fnd e´ a func¸a˜o que mapeia
a combinac¸a˜o de dois elementos (um estado e um evento, sendo o evento ε tambe´m
poss´ıvel) a um conjunto de poss´ıveis estados.
• O estado inicial pode, ele pro´prio, ser um conjunto de estados, ou seja, x0 ⊆ X.
3.2.2 Funcionamento do Autoˆmato Na˜o-Determin´ıstico
A fim de demonstrar o funcionamento de um autoˆmato na˜o determin´ıstico, sera˜o utilizados
dois exemplos.
Exemplo 3.4. Considere o AFND mostrado na Figura 3.5. Note que o evento a ocorre no
estado 0, e o estado seguinte pode ser o pro´prio estado ”0”, ou o estado ”1”. Assim, a func¸a˜o
de transic¸a˜o e´ definida como: fnd(0, a) = {0, 1}, e fnd(1, b) = {0}. As transic¸o˜es fnd(0, b) e
fnd(1, a) na˜o esta˜o definidas. Este autoˆmato marca qualquer cadeia de eventos a (a, aa, aaa,
. . . ), assim como qualquer cadeia de eventos ab se b for imediatamente seguido por a ou for o
fim da cadeia.
3.2. AUTOˆMATO NA˜O-DETERMINI´STICO 24
1 3
2
b a, b
a
ε
a
Figura 3.6: Autoˆmato Na˜o Determin´ıstico do Exemplo 3.5.
Exemplo 3.5. Considere agora o AFND mostrado na Figura 3.6. Tem-se que: fnd(1, b) = {2},
fnd(1, ε) = {3}, fnd(2, a) = {2, 3}, fnd(2, b) = {3}, e fnd(3, a) = {1}. Supondo que quando
o sistema seja iniciado ocorra uma evento a, o qual ocasiona a transic¸a˜o do estado 3 para o
estado 1. Isto so´ e´ poss´ıvel se apo´s a inicializac¸a˜o do sistema, ocorrer uma transic¸a˜o do estado
inicial 1 para o estado 3. Isto pode ser poss´ıvel haja visto o evento ε que permite a transic¸a˜o
do estado 1 para o estado 3 sem a ocorreˆncia de um evento espec´ıfico. Ale´m disto, o sistema
poderia voltar ao estado 3 apo´s o disparo de a. Conclui-se assim que o sistema possa estar em
um destes dois estados. Supondo agora que a cadeia baa seja executada. Neste caso o sistema
pode estar em qualquer um dos treˆs poss´ıveis estados, dependendo de qual a sera´ efetivamente
executado.
3.2.3 Linguagens Gerada e Marcada por um AFND
Para se obter as linguagens marcadas e geradas de um AFND, primeiramente e´ necessa´rio
achar-se o autoˆmato determin´ıstico equivalente ao AFND. Ou seja, acha-se o autoˆmato deter-
min´ıstico Gd equivalente ao autoˆmato na˜o-determin´ıstico Gnd, tal que:
L(Gd) = L(Gnd)
e que
Lm(Gd) = Lm(Gnd)
Onde: Gd = (Xd, E, fd, {x0},Xmd), e Gnd = (Xnd, E, fnd,X0,Xmnd)
A relac¸a˜o entre os componentes destas equac¸o˜es, que enta˜o especificam o autoˆmato deter-
min´ıstico equivalente, sa˜o definidas como:
• Xd = 2
Xnd
• x0 = X0
• Xmd = {xd ∈ Xd | xd ∩Xmnd 6= ∅}
• fd(xd, e) =
⋃
x∈xd
fnd(x, e)
Ou seja, apo´s a obtenc¸a˜o desta transformac¸a˜o, do autoˆmato na˜o-determin´ıstico Gnd para o
autoˆmato determin´ıstico Gd, pode-se obter as linguagens gerada e marcada de Gd, que sera˜o
tambe´m as linguagens geradas e marcadas do AFND equivalente.
Considere o Autoˆmato da Figura 3.5. Para este caso os componentes de Gnd sa˜o:
• Xnd = {0, 1}
3.3. PROPRIEDADE BLOQUEANTE 25
• E = {a, b}
• fnd(0, a) = {0, 1}; fnd(1, b) = 0; fnd(0, b) = fnd(1, a) = ∅
• X0 = {0}
• Xmnd = 0
A primeira identificac¸a˜o na transformac¸a˜o sa˜o os estados do autoˆmato determin´ıstico equiva-
lente:
Xd = 2
{0,1} = {∅, {0}, {1}, {0, 1}}
O estado inicial do autoˆmato equivalente e´ o pro´prio estado inicial do AFND:
x0 = X0 = {0}
O conjunto dos estados marcados do autoˆmato equivalente e´ dado por:
Xmd = {{0}, {0, 1}}
pois estes sa˜o os dois elementos de {xd ∈ Xd} que tem alguma intersecc¸a˜o com os elementos de
Xmnd. Para finalizar a especificac¸a˜o do autoˆmato equivalente, calculam-se astransic¸o˜es entre
os estados xd ∈ Xd. Calcula-se fd(xd, e) para cada um dos estados xd ∈ Xd:
• fd({0}, a) = fnd(0, a) = {0, 1}
• fd({0}, b) = fnd(0, b) = ∅
• fd({1}, a) = fnd(1, a) = ∅
• fd({1}, b) = fnd(1, b) = 0
• fd({0, 1}, a) = fnd(0, a) ∪ fnd(1, a) = {0, 1} ∪ ∅ = {0, 1}
• fd({0, 1}, b) = fnd(0, b) ∪ fnd(1, b) = ∅ ∪ {0} = {0}
• fd(∅, x) = ∅
A Figura 3.7 mostra o autoˆmato equivalente ao autoˆmato na˜o-determin´ıstico da Figura 3.5.
Os estados e transic¸o˜es ofuscadas sa˜o estados na˜o acess´ıveis e o estado vazio ∅. Ou seja, o
autoˆmato equivalente se resume ao autoˆmato desenhado na Figura 3.8.
3.3 Propriedade Bloqueante
Em geral, e baseado nas definic¸o˜es de G, L(G) e Lm(G), tem-se que
Lm(G) ⊆ Lm(G) ⊆ L(G)
Como ana´lise desta relac¸a˜o pode-se concluir que a primeira relac¸a˜o se deve ao fato de que Xm
pode ser um subconjunto pro´prio de X, enquanto que a segunda relac¸a˜o e´ uma consequeˆncia
direta da definic¸a˜o de Lm(G) e o fato de que L e´ prefixo-fechado por definic¸a˜o. Esta segunda
relac¸a˜o, Lm(G) ⊆ L(G) merece uma atenc¸a˜o maior, pois esta indicara´ se o autoˆmato em
questa˜o e´ bloqueante ou na˜o.
3.3. PROPRIEDADE BLOQUEANTE 26
{0}
{0, 1}
{1}
{∅}
a
b
b
b
a
a, b
a
Figura 3.7: Autoˆmato Finito Determin´ıstico equivalente ao AFND mostrado na Figura 3.5,
resultado da computac¸a˜o da equivaleˆncia.
{0} {0, 1}
a
b
a
Figura 3.8: Autoˆmato Finito Determin´ıstico equivalente ao AFND mostrado na Figura 3.5.
Deadlock
Um autoˆmato G pode alcanc¸ar um estado x onde Γ(x) = ∅ mas que x /∈ Xm. Se isto ocorrer
significa que neste estado x, na˜o ha´ nenhum evento habilitado para possibilitar a transic¸a˜o
deste estado a outro. Esta situac¸a˜o e´ chamado de deadlock pois nenhum outro evento pode
ser executado. Ale´m disto, este estado na˜o e´ marcado. Ou seja, isto significa que o autoˆmato
na˜o conseguiu finalizar a tarefa, pois como o autoˆmato esta´ bloqueado em x, na˜o tera´ como
alcanc¸ar um estado marcado. Se existir uma situac¸a˜o de deadlock no autoˆmato, significa que
necessariamente Lm(G) e´ um subconjunto pro´prio de L(G), ou Lm(G) ⊂ L(G). Isto se verifica
porque qualquer cadeia de L(G) que termine em algum estado na˜o marcado, e que esteja
bloqueado, na˜o pode ser um prefixo de uma cadeia pertencente a Lm(G).
Livelock
Outro aspecto importante a se considerar e´ a situac¸a˜o em que um conjunto de estados na˜o
marcados formam um componente fortemente conectado. Este conjunto apresenta a carac-
ter´ıstica de permitir a execuc¸a˜o de eventos que possibilitem transic¸o˜es entre os estados deste
conjunto, pore´m nenhum destes eventos leva a algum outro estado fora deste conjunto. Isto
significa que se o autoˆmato alcanc¸a este conjunto de estados, na˜o havera´ maneira de sair deste
conjunto, estando enta˜o o autoˆmato em uma situac¸a˜o chamada de livelock. Mesmo que o
autoˆmato na˜o esteja trancado em um estado, ele esta´ trancado em um conjunto de estados
onde nenhum destes e´ marcado. Ou seja, novamente a tarefa iniciada na˜o podera´ ser finalizada,
3.4. EXPRESSO˜ES REGULARES 27
0
1
2
3
4
5
a
b
g
g
a
b
a g
Figura 3.9: Autoˆmato com propriedade bloqueante analisado no Exemplo 3.6.
caracterizando-se assim tambe´m a condic¸a˜o de bloqueio.
3.3.1 Definic¸a˜o
Um autoˆmato G e´ dito bloqueante se
Lm(G) ⊂ L(G)
E o autoˆmato G e´ na˜o bloqueante se
Lm(G) = L(G)
Quando a caracter´ıstica bloqueante de um autoˆmato se verifica, este bloqueio pode ser do tipo
deadlock ou livelock. Sera´ visto mais adiante me´todos de ana´lise para identificac¸a˜o do tipo de
bloqueio para autoˆmatos bloqueantes.
Exemplo 3.6. Seja o autoˆmato G da Figura 3.9. Verifica-se claramente que o estado 5
caracteriza uma situac¸a˜o de deadlock. Isto porque se a cadeia ag (e neste caso todas as cadeias
que terminam com ag) for executada por G, nenhuma outro evento podera´ ser executado, pois
no estado 5 tem-se que f(5, σ) = ∅ | σ ∈ E. Ainda, verifica-se que Γ(5) = ∅. No autoˆmato
G percebe-se tambe´m que os estados 3 e 4, juntamente com os eventos a, b, g, formam um
componente fortemente conectado. Qualquer cadeia que termine com aa alcanc¸ara´ o estado 3,
e nesta situac¸a˜o G estara´ em livelock. Isto porque nenhum evento possibilita uma transic¸a˜o a
um estado que na˜o seja 3 ou 4, sendo nenhum destes um estado marcado. Formalmente pode-se
dizer que o autoˆmato G e´ bloqueante pois: ambas as cadeias ag e aa (e todas as que terminam
com estas cadeias) pertencem a L(G), mas nenhuma destas cadeias pertence a Lm(G). Ou
seja, isto implica em L(G) 6= Lm(G).
3.4 Expresso˜es Regulares
Como mencionado, autoˆmatos e´ uma das melhores formas de representar as linguagens descriti-
vas do comportamento de um Sistema a Eventos Discretos (SED). Assim, para o modelamento
de um SED procura-se um autoˆmato para gerar a linguagem que descreve todos poss´ıveis com-
portamentos do sistema, assim como a linguagem marcada. Pode-se afirmar (na˜o sera´ provado
aqui) que sempre e´ poss´ıvel achar um autoˆmato que represente uma linguagem, pore´m, para
alguns casos isto pode significar problemas pra´ticos para o desenho do autoˆmato. Isto porque
3.4. EXPRESSO˜ES REGULARES 28
0 1 2 3 4 5
11 31 42 52
41 51
a a a a a
b b
b
b
b
b
. . .
. . .
. . .
. . .
Figura 3.10: Autoˆmato gerador da linguagem Lm = {a
nbn : n ≥ 0}.
algumas linguagens so´ podem ser representadas por um autoˆmato com um nu´mero infinito de
estados.
Seja a linguagem marcada gerada sobre um conjunto E = {a, b} de eventos:
Lm = {a
nbn : n ≥ 0}.
Esta linguagem na˜o pode ser representada por um autoˆmato de estados finito. Um autoˆmato
que geraria esta linguagem e´ mostrado na Figura 3.10.
Definic¸a˜o 3.1. Toda a linguagem que pode ser representada por um autoˆmato de estados finito
e´ dita Linguagem Regular.
Ou seja, autoˆmatos na˜o sa˜o uma maneira pra´tica para representar um linguagens do tipo na˜o-
regular. Seja L1 e L2 duas linguagens regulares. Enta˜o as linguagens a seguir tambe´m sa˜o
linguagens regulares:
1. L1
2. L∗1
3. Lc1 := E
∗ \ L1
4. L1 ∪ L2
5. L1L2
6. L1 ∩ L2
As linguagens regulares sa˜o escritas a partir de expresso˜es regulares, que sa˜o expresso˜es ba´sicas
realizadas sobre conjuntos. Para compactac¸a˜o da notac¸a˜o, as expresso˜es regulares ba´sicas sa˜o
definidas como mostrado na Tabela 3.1.
De maneira recursiva, pode-se definir as seguintes regras:
1. Sa˜o expresso˜es regulares:
a) ∅ que denota um conjunto vazio;
3.5. OPERAC¸O˜ES UNA´RIAS 29
Notac¸a˜o utilizada Significado Descric¸a˜o
+ ∪ A unia˜o de duas cadeias.
u {u} Conjunto da cadeia u.
u∗ {u}∗ = {ε, u, uu, . . .} Fechamento-kleene de u.
(u+ v) {u, v} = {u} ∪ {v} Unia˜o das cadeias u e v.
uv {uv} Concatenac¸a˜o de u e v.
Tabela 3.1: Convenc¸o˜es adotadas para escrita das expresso˜es regulares
b) ε que denota o conjunto ε
c) e que denota o conjunto {e}, para qualquer e ∈ E;
2. Se r e s sa˜o expresso˜es regulares, enta˜o rs, (r + s), r∗, s∗, tambe´m sa˜o;
3. Outras expresso˜es regulares sa˜o formadas pela aplicac¸a˜o das regras 1 e 2 um nu´mero
finito de vezes.
A ordem de precedeˆncia para aplicac¸a˜o destas operac¸o˜es sa˜o:
1. Fechamento Kleene;
2. Concatenac¸a˜o;
3. Unia˜o.
Exemplo 3.7. Seja um conjunto de eventos E = {a, b, g}, a linguagem regular denotada pela
expressa˜o regular (a+ b)g∗ pode ser calculada como:
L = (a+ b)g∗
= {a, b}{g}∗
= {a, b}{ε, g, gg, ggg, . . .}
= {a, b, ag, bg, aag, bbg, aggg, bggg, . . .}
Exemplo 3.8. Seja um conjunto de eventos E = {a, b, g}, a linguagem regular denotada pela
expressa˜o regular (ab)∗ + g pode ser calculada como:
L = (ab)∗ + g
= {ε, ab, abab, ababab, . . .} ∪ {g}
= {ε, g, ab, abab, ababab, . . .}
3.5 Operac¸o˜es Una´rias
Operac¸o˜es una´rias sa˜o operac¸o˜es definidaspara autoˆmatos que podem alterar o conjunto dos
estados deste autoˆmato, mas na˜o altera o conjunto de eventos E.
3.5.1 Acess´ıvel
Em um autoˆmato gene´rico G pode existir a situac¸a˜o em que um ou mais estados na˜o sejam
alcanc¸a´veis, ou acess´ıveis, a partir do estado inicial x0. Enta˜o se x e´ na˜o acess´ıvel, isto equivale
3.5. OPERAC¸O˜ES UNA´RIAS 30
a dizer que na˜o existe uma cadeia s ∈ L(G) que fac¸a com que f(x0, s) = x | x ∈ X. Se
estes estados na˜o acess´ıveis forem retirados do autoˆmato, a linguagem gerada e a linguagem
marcada permanecera˜o inalteradas. Define-se enta˜o a operac¸a˜o Ac(G) como a operac¸a˜o que
retira do autoˆmato G todos os estados inacess´ıveis, assim como todas as transic¸o˜es ligadas a
estes estados.
Formalmente esta operac¸a˜o e´ definida como
Gac = Ac(G) := (Xac, E, fac, x0,Xac,m) onde
Xac = {x ∈ X : (∃s ∈ E
∗)[f(x0, s) = x]}
Xac,m = Xm ∩Xac
fac = f |Xac×E→Xac
Fazendo-se a interpretac¸a˜o desta definic¸a˜o tem-se que:
Gac e´ o novo autoˆmato com todos os estados acess´ıveis;
Xac todo o estado x que pertence a X, e que para este estado existe uma cadeia s que permite
alcanc¸a-lo a partir de x0 (f(x0, s) = x), faz pate deste conjunto.
Xac,m a intersecc¸a˜o dos estados acess´ıveis com os estados marcados do autoˆmato G resulta
no conjunto dos estados marcados e acess´ıveis;
fac e´ a func¸a˜o de transic¸a˜o definida agora sobre um domı´nio possivelmente reduzido: Xac×E.
3.5.2 Coacess´ıvel
Em um autoˆmato gene´rico G pode existir a situac¸a˜o em que na˜o haja um caminho no diagrama
de estados deste estado x para nenhum dos estados marcados. A este estado x da´-se o nome
de estado na˜o co-acess´ıvel. Aplicar a operac¸a˜o CoAc(G) significa retirar todos os estados que
na˜o sa˜o co-acess´ıveis, e todas as transic¸o˜es ligadas a estes estados. O resultado desta operac¸a˜o
e´ um autoˆmato cujos estados sa˜o todos co-acess´ıveis.
Formalmente esta operac¸a˜o e´ definida como
Gcoac = CoAc(G) := (Xcoac, E, fcoac, x0,coac,Xm) onde
Xcoac = {x ∈ X : (∃s ∈ E
∗)[f(x, s) ∈ Xm]}
x0,coac =
{
x0 se x0 ∈ Xcoac
indefinido outros casos
fcoac = f |Xcoac×E→Xcoac
Fazendo-se a interpretac¸a˜o desta definic¸a˜o tem-se que:
Gcoac e´ o novo autoˆmato com todos os estados co-acess´ıveis;
Xcoac todo o estado x que pertence aX, e que para este estado existe uma cadeia s que permite
a partir dele alcanc¸ar algum estado marcado f(x, s) ∈ Xm, faz pate deste conjunto.
x0,coac se o estado inicial x0 for co-acess´ıvel, (x0 ∈ Xcoac), enta˜o x0 continua sendo o estado
inicial no autoˆmato co-acess´ıvel Gcoac. Caso contra´rio, x0 sera´ retirado do autoˆmato, e
Gcoac tera´ um estado inicial indefinido.
3.6. MINIMIZAC¸A˜O DO ESPAC¸O DE ESTADOS 31
fac e´ a func¸a˜o de transic¸a˜o definida agora sobre um domı´nio possivelmente reduzidoXcoac×E.
A operac¸a˜o CoAc(G) pode diminuir em tamanho a linguagem L(G), pois aqueles estados na˜o
co-acess´ıveis retirados pela operac¸a˜o CoAc(.) podem ser acess´ıveis. Entretanto, a operac¸a˜o
CoAc(.) na˜o afeta a linguagem Lm(G), pois o estado deletado (e portanto na˜o co-acess´ıvel)
na˜o pode estar em nenhum caminho do estado x0 para algum estado de Xm.
Quando G = CoAc(G) enta˜o G e´ dito com sendo um autoˆmato co-acess´ıvel, e neste caso,
L(G) = Lm(G). Esta observac¸a˜o significa que a co-acessibilidade e´ fortemente relacionada
com o conceito de autoˆmato bloqueante. Ou seja, se um autoˆmato for co-acess´ıvel, ele necessa-
riamente sera´ na˜o bloqueante.
3.5.3 Trim
Um autoˆmato e´ definido como trim quando este autoˆmato for tanto acess´ıvel quanto co-
acess´ıvel. Ou seja, o autoˆmato que sofrer as operac¸o˜es de CoAc(.) e Ac(.) (independentemente
da ordem em que estas operac¸o˜es sejam aplicadas) sera´ um autoˆmato trim. Formalmente a
operac¸a˜o Trim e´ definida como
Trim(G) := CoAc[Ac(G)] = Ac[CoAc(G)]
Exemplo 3.9. Seja o autoˆmato G da Figura 3.11a. Aplicar a operac¸a˜o CoAc(G) significa pri-
meiramente verificar se existe um ou mais estados que, a partir destes estados, na˜o seja poss´ıvel
se alcanc¸ar o estado marcado 2. Isto e´ verificado para os estados 3, 4 e 5. Assim, apo´s aplicar-
se a operac¸a˜o CoAc(G) tem-se o autoˆmato Gcoac, mostrado na Figura 3.11b. O autoˆmato Gcoac
e´ co-acess´ıvel, pore´m na˜o acess´ıvel, pois o estado 6 na˜o e´ alcanc¸a´vel por nenhum caminho a
partir de x0. Enta˜o, aplicando-se Ac(Gcoac), o estado 6 sera´ retirado, e o autoˆmato resultante
sera´ um autoˆmato trim. Ou seja, Gtrim = Ac(GCoAc) = Ac(CoAc(G)) = CoAc(Ac(G)). Esta
u´ltima igualdade e´ valida pois a ordem em que as operac¸o˜es Ac(.) e CoAc(.) sa˜o aplicadas,
na˜o altera o resultado, que sera´ o mesmo autoˆmato trim. A Figura 3.11c mostra o autoˆmato
Gtrim.
3.6 Minimizac¸a˜o do Espac¸o de Estados
Como visto na composic¸a˜o de autoˆmatos, o nu´mero de estados pode crescer muito rapidamente.
Em SED se esta´ interessado em obter os autoˆmatos com o menor nu´mero de estados poss´ıveis,
para que a analise dos modelos por autoˆmatos requeira menos recursos computacionais.
Toda linguagem regular e a linguagem marcada podem ser geradas por mais de um autoˆmato.
Diz-se que dois autoˆmatos G1 e G2 sa˜o equivalentes se, e somente se:
L(G1) = L(G2) e Lm(G1) = Lm(G2)
Existe pore´m um autoˆmato GCcan que tambe´m gera a linguagem L e Lm, cujo tamanho do
conjunto de estados Xcan (|Xcan|) e´ mı´nimo. Este autoˆmato Gcan recebe o nome de gerador
canoˆnico das linguagens modelo do SED.
3.6. MINIMIZAC¸A˜O DO ESPAC¸O DE ESTADOS 32
0
1
2
3
4
5
6
a
b
g
g
a
a
b
b
a g
(a)
0
1
2 6
a
b
g
b
(b)
0
1
2
a
b
g
(c)
Figura 3.11: (a) Autoˆmato G do Exemplo 3.9. (b) CoAc(G). (c) Trim(G).
3.6.1 Equivaleˆncia de Estados
A minimizac¸a˜o de estados de um autoˆmato G se da´ pela procura de equivaleˆncia dos estados
em X. Para dois estados x e y, pertencentes a X, algumas observac¸o˜es podem ser feitas:
1. Se x ∈ Xm e y /∈ Xm, enta˜o os estados x e y nunca podera˜o ser equivalentes;
2. Suponha que x e y sejam ambos de Xm ou nenhum dos dois esteja em Xm. Neste caso
x e y podem ser equivalentes. Se f(x, e) = f(y, e) para qualquer evento e ∈ E ∪ {ε},
enta˜o x e y sa˜o equivalentes, pois ambos ira˜o para a mesma sequencia de estados para
qualquer cadeia aplicados a eles;
3. A observac¸a˜o anterior ainda vale se f(x, e) = y e f(y, e) = x para um ou mais eventos
e, pois a func¸a˜o dos estados x e y sa˜o intercambia´veis depois de e. Logicamente, para
todos os outros eventos e a seguinte relac¸a˜o deve ser va´lida: f(x, e) = f(y, e);
4. De modo geral, seja R o conjunto de estados tal que: ou R ⊆ Xm ou R ∩ Xm = ∅.
Enta˜o R consiste de estados equivalentes se f(x, e) = z /∈ R implicar em f(y, e) = z,
para qualquer x, y ∈ R. Ou seja, se todas as poss´ıveis transic¸o˜es dos estados em R para
estados fora de R devem ser causadas pelo mesmo conjunto de eventos, e devem ter o
mesmo pro´ximo estado.
Com base nestas observac¸o˜es pode ser definido um procedimento para que se identifiquem as
equivaleˆncia de estados de maneira sistema´tica. Para tal existe um Algoritmo de determinac¸a˜o
das equivaleˆncia entre os estados, e que sera´ definido na sequencia.
3.6. MINIMIZAC¸A˜O DO ESPAC¸O DE ESTADOS 33
q1
q2
qn-1
...... ... ...
qn
...
...
...q0 q1 qn-2 qn-1
Figura 3.12: Tabela para aplicac¸a˜o do Algoritmo 1
3.6.2 Algoritmo para Minimizac¸a˜o de Estados
O algoritmo aqui descrito baseia-se na identificac¸a˜o de equivaleˆncia de estados aos pares.
Sempre que um par na˜o pode ser equivalente ele e´ exclu´ıdo. Inicia-se com a exclusa˜o de todos
os pares em que sa˜o formados por um elemento do conjunto X e um elemento formado pelo
conjunto Xm. Isto e´ feito devido a` primeira observac¸a˜o descrita na sec¸a˜o 3.6.1. A todos
os outros pares na˜o marcados no in´ıcio sa˜o verificadas as existeˆncias