Matematica Computacional - Maquinas de Estados e Automatos

MATEMÁTICA COMPUTACIONAL AULA 4 Prof Luis Gonzaga de Paulo 2 CONVERSA INICIAL Muitos dos conceitos que estudamos em matemática tem aplicação direta e prática não apenas em ambientes complexos e requintados mas também em coisas simples do dia a dia As máquinas e os autômatos que estudaremos nesta aula são um exemplo são frequentemente usadas para a modelagem matemática dos mais diferentes tipos de problemas desde analisadores de linguagem a engines de busca mecanismos de inferência robôs e máquinas dos mais diversos tipos Porém em sua essência tais máquinas são fundamentais para os ambientes de computação pois em síntese o próprio computador é uma dessas máquinas O conhecimento do funcionamento dessas máquinas em nossos estudos tem o propósito de possibilitar o uso intenso dessas ferramentas quer seja para a modelagem e o desenvolvimento de solução para os diversos problemas que se apresentam para os profissionais da tecnologia quer seja para o estudo de questões relativas à computação para a revisão de conceitos e o desenvolvimento tecnológico e científico TEMA 1 MÁQUINA DE ESTADOS As máquinas de estado são uma forma matemática de abstrair processos ou o funcionamento de equipamentos reais sejam eletrônicos ou mecânicos e ainda dos softwares Em outras palavras as máquinas de estado são um modelo matemático de sistemas que possuem entradas e saídas discretas e a capacidade de representar em um certo momento um estado pré estabelecido As máquinas de estado também são chamadas autômatos ou máquinas de estado finito FSM Finite State Machine em inglês O tipo de abstração propiciado por essas máquinas nos permite a modelagem matemática de um vasto número de problemas Apesar de possuir a capacidade de representar múltiplos estados uma FSM só pode apresentarse em um estado por vez denominado estado atual sendo esta é principal característica de uma máquina de estados O estado atual representa a informação relativa às entradas passadas e isso é necessário para que se possa determinar o comportamento do sistema perante as próximas entradas Uma FSM pode ser representada por uma quíntupla Q δ q0 F 3 Q é um conjunto finito de estados é conjunto finito de símbolos chamado de alfabeto da FSM δ é a função de transição q0 é o estado inicial no qual qualquer entrada é processada q0 Q F é um conjunto de estadoestados finais de Q F Q Figura 1 Diagrama de representação de uma máquina de estados A terminologia aplicada às FSM inclui os seguintes termos Alfabeto é um conjunto finito de símbolos Por exemplo a b c d é um conjunto do alfabeto no qual a b c e d são símbolos String é uma sequência finita de símbolos obtidos de Por exemplo a string cabcad é uma string válida do conjunto do alfabeto a b c d Comprimento de uma string é o número de elementos presentes na string denotado por S Por exemplo se S cabcad S 6 Se S 0 então a string é chamada string vazia denotada por λ or ε Fecho de Kleene ou Operador de Kleene é um operador unário ou um conjunto de símbolos ou strings dado um infinito conjunto de todas as possíveis strings de todos os possíveis comprimentos sobre incluindo λ A representação 0 1 2 p é o conjunto de todas as strings possíveis de comprimento p Por exemplo se a b λ a b aa ab ba bb 4 Fecho de Kleene Mais é um conjunto infinito de possíveis strings de todos os possíveis comprimentos sobre excluindo λ A representação é 1 2 3 λ Por exemplo se a b então a b aa ab ba bb Linguagem é um subconjunto de para algum alfabeto que pode ser finito ou infinito Por exemplo se a linguagem L compreende todas as strings possíveis de comprimento 2 sobre a b então L ab aa ba bb A base do funcionamento de uma FSM é justamente isso considerar que um estado armazena informações sobre as etapas anteriores isto é o passado do processo Além disso o estado reflete as mudanças ocorridas desde a entrada neste estado até o momento presente Uma mudança de estado geralmente descrita ou especificada por uma condição que precisa ser atendida ou ocorrer referese à uma transição Uma ação referese à uma atividade a ser realizada para gerar a transição ou mesmo à uma atividade que ocorre em função de uma transição Figura 2 Um semáforo farol ou sinal exemplo de uma FSM 5 Figura 2 Um diagrama de estado de FSM de um elevador Um diagrama de estado é a forma gráfica que utilizamos para representar o funcionamento de uma máquina de estado como mostrado na Figura 3 As tabelas de transição de estado também podem representar as FSM máquinas de estado Uma máquina de estados finita pode ser descrita por uma tabela de transição de estados que contém as informações completas sobre as ações e os estados para cada um dos estados e também todas as transições registradas ou previstas Tabela 1 Estados de uma FSM As máquinas de estado podem ser de dois tipos as do tipo aceitadoras ou reconhecedoras como mostrado na Figura 4 que produzem uma saída binária restrita a sim ou não para informar se a entrada é aceita pela máquina ou não e as do tipos transdutoras como visto na Figura 5 que produzem uma informação na saída baseada em um estímulo ou informação de entrada eou um estado utilizando ações e que geralmente são utilizadas para aplicações de controle Condição Estado A Estado B Estado C 1 2 Estado C 3 Estado Tabela de Transição de Estados 6 Figura 4 FSM do tipo aceitadores Do ponto de vista matemático uma FSM é função da relação de conjuntos prédeterminados e tem a seguinte definição Gersting 2015 Máquina de Estado Finito M E I O fE fO é uma máquina de estado finito se E é um conjunto finito de estados I é um conjunto finito de símbolos de entrada o alfabeto de entrada O é um conjunto finito de símbolos de saída o alfabeto de saída e fE fO são funções onde fE E x I E e fO E O A máquina sempre começa inicializada por um estado inicial fixo e0 Figura 5 FSM do tipo transdutores As figuras apresentadas e os exemplos utilizados até aqui tratam de um tipo de FSM que denominamos AFD Autômato Finito Determinístico ou seja uma estrutura matemática constituída por três tipos de elementos um conjunto de estados um alfabeto com os símbolos reconhecidos como Efeitos Físicos Efeitos Mecânicos Luz Calor Som Posição Força Velocidade Sinal de Saída Sensor 7 entrada e saída e um conjunto de transições Entre os estados destacamos um único estado inicial e um subconjunto composto dos estados finais Um AFD Autômato Finito Determinístico é representado por uma quíntupla Q δ q0 F na qual Q é um conjunto finito de estados é um conjunto finito de símbolos chamado alfabeto δ é a função de transição na qual δ Q Q q0 é o estado inicial a partir do qual qualquer entrada é processada q0 Q F é um conjunto de estadoestados finais de Q F Q Como já vimos um AFD Autômato Finito Determinístico é representado por um dígrafo denominado diagrama de estado Nesse dígrafo os vértices representam os estados as arestas nomeadas com o alfabeto de entrada mostram as transições o estado inicial é definido por uma única aresta vazia e o estado final é indicado por um círculo duplo Por exemplo consideremos um AFD como segue Q a b c 0 1 q0 a F c A função de transição δ é apresentada no quadro a seguir Quadro 1 Função de transição para o AFD Estado atual Próximo estado para uma entrada 0 Próximo estado para uma entrada 1 a a b b c a c b c Podemos representar graficamente esse AFD da seguinte forma 8 Figura 6 Estado do AFD proposto Em um AFD para cada par estado símbolo há uma transição para um único estado o que confere um caráter determinístico ao funcionamento deste autômato Caso eliminemos essa restrição ou seja se para um determinado par estado símbolo for possível haver transições para dois ou mais estados passamos a denominar a FSM como AFN Autômato Finito não Determinístico Ou seja em um AFN é possível haver um conjunto com várias operações possíveis para a mesma palavra ou símbolo de entrada em um estado Os componentes de um AFN são basicamente os mesmos de um AFD porém um AFN contempla as seguintes definições Um AFN pode ter mais que um estado inicial A função de transição apresenta para cada par estado símbolo um conjunto de estados Um AFN Autômato Finito NãoDeterminístico é representado por uma quíntupla Q δ q0 F na qual Q é um conjunto finito de estados é um conjunto finito de símbolos chamado alfabeto δ é a função de transição na qual δ Q 2Q 2 elevado a Q devese ao fato de que a transição de um estado pode para qualquer combinação de Q q0 é o estado inicial a partir do qual qualquer entrada é processada q0 Q F é um conjunto de estadoestados finais de Q F Q Um AFN também pode ser representado por um dígrafo um diagrama de estado da mesma forma que um AFD Para exemplificar vamos considerar um AFN com as seguintes características 9 Q a b c 0 1 q0 a F c A função de transição δ é apresentada no quadro a seguir Quadro 2 Função de transição para o AFD Estado Atual Próximo Estado para uma Entrada 0 Próximo Estado para uma Entrada 1 a ab b b c ac c bc c A representação gráfica desse AF pode ser a seguinte Figura 7 Gráfico do AFN proposto O Quadro 3 apresenta um comparativo entre um AFD e um AFN Quadro 1 Comparativo entre um AFD e um AFN AFD AFN A transição de um estado ocorre para um único estado próximo particular para cada símbolo de entrada Por isso é chamado determinístico A transição de um estado pode ocorrer para vários estados seguintes para cada símbolo de entrada Por isso é chamado de não determinístico Transições de strings vazias não existem Transições de strings vazias podem ocorrer O retrocesso é permitido O retrocesso nem sempre é possível Requer mais espaço Requer menos espaço Uma string é aceita se passar para um estado final Uma string é aceita se pelo menos uma das transições possíveis terminar em um estado final 10 Figura 8 Arquitetura de um AFD Um AFD pode ser representado pela arquitetura mostrada na Figura 9 uma máquina que opera com uma leitura sequencial em uma fita e em apenas uma direção para a direita Esta fita contém os símbolos distribuídos em células sendo um único símbolo em cada célula A máquina também tem um registrador para armazenar o estado atual um conjunto de instruções a função de transição do AFD e uma unidade de controle É possível também que se possa fazer a leitura bidirecional da fita permitindo que a transição possa avançar ou retroceder na leitura dos símbolos Nesse caso para evitar que a leitura avança para além do final ou retroceda para antes do começo é necessário que existam mais duas células com símbolos especiais e que na prática limitam as transições uma transição de avanço ou leitura da fita para a direita para a condição e uma transição de retrocesso ou leitura da fita para a esquerda para a condição A Figura 9 apresenta a arquitetura dessa variação de AFD Figura 9 AFD com fita bidirecional controle ᵟ a1 a2 ai an e fita de somente leitura unidirecional registrador com estado atual controle ᵟ e fita de somente leitura bidirecional registrador com estado atual a1 a2 ai an 11 Na aula prática sobre FSM são apresentados problemas para os quais a solução emprega os dois tipos de autômatos e a solução proposta para eles assim como exercícios resolvidos que reforçam os conceitos apresentados Além de seu uso na matemática na engenharia e nas tecnologias em geral as Máquinas de Estado são largamente empregadas na computação quer seja na modelagem do funcionamento de softwares sistema ou aplicativos quer seja para projetar sistemas digitais compostos de hardware e software na Engenharia de Software nos projetos de compiladores e de protocolos de rede e também no estudo da computação e das linguagens TEMA 2 AUTÔMATOS DE PILHA Apesar da sua extensa aplicação as máquinas de estado finito FSM ou autômatos finitos não atendem à totalidade dos problemas É o caso por exemplo de aplicações para as quais é necessário usar expressões aritméticas Nesses casos falta aos autômatos uma memória que permita registrar todos os valores ou as ocorrências dos símbolos Para atender à essa necessidade são utilizados os AP Autômatos de Pilha pushdown automata em inglês Figura 10 A arquitetura de um AP Estes são mecanismos de grande importância para a computação como por exemplo nos compiladores de linguagem de programação na etapa de análise sintática de um código Ainda diferentemente dos autômatos finitos um autômato de pilha não determinístico tem uma abrangência muito superior a dos controle ᵟ e fita de somente leitura bidirecional registrador com estado atual a1 a2 ai an b1 b2 bn topo da pilha 12 AP determinísticos Um autômato de pilha é uma máquina de estados bastante semelhante à um AFD porém com o adicional de uma pilha A Figura 10 apresenta a arquitetura de um AP A pilha tal como uma fita compõese de células que são capazes de receber apenas um símbolo por vez A leitura porém é feita apenas na célula do topo da pilha No início do processo o registrador contém o estado inicial do AP A fita então recebe a palavra de entrada da sua primeira célula pois o cabeçote de leitura está posicionado na primeira célula da fita Neste momento a pilha está vazia À medida em que a leitura da fita prossegue e as transições resultam em um uso da pilha um símbolo de fim de pilha F é inserido na pilha de modo a identificar esse status novamente quando a pilha for lida A principal diferença entre um APD Autômato de Pilha Determinístico e um APN Autômato de Pilha NãoDeterminístico reside no fato de que o APN pode contemplar transições compatíveis entre si TEMA 3 MÁQUINA DE MEALY Uma máquina de Mealy é uma FSM cuja saída depende do estado atual bem como da entrada Pode ser descrita por uma sêxtupla Q O δ X q0 em que Q conjunto finito de estados conjunto finito de símbolos denominado alfabeto de entrada O conjunto finito de símbolos denominado alfabeto de saída δ função de entrada de transição em que δ Q Q X função de saída da transição em que X Q O q0 estado inicial a partir do qual qualquer entrada é processada q0 Q Os estados de uma máquina de Mealy são mostrados no quadro a seguir 13 Quadro 4 Estados de uma máquina de Mealy Estado atual Próximo estado entrada 0 entrada 1 Estado Saída Estado Saída a b x1 c x1 b b x2 d x3 c d x3 c x1 d d x3 d x2 O diagrama de estados dessa máquina é o seguinte Figura 11 Diagrama de estados de uma máquina de Mealy TEMA 4 MÁQUINA DE MOORE Uma máquina de Moore é uma FSM cujas saídas dependem apenas do estado atual Pode ser descrita por uma sêxtupla Q O δ X q0 em que Q conjunto finito de estados conjunto finito de símbolos denominado alfabeto de entrada O conjunto finito de símbolos denominado alfabeto de saída δ função de entrada de transição em que δ Q Q X função de saída da transição em que X Q O q0 estado inicial a partir do qual qualquer entrada é processada q0 Q Os estados de uma máquina de Moore são mostrados no quadro a seguir 14 Quadro 5 Estados de uma máquina de Moore Estado atual Próximo estado Saída Entrada 0 Entrada 1 a b c x2 b b d x1 c c d x2 d d d x3 O diagrama de estados de uma máquina de Moore é o seguinte Figura 12 Diagrama de estados de uma máquina de Moore TEMA 5 MÁQUINA DE TURING A Máquina de Turing é um dispositivo inventado em 1936 por Alan Turing matemático inglês que aceita as linguagens conjunto recursivamente enumerável geradas por gramáticas tipo 0 Uma máquina de Turing é um modelo matemático que consiste em uma fita de comprimento infinito dividida em células pelas quais a entrada é dada e de uma cabeça de leitura que lê a fita de entrada Um registrador de estado armazena o estado da máquina de Turing Depois de ler um símbolo de entrada este é substituído por outro símbolo o estado interno da máquina é alterado e a cabeça de leitura se move uma célula para a direita ou para a esquerda Se a máquina atingir o estado final a string de entrada será aceita caso contrário será rejeitada Uma máquina de Turing pode ser formalmente descrita com uma sétupla Q X δ q0 B F em que Q é um conjunto finito de estados X é o alfabeto da fita 15 é o alfabeto de entrada δ é a função de transição δ Q X Q X deslocamento à esquerda deslocamento à direita q0 é o estado inicial B é o símbolo de Espaço em Branco F é o conjunto de estados finais Uma comparação da máquina de Turing com outros modelos de autômatos é bastante útil como mostrando no quadro a seguir Quadro 2 Máquina de Turing x outros autômatos Tipo de Máquina Estrutura de Pilha de Dados Determinística Autômatos Finitos NA Sim Autômato de Pilha Último a entrar primeiro a sair LIFO Não Máquina de Turing Fita infinita Sim Vamos à um exemplo da máquina de Turing M Q X δ q0 B F com Q q0 q1 q2 qf X a b 1 q0 q0 B espaço em branco F qf A transição de estados δ é dada por Simbolo do Alfabeto da Fita Estado atual q0 Estado atual q1 Estado atual q2 a 1Rq1 1Lq0 1Lqf b 1Lq2 1Rq1 1Rqf Em uma máquina de Turing a complexidade do tempo referese à medida do número de vezes que a fita se move quando a máquina é inicializada para alguns símbolos de entrada e a complexidade do espaço é o número de células da fita gravadas A complexidade do tempo pode ser representada por T n O 16 n log n A complexidade do espaço da máquina de Turing pode ser representada por S n O n Quanto à linguagem uma máquina de Turing aceita uma linguagem se entrar em um estado final para qualquer string de entrada escrita Uma linguagem é dita recursivamente enumerável gerada pela gramática Tipo 0 se for aceita por uma máquina de Turing Uma MT decide por uma linguagem se o aceita e entra em um estado de rejeição para qualquer entrada que não esteja nessa linguagem Uma linguagem é recursiva se for decidida por uma máquina de Turing Podem haver alguns casos em que uma máquina de Turing não para Então essa máquina de Turing aceita a linguagem mas não a decide Vamos ver questões elementares da máquina de Turing com o auxílio dos dois exemplos a seguir Primeiramente vamos tratar de uma máquina de Turing que possa reconhecer todas as entradas com uma string na qual o número de letras a seja par Essa máquina de Turing M pode ser construída com os seguintes passos Seja q1 o estado inicial Se M está em q1 ao ler a entra no estado q2 e escreve B espaço em branco Se M está em q2 ao ler a entra no estado q1 e escreve B espaço em branco Dos movimentos apresentados nós podemos verificar que M entra no estado q1 se ler um número par de as e entra no estado q2 se ler um número ímpar de as Portanto q2 é o único estado de aceitação Deste modo M q1 q2 1 1 B δ q1 B q2 Em que δ é dado por Símbolo do alfabeto da fita Estado atual q1 Estado atual q2 a BRq2 BRq1 No segundo exemplo projetamos uma máquina de Turing que lê uma string representando um número binário e apaga todos os 0s iniciais da string No entanto se a string for composta apenas por 0s ela manterá um 0 Vamos supor que a string de entrada seja delimitada por um espaço em branco B em 17 cada extremidade da cadeia Então nossa máquina de Turing M pode ser construída pelos seguintes movimentos Seja q0 o estado inicial Se M está em q0 ao ler 0 move à direita entra no estado q1 e apaga o 0 Ao ler 1 entra no estado q2 e move à direita Se M está em q1ao ler 0 move à direita 0 ou seja troca os 0s por Bs Ao atingir o 1 mais à esquerda entra em q2 e move à direita Se encontra B ou seja a string é composta apenas de 0s move à esquerda e entra no estado q3 Se M está em q2 lendo tanto 0 ou 1 move à direita Se encontrar B move à esquerda e entra em q4 Isto valida que a string contém apenas 0s e 1s Se M está em q3 troca B por 0 move à esquerda e atinge o estado final qf Se M está em q4 ao ler tanto 0 ou 1 move à esquerda Ao alcançar o início da string ou seja ler B atinge o estado final qf Portanto M q0 q1 q2 q3 q4 qf 01 B 1 B δ q0 B qf Em que δ é dado por Símbolo do alfabeto da fita Estado atual q0 Estado atual q1 Estado atual q2 Estado atual q3 Estado atual q4 0 BRq1 BRq1 ORq2 OLq4 1 1Rq2 1Rq2 1Rq2 1Lq4 B BRq1 BLq3 BLq4 OLqf BRqf FINALIZANDO As máquinas de estado fazem parte de um poderoso arsenal para o desenvolvimento de soluções com base na formulação matemática do problema e suas possíveis soluções Por serem processos empregados desde a origem da computação com um forte embasamento matemático podem causar uma primeira impressão de complexidade Entretanto o uso constante e a sua equiparação aos componentes essenciais dos computadores os circuitos 18 digitais de lógica e aritmética binária fornece um precioso conhecimento para o estudo de problemas e o projeto de soluções computacionais com a vantagem de poderse utilizar a modelagem matemática em sua plenitude valendose principalmente das provas dos modelos formais o que em termos de otimização do uso de tempo e de recursos escassos pode ser a diferença entre o sucesso e o fracasso do projeto 19 REFERÊNCIAS BONAFINI F C Matemática e estatística São Paulo Pearson Education do Brasil 2014 GERSTING J L Fundamentos matemáticos para a ciência da computação um tratamento moderno de matemática discreta Rio de Janeiro LTC 2015 MACEDO L R D CASTANHEIRA N P ROCHA A Tópicos de matemática aplicada Curitiba InterSaberes 2013 STEIN C DRYSDALE R L BOGART K Matemática discreta para ciência da computação São Paulo Pearson Education do Brasil 2013 VIEIRA M J Introdução aos Fundamentos da computação linguagens e máquinas São Paulo Pioneira Thomson Learning 2005 WALPOLE R E et al Probabilidade estatística para engenharia e ciências São Paulo Pearson Prentice Hall 2009