Laboratório de Sistemas e Sinais
Máquinas de Estados
Luı́s Caldas de Oliveira
Março 2009
As máquinas de estados são sequenciais: começam num estado inicial, e reagem aos valores de entrada transitando sequencialmente entre estados. A realização de máquinas de estados em software é razoavelmente simples.
Neste laboratório, exploraremos a sua construção e progrediremos até à realização de uma implementação que faça
a composição de duas máquinas de estados.
1 Introdução
1.1
Cadeias de caracteres em Matlab
As máquinas de estados operam sobre sequências de sı́mbolos de um alfabeto. Por vezes esse alfabeto é
numérico mas, no caso mais geral, é um conjunto de elementos com nomes arbitrários. Por exemplo, a entrada
para uma máquina que funcione como um gravador de chamadas será:
Entradas = {toca, atende, fimdasaudacão, fimdamensagem, nulo}
Cada elemento do conjunto anterior pode ser representado em Matlab como uma cadeia de caracteres (help
strings). As cadeias de caracteres são delimitadas por plicas. Por exemplo:
>> x = ’toca’;
A própria cadeia de caracteres é uma matriz de caracteres, sendo assim é possı́vel indexar os caracteres individuais
>> x (1:3)
ans =
toc
Podem-se juntar cadeias de caracteres tal como matrizes normais,
>> y = ’o’;
>> z = ’sino’;
>> [x, y, z]
ans =
tocaosino
Isto pode não ser necessariamente o que é pretendido. Pode-se querer construir uma matriz de cadeias de
caracteres em que cada elemento é ele próprio uma cadeia de caracteres (em vez de um só caracter). Esse objecto
pode ser representado em Matlab como um cell array,
>> c = {’toca’, ’atende’, ’fim da saudação’, ’fim da mensagem’, ’nulo’}
Notar as chavetas em vez dos parenteses rectos habituais. Um cell array em Matlab é uma matriz em que os
seus elementos são objectos Matlab arbitrários (tais como cadeias de caracteres e matrizes). Os cell arrays podem
ser indexados tal como os vectores normais
1
>> c(1)
ans =
’toca’
Pretende-se muitas vezes testar uma cadeia de caracteres para saber se é igual a outra cadeia. O operador ==
não pode ser usado na comparação de cadeias de caracteres ou em células de um cell array,
>> c = ’toca’;
>> if (c == ’atende’) result = 1; end
??? Error using ==> ==
Array dimensions must match for binary array op.
>> c = {’toca’, ’atende’, ’fim da saudação’, ’fim da mensagem’, ’nulo’}
??? Error using ==> ==
Function ’==’ not defined for cariables of class ’cell’
As cadeias de caracteres devem ser comparadas usando strcmp ou switch (ver a ajuda on-line destes
comandos).
>> c = {’toca’, ’atende’, ’fim da saudação’, ’fim da mensagem’, ’nulo’}
1.2
Ficheiros de comandos
Em Matlab podem-se guardar programas em ficheiros que se mandam executar a partir da linha de comandos.
A um ficheiro de comandos deste tipo dá-se o nome de m-file, e tem um nome na forma comando.m em que
comando é o nome do comando a introduzir na linha de comandos para executar o programa.
Pode-se usar um qualquer editor de texto para criar e editar uma m-file mas o Matlab inclui ele próprio um
editor. Para chamar esse editor selecciona-se New e M-file do menu File do Matlab.
Para executar o programa, o Matlab precisa de saber onde encontrar o novo ficheiro de comandos. O modo
mais simples de resolver isto é guardar o ficheiro na directoria corrente do Matlab. Por exemplo, se os ficheiros de
comandos estão na directoria
D:\home\lco
poderá utilizá-los fazendo
>> cd D:\home\lco
>> pwd
ans =
D:\home\lco
O comando cd faz com que o Matlab altere a directoria de trabalho. O comando pwd retorna a directoria de
trabalho actual (a mnemónica é present working directory).
O Matlab pode procurar a presença de m-files numa sequência de directorias usando o comando path. Por
exemplo, em vez de mudar a directoria corrente, poderı́amos ter usado o seguinte,
>> path(path, ’D:\home\lco’);
Este comando indica ao Matlab que deverá procurar os ficheiros de comandos onde já procurava anteriormente
(o primeiro argumento path) e na nova directoria.
Supondo que se cria um ficheiro ola.m contendo,
% OLA - diz olá.
disp(’Olá’)
2
A primeira linha é um comentário. O comando disp imprime o seu argumento no ecrã sem mostrar o nome
da variável. Se se escrever o seguinte na linha de comandos,
>> ola
Olá
Nos nomes dos comandos podem-se trocar as letras minúsculas por maiúsculas, ou seja, OLA e ola são a
mesma coisa. O comentário no inı́cio do ficheiro é usado pelo comando help do Matlab.
>> help ola
OLA - diz olá.
O comando ola anterior corresponde a um programa e não a uma função, pois não existe valor de retorno.
Para definir uma função é necessário incluir o comando function no ficheiro. Por exemplo, se o ficheiro
reverse.m contiver:
function result = reverse(argument)
% REVERSE - retorna o array passado como argumento invertido
result = argument (length(argument):-1:1);
podemos fazer
>> reverse(’olá’)
ans =
álo
O valor retornado são os caracteres da cadeia passada como argumento em ordem inversa.
Uma função pode ter qualquer número de argumentos e valores de retorno. Para definir uma função com dois
argumentos e dois valores de retorno pode-se usar
function [res1, res2] = fun(arg1, arg2)
os valores de res1 e res2 são atribuı́do dentro do ficheiro. Para usar esta função podemos atribuir os valores
de retorno a duas variáveis diferentes,
[r1, r2] = fun(a1, a2)
Os nomes dos argumentos e das variáveis de retorno são arbitrários
2 Trabalho para os alunos
1. Considere o seguinte cell array
cellarray = {’a’, ’b’, ’a’, ’a’, ’b’}
(a) Execute a seguinte sequência de comandos:
n = 0
for e = cellarray
if strcmp(e,’a’) n = n + 1;
end
end
(b) Em seguida, defina uma função conta que conte as ocorrências do caracter a em qualquer argumento.
(c) Quantas ocorrências do caracter a existem em x e em y? Por que são diferentes?
>> x = [’a’, ’b’, ’c’, ’a’, ’aa’]
>> y = {’a’, ’b’, ’c’, ’a’, ’aa’}
(d) Modifique o comando anterior para que receba dois argumentos em que o primeiro é o caracter cujo
número de ocorrências se pretende contar no segundo argumento.
3
{0}/0
{1}/1
{1}/0
{0}/1
0
1
Entradas = {0, 1, nulo}
Saı́das = {0, 1, nulo}
Figura 1: Máquina de estados.
2. A função input pode ser usada para pedir interactivamente dados ao utilizador.
(a) Crie e execute um ficheiro de comandos Matlab com o seguinte conteúdo:
% Cumprimenta o utilizador
while 1
resp = input(’Como te chamas? ’, ’s’);
if (strcmp(resp, ’sair’)|strcmp(resp, ’’))
break;
end
disp([’Olá ’ resp])
end
(b) Escreva um programa que pede ao utilizador uma cadeia de caracteres e que usa a função conta para
devolver o número de ocorrências de a nessa cadeia.
3. Considere a máquina de estados da figura 1.
(a) Construa uma m-file contendo uma definição da sua função de actualizacão. Verifique se corresponde
ao diagrama apresentado.
% The next result is 0 or 1.
function [proximo, saida] = actualiza(estado, entrada)
%
switch estado
case ’0’
switch entrada
case ’0’
proximo = ’0’;
saida = ’0’;
case ’1’
proximo = ’1’;
saida = ’0’;
otherwise
proximo = estado;
saida = ’nulo’;
end
case ’1’
switch entrada
case ’0’
proximo = ’0’;
saida = ’1’;
case ’1’
proximo = ’1’;
saida = ’1’;
4
otherwise
proximo = estado;
saida = ’nulo’;
end
end
(b) Em seguida, crie um programa que solicite ao utilizador uma entrada e, se esta estiver no alfabeto da
máquina, que reaja ao seu valor, voltando a solicitar uma nova entrada. Se a entrada não pertencer ao
alfabeto da máquina, o programa deverá assumir que a entrada é nulo e não deverá mudar de estado
(stutter). Verifique que a sua função de actualização tem em consideração a entrada nulo.
4. Projecte um animal de estimação virtual1 , neste caso um gato, construindo uma máquina de estados, escrevendo uma função actualizacão, e escrevendo um programa para executar repetidamente essa função. O
gato virtual deverá ter o seguinte comportamento:
O gato começa por estar feliz. Se lhe fizerem festas ele ronrona. Se lhe derem comida ele
vomita. Com o passar do tempo, ele fica com fome e roça-se nas pernas das pessoas. Se lhe derem
comida quando está com fome ele ronrona e fica feliz. Se lhe fizerem festas quando tem fome, ele
morde. Se o tempo passar enquanto ele está com fome, ele morre.
(a) Crie uma função de actualização para o seu gato virtual em que as palavras em itálico na descrição
anterior devem ser elementos ou do espaço de estados ou dos alfabetos de entrada ou de saı́da. Apresente os alfabetos de entrada e de saı́da e bem como o diagrama da transição de estados. Escreva um
programa para executar a máquina de estados até que o utilizador escreva sair.
(b) Construa uma máquina de estados que produza entradas para o seu gato virtual de modo que o gato
nunca morra. Essa máquina de estados deverá gerar saı́das tempo e comida de tal maneira que o gato
nunca alcança o estado de morre.
Repare que esta máquina de estados não tem entradas particularmente significativas. O alfabeto de
entrada poderá ser
Entradas = {1, nulo}
onde uma entrada de 1 significa que a máquina deverá produzir uma saı́da não-nula, e uma entrada
nulo deverá produzir uma saı́da nula.
(c) Escreva um programa onde sua máquina de estados alimentadora seja composta em cascata com sua
máquina de estados do gato virtual, e verifique que o gato não morre. A máquina de estados deve
permitir a passagem do tempo (produzindo um número infinito de saı́das tempo) mas deve ser tão
simples quanto possı́vel.
Um dos objectivos principais deste exercı́cio é o de mostrar que as máquinas de estado sistematicamente construı́das podem ser compostas com facilidade.
A máquina de estados alimentadora pode ser considerada um controlador em cadeia aberta porque
controla o animal de estimação virtual sem observar a sua saı́da. No entanto, na maioria dos sistemas
práticos, não é possı́vel projectar um controlador em cadeia aberta. O laboratório seguinte explorará os
controladores em cadeia fechada.
1 Este
problema inspirou-se no jogo Tamagotchi feito por Bandai em Japão. Tamagotchi pode ser traduzido por “pequeno ovo” foi extremamente popular no final dos anos 90 e tinha um comportamento consideravelmente mais complexo do que o descrito neste exercı́cio.
5