3. Teoria dos Autómatos

• A teoria de autómatos é o estudo de computadores abstratos, também chamados de “máquinas”.

• Em 1930, antes de existirem computadores, A. Turing desenvolveu uma máquina abstrata que tinha todas as características dos computadores atuais, ao menos no que se refere ao quanto eles poderiam calcular.

• O objetivo de Turing era descrever com exatidão o que uma máquina de computação seria e o que ela não seria capaz de fazer.

• As conclusões de Turing aplicam-se não apenas à sua máquina, mas também as máquinas reais de hoje.

1-1

• Na década de 1940 e 1950, tipos de máquinas simples, que hoje são chamados de “autómatos finitos”, foram estudados por diversos pesquisadores.

• No final dos anos 50, o linguista N. Chomsky iniciou o estudo de “gramáticas” formais. Essas gramáticas têm um relacionamento estreito com os autómatos abstratos e que hoje servem como base de importantes componentes de software, incluindo parte dos compiladores.

1-2

• Em 1969, S. Cook estendeu o estudo de Turing do que podia e não podia ser calculado.

• Ele conseguiu separar os problemas que podem ser resolvidos de forma eficiente por computadores daqueles que poderiam em princípio ser resolvidos, mas que na prática levam tanto tempo para serem solucionados que os computadores são inúteis para solucioná-los

• Tais problemas são chamados “intratáveis” ou “NP-difíceis” (NPHard). Mesmo com a melhoria exponencial na velocidade dos computadores (Lei de Moore) é muito pouco provável que haja impacto significativo na habilidade de resolver grandes instâncias de problemas intratáveis.

1-3

• Todos esses desenvolvimentos teóricos têm ligação direta com o que os cientistas da computação fazem hoje.

• Por exemplo: a teoria dos problemas intratáveis permite-nos deduzir se ao encontrar um problema temos chance de conseguir construir um programa para resolvê-lo (porque ele não é intratável) ou se teremos de descobrir algum modo de contornar o problema intratável.

1-4

• Um autómato é uma construção feita de estados, projetado para determinar se a entrada pode ser aceite ou rejeitada. Parece-se muito com um jogo de tabuleiro básico em que cada espaço no tabuleiro representa um estado.

• Cada estado tem informações sobre o que fazer quando uma entrada é recebida pela máquina.

• Quando a máquina recebe um nova entrada, ela analisa o estado e escolhe um novo local baseada na informações sobre o que fazer ao receber essa entrada nesse estado.

• Quando não há mais entradas, o autómato pára e o espaço onde está quando conclui determina se o autómato aceita ou rejeita esse conjunto específico de entradas.

1-5

• Um autómato executa (ou roda) quando lhe é dada uma sequência de entradas (individualmente) em passos de tempo discretos.

• Um autómato processa uma entrada que é obtida a partir de um conjunto de símbolos ou letras, que é chamado de alfabeto.

• Os símbolos recebidos pelo autómato como entrada, em qualquer etapa (ou passo) são uma sequência de símbolos chamados de palavras.

• Um autómato contém um conjunto finito de estados. Para cada instante durante a execução, o autómato está em um de seus estados. Ao receber uma nova entrada, move-se para outro estado (ou faz a transição) baseado numa função que tem o estado atual e o símbolo como parâmetros. Esta função é chamada de função de transição

1-6

• O autómato lê os símbolos da palavra de entrada, um após o outro, e faz a transição de estado para estado, de acordo com a função de transição, até a palavra ser totalmente lida.

• Uma vez que a palavra de entrada foi lida, diz-se que o autómato deve parar. O estado no qual o autómato pára é chamado de estado final.

• Dependendo do estado final, o autómato pode aceitar ou rejeitar uma palavra de entrada.

• Existe um subconjunto de estados do autómato, que é definido como o conjunto de estados de aceitação. Se o estado final é um estado de aceitação, então o autómato aceita a palavra. Caso contrário, a palavra é rejeitada.

1-7

• O conjunto de todas as palavras aceites por um autómato é chamado de linguagem reconhecida pelo autómato. Qualquer subconjunto da linguagem de um autómato é uma linguagem reconhecida pelo autómato.

• Em suma, um autómato é um objeto matemático que toma uma palavra como entrada e decide se a aceita ou rejeita. Como todos os problemas computacionais são redutíveis para o problema de aceitação/rejeição de palavras

1-8

• Teoria dos autómatos:

– é o estudo das máquinas abstratas ou autómatos, bem como problemas computacionais que podem ser resolvidos usando esses objetos.

– É objeto de estudo tanto da Ciência da Computação Teórica como da Matemática Discreta. A palavra autómato vem da palavra grega αὐτόματα que significa “autoação” (em tradução livre), isto é, sem influência externa.

1-9

• "Autómatos finitos" ou “máquinas de estado finito" são modelos matemáticos usados para conceber programas de informáticos ou circuitos lógicos digitais.

• É concebido como uma máquina abstrata que pode ter um número finito de estados.

• São bons modelos para computadores com uma quantidade extremamente limitada de memória, como por exemplo, um elevador, relógios automáticos da porta, ou digital.

1-10

• Os autómatos finitos constituem um modelo útil para muitos elementos importantes de hardware e software.

• Alguns exemplos:

– Software para projetar e verificar o comportamento de circuitos digitais

– Analisador Léxico de um compilador típico (isto é, componente que divide o texto de entrada em unidades lógicas, como identificadores, palavras chave, etc.)

– Software para examinar grandes corpos de texto, como páginas Web

– Software para verificar sistemas de todos os tipos que tem um número finito de estados distintos, como protocolos de comunicação ou segurança

1-11

• Estes elementos têm como características estarem a todo o momento num determinado “estado” de um conjunto finito deles.

• Como o conjunto é finito a história toda de execução não pode ser memorizada, assim o sistema deve ser projetado a fim de memorizar apenas o que é relevante.

• A vantagem de usar um número finito de estados é que é possível implementá-lo de uma forma simples em hardware como um circuito, ou num software que possa tomar decisões examinando apenas um número limitado de dados ou a própria posição no código.

1-12

Exemplo de autómato finito:

• um interruptor que memoriza se está no estado “ligado” ou “desligado”, e permite que o utilizador pressione um único botão cujo efeito será diferente de acordo com o estado em que o interruptor se encontra, ou seja, se ele estiver desligado e for pressionado ele irá ligar, e vice-versa.

1-13

• Os estados estão representados por círculos, e a ação (ou “entrada”) está representada pelos arcos. Neste caso temos os estados ligado e desligado, e ambos os arcos representam a ação de pressionar o botão. O estado inicial é indicado pela palavra “início” e por uma seta que leva a este estado. Frequentemente também precisamos indicar um ou mais estados “finais” ou de “aceitação”, que representam que a entrada é “válida”, neste caso utilizamos círculos duplos para representar tais estados.

1-14

Outro exemplo:

• um autómato que reconhece a palavra chave case: ele tem cinco estados que representam desde a string vazia até a palavra completa, passando por todos os seus prefixos.

• O único estado de aceitação é aquele em que a palavra aparece completa. Podemos imaginar este autómato como parte de um analisador léxico, que estará analisando um a um os caracteres do programa.

1-15

• Uma máquina de estados finita (FSM - do inglês Finite State Machine) ou autómato finito é um modelo matemático usado para representar programas de computadores ou circuitos lógicos.

• O conceito é concebido como uma máquina abstrata que deve estar num número finito de estados. A máquina está em apenas um estado por cada vez: este estado é chamado de estado atual.

• Um estado armazena informações sobre o passado, isto é, ele reflete as mudanças desde a entrada num estado, no início do sistema, até ao momento presente.

• Uma transição indica uma mudança de estado e é descrita por uma condição que precisa ser realizada para que a transição ocorra. Uma ação é a descrição de uma atividade que deve ser realizada num determinado momento.

1-16

• Máquinas de estado finitos podem modelar um grande número de problemas, entre os quais: – a automação de design eletrônico,

– projeto de protocolo de comunicação,

– análise e outras aplicações de engenharia.

• Na biologia e na pesquisa da inteligência artificial, máquinas de estado ou hierarquias de máquinas de estado são, por vezes, utilizadas para descrever sistemas neurológicos e em linguística para descrever as gramáticas das linguagens naturais.

1-17

• Um estado descreve um nó de comportamento do sistema em que está à espera de uma condição para executar uma transição.

• Normalmente, um estado é introduzido quando o sistema não reage da mesma forma para uma mesma condição.

• No exemplo de um sistema de rádio de carro, quando se está ouvindo uma estação de rádio, o estímulo "próximo" significa ir para a próxima estação. Mas quando o sistema está no estado de CD, o estímulo "próximo" significa ir para a próxima faixa.

1-18

• O mesmo estímulo desencadeia ações diferentes, dependendo do estado atual. Em algumas representações de máquinas de estado finitas, também é possível associar ações a um estado:– Ação de entrada: o que é realizado ao entrar no estado,

– Ação de saída: o que é executado ao sair do estado.

• A transição é um conjunto de ações a serem executadas quando uma condição for cumprida ou quando um evento é recebido.

• Máquinas de estado são utilizadas para descrever circuitos sequenciais. Diferentemente de um contador que em geral conta eventos, uma máquina de estado costuma ser usada para controlar o evento.

1-19

• Máquinas de estados finitos podem ser representadas por meio de um diagrama de estados (ou diagrama de transição de estados).

• Diversas tabelas de transição de estados são usadas, a mais famosa é a mostrada abaixo. A combinação do estado atual (ex: B) com uma condição (ex: Y) determina o próximo estado (ex: C). Através do uso das tabelas podemos representar uma máquina finita de estados que contenha informações completas sobre as ações

1-20

• Máquinas de Estados UML• A UML tem uma notação para descrever máquinas de estado.

Máquinas de estado UML superam as limitações das FSMs [Finite State Machines] tradicionais, mantendo os seus principais benefícios.

• As máquinas de estados UML introduzem os novos conceitos de estados aninhados hierarquicamente e em regiões ortogonais, enquanto estende a noção de ações.

• Elas suportam ações que dependem tanto do estado do sistema quanto da condição, assim como ações de entrada e saída que estão associadas com os estados em vez de transições.

1-21

1-22

• Máquinas de estado SDL

• A SDL [Specification and Description Language] é um padrão da União Internacional de Telecomunicações e é uma das melhores linguagens para descrever máquinas de estado, pois inclui símbolos gráficos para descrever as ações na transição:– enviar um evento

– receber um evento

– iniciar um temporizador

– cancelar um temporizador

– iniciar uma nova máquina de estado simultânea

– decisão

• SDL incorpora tipos básicos de dados chamado Abstract Data Types, uma linguagem de ação, e uma semântica de execução, a fim de tornar a máquina de estados finita executável.

1-23

1-24

• Existem várias outras maneiras de se representar uma FSM

• Um exemplo é o HDL:

• Em HDL (Hardware Description Language) ou LDH(Linguagem de Descrição de Hardware) é possível criar máquinas de estado simples e de descrição intuitiva. É feito o uso de estados nomeados para os quais não há valores binários definidos. Em VHDL existem as palavras-chave como TYPE por exemplo, que define o tipo enumerado em VHDL. O projetista lista em nomes simbólicos (diferentes das palavras-chave) todos os possíveis valores que um sinal, variável ou porta que é declarado como sendo deste tipo pode assumir. O valor binário é determinado pelo compilador, deixando o trabalho do projetista mais simples.

1-25

• Além de seu uso na modelagem de sistemas reativos aqui apresentados, máquinas de estados finitas são significativos em diversas áreas, incluindo– engenharia elétrica,

– linguística,

– ciência da computação,

– filosofia,

– biologia,

– matemática e lógica.

• Em ciência da computação, máquinas de estados finitas são amplamente utilizados na modelagem do comportamento das aplicatições, design de sistemas digitais de hardware, engenharia de software, compiladores, protocolos de rede, e o estudo da computação e linguagens.

1-26

• Aceitadores e reconhecedores: – produzem uma saída binária, dizendo sim ou não para responder se a

entrada é aceite pela máquina ou não.

– Todos os estados da FSM estão a dizer se quer aceitar ou não quer aceitar.

– No momento em que todas as entradas são processadas, se o estado atual é um estado de aceitação, a entrada é aceite, caso contrário é rejeitada.

– Como regra a entrada são símbolos (caracteres); ações não são usadas.

– O exemplo da figura seguinte mostra uma máquina de estados finita que aceita a palavra "nice". Neste FSM o único estado de aceitação é o número 7

1-27

1-28

• A máquina também pode ser descrita como a definição de uma linguagem, que conteria todas as palavras aceites pela máquina e nenhuma das que são rejeitadas; dizemos então que a linguagem é aceite pela máquina.

• Por definição, linguagens aceitas por FSMs são as linguagens regulares, isto é, uma linguagem é regular se existe alguma FSM que a aceita

1-29