LFA04 - Autômato Finito DETERMINÍSTICO (Funcionamento)

a bomba só meu nome é Zé Rui e na aula de hoje de nós vamos dar sequência no capítulo 2 que nós estamos estudando as linguagens regulares e vamos estudar o que que é um sistema de Estados finitos e o primeiro formalismo que é o autômato beleza vamos para a nossa aula então bom [Música] então o que que venha ser um sistema de estados finitos pessoal então ele é um modelo matemático que tem um conjunto de entradas e saídas e essa saída são discretas ou seja ele é composto por uma entrada por exemplo a AB

e os estados que ele pode pular um por um de acordo com cada letra que ele lê um ponto extremamente importante o sistema de estados finitos não possuem memória então ele não sabe aonde ele passou por isso nós vamos ter que bolar uma memória quase que igual naquele filme lá do João e Maria que ia Deixando as migalhas para trás né para saber onde é que passou porque ele mesmo não possui memória e sem ficar muito claro costuma até pedir se na prova para vocês como o próprio e nele Tem que ter um número finito

e pré-definido de estados esse número de estados não muda ao longo do seu funcionamento e a máquina parece Óbvio mas a gente tem que registrar isso né Essa máquina de estados ela pode estar somente em um estado por vez um exemplo aí de máquina de estado que todo mundo lida com ela é o tal do elevador né o elevador aqui ó seria isso nós temos então três estados ou ele está parado ou ele está descendo o ele está subindo então se você deu um comando para ele uma entrada de dados que é o sensor levantado

ele tá descendo então perceba que você tem sempre que analisar duas coisas em qual estado que você tá E qual ação que você fez então perceba que se você está nesse estado aqui significa elevador está descendo o pensando aqueles elevador de obra tá que você levanta e abaixa Tá então vamos lá Se Você levantou e ele tá descendo significa que ele vai começa a parar porque talvez você vai querer que ele suba beleza mas antes de subir ele não pode no sistema de estado ele não pula de um estado lá para o outro de cara

não se ele tá descendo ele para e depois ele sobe com quarto comigo então você tá descendo o sensor tá levantado ele muda de estado para parado Se Você levantou o sensor de novo continua com ele levantado e ele tava parado quer dizer que agora está subindo se ele tá subindo ele abaixou significa que ele parou se ele tá parado e se abaixou de novo significa está descendo Então olha só é bem legal essa história porque porque você tem que sempre lembrar que você tá na lizando dois casos sempre o estado e o comando e

a entrada que te foi dada isso caracteriza como um sistema de estados finitos então dito isso nós podemos então partir para o ensino um autômato porque um autômato ele é uma máquina de Estado então nós temos que saber esse conhecimento acabei de colocar para vocês vamos lá então é um sistema de estados finitos ele pode ser de 3 tipos ou determinístico não-determinístico ou não determinístico com movimentos vazios o apenas que nós chamamos de como movimentos vazios tá nós vamos ver que todos eles são equivalentes o que que vem a ser um autômato determine Como o

próprio nome diz ele você sabe aonde ele está dado uma determinada entrada então por exemplo a partir de um determinado estado e de um símbolo lido ou seja de uma entrada ele pode estar apenas em um único lugar é como se fosse assim né se o cara vira para você falar vou ver se adivinho onde é que eu tô eu tô vendo o mar e tô embaixo do Cristo Redentor E você tá no Rio de Janeiro ou seja determinista não tem não tem dúvida entender o que que determinismo de acordo com os dois pontos que

você tem que analisar Ele só pode estar em um único lugar enquanto que eu não determinístico como qualquer outra coisa não determinista Você não tem como determinar com sem por cento de certeza aonde ele vai estar por quê Porque eu não determinismo diz o seguinte que a partir de um determinado estado e um símbolo lido ele pode assumir um conjunto de estados Pode ser que ele esteja em outro lugar beleza e o com movimentos vazios é a partir de um determinado estados e sem nenhuma entrada isso aqui é E é abstração em pessoa né você

vai mudar de estado sem ter consumido em uma aleta primeiro deles nós vamos ver é esse determinístico aí vamos lá então o nosso if the autômato finito determinístico então é composto por uma fita que é onde vai ter a nossa entrada na unidade de controle que é onde vai estar buscando o cada uma dessas entradas e lendo e a função programa ou função de transição que vai nos falar ó Eu li um lá então você vai para lá eu lhe um beijo então você vai para cá essa função de transição que vai nos dizer qual

vai ser o movimento dentro do nosso grafo Então a nossa fita é o nosso dispositivo de entrada contém as informações a unidade de controle reflete o estado corrente da máquina ou se precisar saber onde que eu tô é a unidade controle que vai te falar possui uma unidade de leitura ou seja a cabeça da fita é uma cabeça igual como se fosse antigamente aquelas vitrolas né que você colocava assim escutava som acessa uma célula da fita por vez é muito comum vocês estão fazendo exercício que é consumir duas três letrinhas ao mesmo tempo não não

pode está errado tá movimenta-se exclusivamente para a direita Então você começa Leno as suas letrinhas ela vai ler no sempre da esquerda para direita Ok Atenção para isso porque por exemplo lá na máquina de turing Isso muda isso pode ir para lá pode vir para cá pode vir para cá de novo tá mas aqui não autômato determinismo ele vai somente da esquerda para direita e por fim a função programa O transição é como se fosse o cérebro do seu autômato é ela que norteia para onde que o movimento vai acontecer vamos ver o funcionamento então

aqui então nós temos um exemplo de fita né então tem uma fita a entrada a b c b a é uma palavra de um alfabeto de uma linguagem e aí vai vir a unidade de controle verificando cada uma dessas letrinhas e verificando lá nas nossas regras se ela tá ok ou não está ok dentro dessa linguagem e por fim quem nos fala isso é a função de transmissão ou função programa Então a partir do Estado corrente e do símbolo lido ela te fala para onde que você vai então um exemplo seria esse aqui ó Sigma

que é um B = 4 não entende nada né então beleza então vamos entender bem isso aqui ó a leitura dessa linha é se o estado atual é o que um e o símbolo lido foi B vá para o estado que é quatro Então esse aqui a função de transição se eu estou no estado que um e eu li a letrinha B aí quer dizer que eu vou ter que mudar de estado para o estado do que quatro simplesmente assim tá claro pessoal então vamos lá como é que ele é essa daqui ó se eu

estou no estado P ele a letra A eu vou mudar para o estado que beleza é simplesmente isso agora visualmente é a mesma coisa isso aqui é a mesma coisa que essa imagem aqui ó Então olha só se eu estou no estado P estados são as bolinhas e transição são as setinhas Então vamos lá se eu estou no estado P aqui ó no estado P lhe a letra A Quer dizer então que eu vou mudar para o estado do que simplesmente isso tá então estado anterior símbolo lido novo Estado então aqui está o estado anterior

o símbolo lido e aqui o novo estado tão vendo pessoal como que é simples isso aqui é muito tranquilo mas como é novo você tem que exercitar não tem outro caminho então vamos é um avançar um pouco mais e colocar aqui agora a definição matemática de IOF de do autômato finito determinístico ele é uma tupla de cinco conjuntos agora você vai conseguir entender tudo aquilo que nós o melhor botar em prática tudo aquilo que nós conversamos na aula de definição dos vocabulários né então Ó o nosso autômato é definido pela letra M E aí nós

temos então no alfabeto um conjunto de estados as regras de produção o estado Inicial que é onde ele começa e o conjunto de estados finais nós vamos ver cada coisa que agora o m deitado é o alfabeto o que o conjunto de estados o Sigma aqui a Delta né na verdade a Delta é uma função de transição que segue a seguinte cara que cartesiano com alfabeto Me leva para um que aí você pode falar porque trem esquisito não não é esquisito você não entendeu esse aqui ó o link ep pena é um elemento do conjunto

de estados possíveis que então então eu tô no estado lhe uma letra do alfabeto por exemplo a e vou para um outro estado então percebam que muitas vezes as definições matemáticas gente assusta com ela bobagem mesmo porque se você lê com calma você consegue entender o que está sendo dito ali e esse formalismo torna as coisas muito mais amplas e muito menos ambíguas tá então alguém pode ou não porque o cara escreveu desse jeito porque assim tira ambiguidade e faz com que todo mundo entenda da forma correta que zera o nosso estado Inicial e é

fiel conjunto dentro dos Estados possíveis que vai ser onde ele vai terminar ou seja o estado final por convenção na hora de desenhar o estado Inicial gente põe uma setinha nele só um triângulo Zinho assim cá PSOL tanto faz e os está é um a gente coloca linha dupla ou uma linha mais grossa só para diferenciar aí a função de transmissão ela pode ser escrita assim ou por meio de uma tabela né só tô no estado pelo a mesma coisa ó P chegou a letrinha ou prestado o que estou em pé ele a letra A

vou para que tá a mesma forma de escrever isso é por meio de uma tabela que nós chamamos de tabela de transição e vocês vão ver que na hora de implementar esse dentro do computador a melhor forma de se fazer é usando uma tabelinha uma matriz beleza falando falando falando que agora nós vamos para prática vamos ver esse aqui funcionando que é o nosso objetivo maior dessa aula então um exemplo é o exercício é Construa um autômato finito determinístico que aceite qualquer palavra no alfabeto AB então Vamos por partes ele quer que faz então autômato

que aceite qualquer para o quê Qual que é o alfabeto AB então alguma palavra vai ter ser do tipo AABB cê não não vai ter cê hora nenhuma porque o meu alfabeto é só a e b beleza e essa minha esse meu tomado né ele vai possui como subir palavra ah ah o bebê Aí eu te pergunto por exemplo aqui até abrir um editor de texto aqui a palavra a AB AB AB vai se aceita por essa linguagem não não vai porque tá dizendo aqui ó que possua como subir palavra ah ah o bebê por

exemplo Então essa daqui vai ser aceita AB AB a vai ser aceita vai porque tem dentro dela ah ah então essa linguagem ou seja esse autômato só vai aceitar palavras que possuam ah ah o bebê dentro dela essas duas aqui vão ser aceitas entender então não é porque em todas as possibilidades de fazer palavra com a e b que essa linguagem tem que aceitar não então esse autônomo que só vai aceitar palavras que possuam ah ah o bebê então por exemplo essa palavra aqui ó a bebê será aceita porque ela tem como sua palavra beber

e atende esse pedido aqui ó então Ó a mesma coisa de escrever isso aqui em português é escrever da forma formal que então é like é uma linguagem tal que w são as palavras DL tal que w possui ah ah o bebê como subir palavra hoje eu formado a 12 e 13 anos nesse Quanto tempo mais é Prefiro muito mais ler uma definição dessa do que essa é a medida que você for avançando também isso aqui tem muito menos a ambiguidade do que isso aqui tá certo agora vou fazer uma mágica que colocar para você

o autômato pronto eu quero tá funcionando depois nós vamos aprender a construir ele aí é bem simples também mas vamos entender o seu funcionamento E aí a gente vai construir Então tá aí ó esse é o autômato que vai reconhecer cada uma dessas palavras aqui ó acredite se quiser colocar aqui ó então por exemplo cada uma dessas palavras aqui o senhor jogar aqui nessa Engenhoca aqui ele vai me falar no final foi aceito foi rejeitado foi aceita foi rejeitado entendeu É isso que nós vamos fazer aqui agora então vamos lá então aqui tá definição matemática

do autômato que é 1 m que têm um alfabeto AB que tem quais estados pessoal Qual é o conjunto de estados dele dá uma olhadinha aqui ó o estado quiseram estado que um estado que dois estado que é os estados são as bolinhas e as transições são as setinhas beleza Quem são os meus E aí são as minhas transições eles estão aqui na minha tabela de transição a escrita aqui é a mesma coisa que tá desenhado aqui ó ó que é zero chegou a tá mandando eu ir para onde Para que dá uma olhadinha na

tabela se tem esse aqui ó que 0 chegam lá vai para que um então com isso aqui na mão você consegue construir e com isso aqui na mão você consegue construir esse desenho concorda comigo vamos ver se tá tudo certinho fazer mais um aqui ó que é dois chegam lá mas para que um então ó tô aqui em que é dois chegou a letrinha a ele me manda aí para que um tosse isso aqui tá condizente com a minha tabela de transição tá tudo certo então as minhas transições tá definidas aqui nessa tabela o estado

Inicial é o que zera o que tem a setinha em cima dele e os estados finais os estados que podem ser mais de um é o chefe tão por isso a gente coloca entre Chaves e você pode ter mais de um estado final ele tá marcado aqui ó com uma linha um pouco mais grossa beleza pessoal então aqui matematicamente está definido o seu autômato eu poderia tampar esse desenho aqui consequentemente você consegue se virar com essa tabelinha aqui mas vou deixar os dois porque nós estamos na nossa primeira ao Então vamos lá vamos ver se

funcionamento em prática nós vamos analisar então a seguinte entrada a bebê a se ela é aceita pela linguagem eu te pergunto ela é vai ser aceita vai Não vai a gente já sabe de ante-mão que se ela tem bebê dentro dela ela vai ser aceita Então vamos lá como é que você que funciona eu tô marcando aqui de vermelhinho e tô colocando um triângulo aqui ó eu mostrar em qual letra da fita que eu estou lendo e aí eu coloco aqui também o estado para mim não perder Qual estado que eu tô Então vou estar

olhando tanto aqui Ah tá é que eu tô escrevendo para você para depois na hora de estudar Você não se perder só estou no estado que zero e leu a letrinha a para onde que eu vou ou eu pergunto para minha tabela ou eu simplesmente olho no desenho estou em que 0 chegou a mandar eu ir para que um tá aqui ó para o estado que então você coloca ele aqui e aqui você já consumiu se a letrinha E você já consumiu ela arreda para frente beleza em qual estado que você tá agora que você

saiu daqui pulou para cá tranquilíssimo né Então vão adiante tô no estado que é um você pode olhar aqui também tô no estado que um chegou a letra B ele manda eu vim para onde se fosse ar eu viria para cá mas chegou aqui a letrinha B que ele manda eu ir para o estado que é dois estão a mesma coisa estou no estado que é um leu B para onde que vai você vai para o estado que é dois woofers é mais fácil mais vamos lá estou agora no estado do que é dois e

lê ele a letra B ele manda eu ir para onde para um estado que F é o que eu vou fazer estou em que dois se eu li a letra B que tá aqui ó é a próxima ser consumida eu vou para quê efe ao Pai a cheguei no que fqf estado final acabou não não acabou ainda porque porque só pode parar quando você está no estado final e acabou de ler a sua fita tchau é o campeão tem Será que acabou não não acabou só aceita quando tá no estado final tá então vamos continuar

se eu tô no que é Pilão a ele vai para onde ele fica no estado que f de novo aí beleza ele vai pular para fora da fita acabou de ler a fita Será que agora eu posso parar agora sim eu posso parar por quê Porque eu estou no estado final e além de consumir a fita Qual é a resposta esta palavra ela é aceita pela linguagem l então vamos no outro exemplo se eu tivesse terminado de ler a fita e tivesse morrido parado aqui no Q2 a palavra que eu teria lido seria aceita não

por quê que é dois não estado final entender então essa Engenhoca que ela funciona perfeitamente ela vai te falar com garantia sem por cento de certeza que a entrada pertence a linguagem se ele morreu terminou no estado final e se ele consumiu toda a sua fita se ele não conseguiu consumir sua fita inteira Essa palavra não foi aceita se ele morreu parou em algum outro estado que não seja quê efe também não foi aceita tá claro isso pessoal era isso que eu tinha para mostrar para vocês então agora eu vou registrar isso que eu acabei

de falar aqui para vocês a condição é de um autômato é se a palavra foi aceita ou rejeitada se ela foi aceita e significa que ela processou o último símbolo e parou no estado final se essas duas coisas acontecer você pode bater o carimbo e falar essa palavra foi aceita se um desses dois não foi atendido você vai falar aqui não foi aceita ou seja após processar o último símbolo as um estado não final não é aceita ou a função de transição está indefinida para algum parâmetro seja ela morreu aqui no meio aqui ó como

por exemplo Ó você tentou entrar com a palavra ABC então o ar eu vim para cá o Bê eu vim para cá aí chegou aqui chegou a letrinhas e eu não tenho saída nenhuma aqui ó como se fosse uma Encruzilhada né Eu só posso sair para rua ou para Rua B tá mandando eu ir para Rua C E aí ruas e pé paro estragou não foi aceita também beleza agora é com você Oi e agora como é que faz um autômato a boa notícia é não tem regra não tem fórmula pronta ou seja você vai

tentar fazer por tentativa e erro na verdade não é um tiro no escuro também é uma coisa que tem uma determinada lógica e aí eu que eu vou ensinar para vocês e com a prática vocês pegam é igual andar de bicicleta não adianta a gente ficar só falando ó você vai pegar o pedal vai tentar manter o prumo tal tal tal momento linear da bicicleta eu posso te ensinar física toda adianta você não chegar ali no tentar esfolar o joelho no chão as 15 vezes não tem jeito não vai aprender andar de bicicleta beleza pessoal

agora não podemos esquecer que sempre a gente quer dar uma roubadinha né ele não tem memória ele não tem memória é uma máquina de Estado então a dica é o estado atual que você está esse eu sei onde eu estou eu posso não lembrar da onde que eu vim nem para onde que eu vou né é uma mineira uma que eu tô pronto corro corro né agora então você sabe que o estado atual que você está e ele se a única que você conhece então se usa ele a seu favor funcionando ele como a memória

é o máximo que dá para fazer e uma outra dica que eu sempre faço quando eu estou construindo é eu já coloco diante mangual fiz aqui ó escreva num papelzinho do lado há sentenças que eu sei que essa não vai ser aceita Essa vai ser aceita Essa vai ser aceita e essa vai ser aceita eu visualizo aquelas que vão dar certo e aquelas que não vão dar certo e começa a produzir Milton é o que eu vou mostrar para vocês na aula que vem beleza pessoal então a gente finaliza por aqui e na aula que

vem a gente dá sequência na construção dos autônomos se você gostou dá um joinha para a gente aí compartilha com seus colegas um grande abraço pessoal valeu