Agenda de Aula 2: Autômatos Finitos e Máquinas de Estados Finitos

Agenda Automáticos finitos ou máquinas de estados finitos são modelos que representam um conjunto de possíveis estados e as relações de transição entre estes estados Teoria da Computação Aula 2 Automáticos finitos Prof Alex Torquato Souza Carneiro alexcarneirofaculdadeimpactacombr Autômatos finitos ou máquinas de estados finitos são modelos que representam um conjunto de possíveis estados e as relações de transição entre estes estados Podemos fazer um modelo da vida como um autômato finito Infância Adolescência Adulto Velhice Infância Adolescência Adulto Velhice Infância Adolescência Adulto Velhice De modo geral os estados que um autômato finito possui são estado inicial identificado por uma seta estados intermediários e um estado final identificado por um círculo duplo Estes estados são conectados pelas ações ou condições que levam de um estado a outro De modo geral os estados que um autômato finito possui são estado inicial identificado por uma seta estados intermediários e um estado final identificado por um círculo duplo Estes estados são conectados pelas ações ou condições que levam de um estado a outro Modelo para uma porta automática Fechada Abert a Automáticos finitos Automáticos finitos Automáticos finitos No exemplo da porta os estados são aberta fechada o estado inicial da porta é fechada o estado final para a porta é fechada As transições entre os estados se dá pela presença de alguém próximo à porta ou quando não há ninguém próximo à porta Esta representação também é denominada diagrama de estados Esta representação também é denominada diagrama de estados O estado final de um autômato é denominado estado de aceitação Alguns estados podem ser retroalimentados Alguns estados podem ser retroalimentados Funcionamento Começo Autômatos finitos Funcionamento Começo fechada Alguém se aproxima Autômatos finitos Funcionamento Começo fechada Alguém se aproxima aberta Ninguém por perto fechada Alguém se aproxima Fechada Aberta Autômatos finitos Funcionamento Começo fechada Alguém se aproxima aberta Ninguém por perto Fechada Aberta Fechada Aberta Fechada Aberta Usaremos os autômatos com o objetivo de identificar padrões em strings Usaremos os autômatos com o objetivo de identificar padrões em strings Por exemplo se desejamos verificar se uma string s formada pelos caracteres a b c termina em a Usaremos os autômatos com o objetivo de identificar padrões em strings Por exemplo se desejamos verificar se uma string s formada pelos caracteres a b c termina em a Autômatos finitos Usaremos os autômatos com o objetivo de identificar padrões em strings Por exemplo se desejamos verificar se uma string s formada pelos caracteres a b c termina em a s abca Autômatos finitos Usaremos os autômatos com o objetivo de identificar padrões em strings Por exemplo se desejamos verificar se uma string s formada pelos caracteres a b c termina em a s abca ok s aaab Autômatos finitos Usaremos os autômatos com o objetivo de identificar padrões em strings Por exemplo se desejamos verificar se uma string s formada pelos caracteres a b c termina em a s abca ok s aaab não Autômatos finitos Usaremos os autômatos com o objetivo de identificar padrões em strings Por exemplo se desejamos verificar se uma string s formada pelos caracteres a b c termina em a 𝛴 δ 𝛴 δ 𝛴 δ 𝛴 δ 𝛴 δ 𝛴 δ 𝛴 δ 𝛴 δ 𝛴 𝛴 δ 𝛴 δ 𝛴 𝛴 δ 𝛴 δ 𝛴 O alfabeto Σ corresponde aos possíveis estímulos fornecidos ao automático O alfabeto Σ corresponde aos possíveis estímulos fornecidos ao autômato Em problemas computacionais elementares é comum vermos Σ 01 O alfabeto Σ corresponde aos possíveis estímulos fornecidos ao autômato Em problemas computacionais elementares é comum vermos Σ 01 𝛴 𝛴 par ímpar 0 0 1 0 0 1 0 0 O alfabeto Σ corresponde aos possíveis estímulos fornecidos ao autômato Em problemas computacionais elementares é comum vermos Σ 01 A função de transição δ corresponde às condições de mudança entre os estados de acordo com os estímulos A função de transição δ corresponde às condições de mudança entre os estados de acordo com os estímulos Como as quantidades de estados e de estímulos são finitas podemos representar δ como um mapeamento entre cada combinação estadoestímulo para um dado estado δ 𝛴 𝛴 q0 par ímpar δ 𝛴 𝛴 𝛴 q0 par ímpar δ 𝛴 𝛴 𝛴 q0 par ímpar δ δ 𝛴 𝛴 𝛴 q0 par ímpar δ δ Uma função qualquer corresponde à uma relação de um elemento de um conjunto denominado domínio para um elemento de um outro conjunto denominado imagem Revisão sobre funções Uma função qualquer corresponde à uma relação de um elemento de um conjunto denominado domínio para um elemento de um outro conjunto denominado imagem Exemplo fx x² Revisão sobre funções Uma função qualquer corresponde à uma relação de um elemento de um conjunto denominado domínio para um elemento de um outro conjunto denominado imagem Exemplo fx x² Domínio ℝ números reais Imagem ℝ números reais ℝ ℝ 5 2 1 0 1 3 5 0 1 4 9 16 25 ℝ ℝ 5 2 1 0 1 3 5 0 1 4 9 16 25 ℝ ℝ 5 2 1 0 1 3 5 0 1 4 9 16 25 ℝ ℝ 5 2 1 0 1 3 5 0 1 4 9 16 25 ℝ ℝ 5 2 1 0 1 3 5 0 1 4 9 16 25 ℝ ℝ 5 2 1 0 1 3 5 0 1 4 9 16 25 ℝ ℝ 5 2 1 0 1 3 5 0 1 4 9 16 25 δ 𝛴 𝛴 δ q0 par ímpar δ 𝛴 𝛴 δ q0 par ímpar δ 𝛴 𝛴 δ q0 par ímpar δ 𝛴 𝛴 δ δ q0 par ímpar δ 𝛴 𝛴 δ δ δ q0 par ímpar δ 𝛴 𝛴 δ δ δ δ q0 par ímpar δ 𝛴 𝛴 δ δ q0 par ímpar δ 𝛴 𝛴 δ δ δ q0 par ímpar δ 𝛴 𝛴 δ δ δ δ q0 par ímpar δ δ δ δ δ δ q0 par ímpar Autômatos finitos determinísticos Definimos um autômato com autômato finito determinístico AFD quando a função δ apresenta todas as combinações de estados e estímulos em seu domínio Autômatos finitos determinísticos Definimos um autômato com autômato finito determinístico AFD quando a função δ apresenta todas as combinações de estados e estímulos em seu domínio Autômatos finitos determinísticos Definimos um autômato com autômato finito determinístico AFD quando a função δ apresenta todas as combinações de estados e estímulos em seu domínio O que acontece com o autômato se este estiver em q₁ e receber 0 O que acontece com o autômato se este estiver em q₂ e receber 1 Autômatos finitos determinísticos Definimos um autômato com autômato finito determinístico AFD quando a função δ apresenta todas as combinações de estados e estímulos em seu domínio Automáto finito não determinístico O que acontece com o autômato se este estiver em q₁ e receber 0 O que acontece com o autômato se este estiver em q₂ e receber 1 Autômatos finitos determinísticos Definimos um autômato com autômato finito determinístico AFD quando a função δ apresenta todas as combinações de estados e estímulos em seu domínio Autômatos finitos determinísticos Definimos um autômato com autômato finito determinístico AFD quando a função δ apresenta todas as combinações de estados e estímulos em seu domínio Autômato finito determinístico Autômatos finitos Uso de autômatos linguagens Automátos finitos Considerando o alfabeto Σ definimos uma linguagem como todas as sequências de strings que podemos formar com este alfabeto As strings são sequências de elementos de um alfabeto Definimos então o conceito de linguagem regular Segue o conceito de linguagem regular Uma linguagem é chamada regular se existir um autômato finito capaz de reconhecêla Exemplo criar um autômato que identifique gerúndios qndo q qn qn d qndo 𝛴 Exemplo criar um autômato que identifique gerúndios Gerúndios são palavras que terminam em NDO andando estudando falando dormindo lendo enchendo qndo q qn qn d qndo 𝛴 qndo q qn qn d qndo 𝛴 qndo q qn qn d qndo 𝛴 qndo q qn qn d qndo 𝛴 qndo q qn qn d qndo 𝛴 Autômatos finitos Exemplo criar um autômato que identifique verbos de 1ª conjugação no infinitivo final ar Autômatos finitos Exemplo criar um autômato que identifique palavras com o prefixo inter