Fundamentos Teoricos da Computação

Segunda Lista de Exercıcios Fundamentos Teoricos da Computacao Prof Julio Cesar da Silva Faculdade Cotemig Exercıcio 1 Classificacao de Linguagens Considere as seguintes linguagens sobre o alfabeto Σ a b Para cada uma delas determine a que classe pertence segundo a hierarquia de Chomsky a L1 anbn n 0 b L2 anbm n m 0 c L3 anbncn n 0 d L4 w a b w e palındromo Tarefa Classifique cada linguagem como regular livre de contexto sensıvel ao contexto ou irrestrita Justifique sua resposta brevemente com base nas caracterısticas de cada classe Dica Lembrese da Hierarquia de Chomsky Exercıcio 2 Derivacao e Reconhecimento de Padrao Considere a seguinte gramatica livre de contexto G V T P S onde V S A variaveis T a b terminais P contem as seguintes producoes S aSb A A λ S e o sımbolo inicial Tarefas a Mostre passo a passo como a gramatica gera a palavra aabb 1 Fundamentos Teoricos da Computacao Faculdade Cotemig b Mostre passo a passo como a gramatica gera a palavra aaabbb c Com base nessas derivacoes descreva um padrao geral para as palavras geradas por essa gramatica d A linguagem gerada por essa gramatica e regular Justifique Observacao o padrao de balanceamento entre os sımbolos a e b pode ser uma pista para a natureza da linguagem Exercıcio 3 Analise de Regras de Derivacao e Reco nhecedor Considere as seguintes regras de derivacao da gramatica G V T P S com V S e T a b S aS S Sb S aSb S ab S λ S bSa Tarefas a Dˆe dois exemplos de palavras que podem ser geradas por essa gramatica b Analise o padrao das palavras existe alguma simetria Algum balanceamento quanti dade de sımbolos a esquerda e a direita entre os sımbolos a e b c A gramatica permite derivar palavras com qualquer numero de as e bs ou ha restricoes d Classifique a linguagem ela e regular livre de contexto sensıvel ao contexto ou irrestrita Justifique e Indique qual tipo de reconhecedor pode ser usado para reconhecer a linguagem autˆomato finito determinıstico AFD autˆomato com pilha AP ou maquina de Turing MT Exercıcio 4 Notacoes Formais Gramatica e AFD Neste exercıcio vocˆe ira apresentar e analisar a notacao formal de dois conceitos centrais da teoria da computacao gramatica formal e autˆomato finito determinıstico AFD Tarefas a Apresente a notacao formal de uma gramatica G como uma quadrupla Defina cada elemento da quadrupla e explique seu papel no processo de derivacao b Apresente a notacao formal de um AFD como uma 5upla Explique o significado de cada elemento 2 Fundamentos Teoricos da Computacao Faculdade Cotemig c Faca uma comparacao entre os elementos das duas estruturas gramatica e AFD Existem relacoes entre as duas notacoes formais Ha alguma correspondˆencia entre regras de producao e funcao de transicao d Responda E possıvel um AFD ter mais de um estado inicial E mais de um estado de aceitacao Justifique com base na definicao formal Exercıcio 5 Construcao de AFD para uma Linguagem Regular Considere a linguagem L w a b w termina com ab Tarefas a Descreva informalmente como funciona um autˆomato que reconhece essa linguagem b A representacao abaixo AFD reconhece as palavras de L Justifique explicando o seu funcionamento de modo informal q q q ab a b ab c Escreva a notacao formal do AFD como uma 5upla d Teste se as palavras abaixo sao aceitas pelo autˆomato ab Sim aab Sim aba Nao abab Sim baba Nao Dica este exercıcio e um exemplo classico de reconhecimento de sufixo Uma abordagem util e lembrar dos dois ultimos sımbolos lidos 3 Fundamentos Teoricos da Computacao Faculdade Cotemig Exercıcio 6 Gramatica Regular equivalente ao AFD do Exercıcio 5 Com base no AFD construıdo no exercıcio anterior construa uma gramatica regular a di reita G V T P S tal que LG w a b w termina com ab Tarefas a Defina os componentes da gramatica V S A B sımbolos naoterminais um para cada estado do AFD T a b alfabeto da linguagem S sımbolo inicial da gramatica correspondente ao estado inicial do AFD b Escreva as producoes P com base nas transicoes do AFD veja se as letras nao terminais podem ser associadas aos estados do automato S aA bS A aA bB B aA bS λ c Justifique a presenca da producao B λ Lembrese que B representa o estado de aceitacao q2 do AFD Em gramaticas regulares o naoterminal que representa o estado final pode gerar λ indicando que a palavra pode terminar ali d Teste sua gramatica derivando as seguintes palavras ab aab abab e Compare o processo de derivacao com o comportamento do AFD ambos reconhecem exatamente as mesmas palavras Exercıcio 7 Introducao ao AFND Neste exercıcio vocˆe ira conhecer e trabalhar com Autˆomatos Finitos Nao Determinısticos AFND compreendendo sua notacao formal seu comportamento e suas diferencas em relacao aos AFDs Parte 1 Notacao Formal Apresente a definicao formal de um AFND como uma 5upla explique cada um dos seus elementos e quais desses elementos sao diferentes de um AFD Parte 2 Exemplo pratico Considere o seguinte AFND 4 Fundamentos Teoricos da Computacao Faculdade Cotemig q0 q1 q2 a ab b b Tarefas a Liste os elementos formais do AFND M b Complete a funcao de transicao δ indicando os multiplos caminhos possıveis c Simule o reconhecimento das palavras ab bab aab bbb d Para cada palavra indique Todas as possıveis sequˆencias de transicoes Se a palavra e ou nao aceita pelo autˆomato Parte 3 Reflexao Quais sao as principais diferencas entre um AFD e um AFND Todo AFND pode ser convertido em um AFD Justifique com base na teoria A linguagem reconhecida por esse AFND e regular Por quˆe Exercıcio 8 Conversao de AFND para AFD Neste exercıcio vocˆe devera aplicar o metodo de subconjuntos para converter um AFND em um AFD equivalente AFND dado Considere o seguinte AFND M Q Σ δ q0 F com Q q0 q1 q2 Σ a b q0 e o estado inicial F q2 5 Fundamentos Teoricos da Computacao Faculdade Cotemig δ definido por δq0 a q0 q1 δq0 b q0 δq1 b q2 δq2 a δq2 b Tarefas a Liste todos os subconjuntos possıveis de Q representando os estados do AFD b Construa a funcao de transicao δ do AFD com base na movimentacao por subconjuntos c Determine o estado inicial do AFD d Determine quais subconjuntos sao estados de aceitacao Dica o novo AFD tera estados representados por subconjuntos de Q como q0 q0q1 q1q2 etc Exemplo de transicao do AFD δq0 a δq0 a q0 q1 Reflexao Compare o tamanho e a complexidade do AFD obtido com o AFND original O que vocˆe observa Exercıcio 9 Expressoes Regulares e Linguagens Regu lares Considere a seguinte expressao regular a baa bb A linguagem gerada por essa ER e composta por todas as cadeias sobre o alfabeto a b que terminam em aa ou bb Tarefas a Escreva em linguagem natural uma descricao informal da linguagem definida pela ER b Expanda a linguagem gerada listando ao menos 10 palavras distintas pertencentes a ela c Desenhe um autˆomato finito determinıstico AFD que reconhece essa linguagem d Construa uma gramatica regular a direita G V T P S que gere essa mesma lingua gem e Discuta 6 Qual a relação entre expressões regulares autômatos finitos e gramáticas regulares Toda linguagem regular pode ser descrita por uma expressão regular Toda ER pode ser reconhecida por um AFD Dica a estrutura a baa bb exige que a cadeia tenha qualquer prefixo incluindo vazio mas terminando em aa ou bb Isso pode ser útil na construção do autômato ou da gramática Exercício 10 Representação Binária de Estados de um Tabuleiro de Xadrez Considere a ideia de representar um tabuleiro de xadrez por meio de cadeias binárias de acordo com a seguinte convenção O tabuleiro é representado como uma sequência de 64 posições linha por linha da esquerda para a direita e de cima para baixo Cada posição do tabuleiro é codificada por dois bits 00 casa vazia 01 peça branca 10 peça preta 11 estado inválido Portanto cada configuração completa do tabuleiro é representada por uma cadeia de exatamente 128 bits Exemplos Tabuleiro vazio 00 00 00 00 Tabuleiro inicial branco nas duas primeiras linhas preto nas duas últimas 01 01 00 00 10 10 Tabuleiro intermediário qualquer combinação de 00 01 e 10 desde que com 64 duplas de bits Tarefas a Escreva uma expressão regular ER que reconheça cadeias com exatamente 128 bits representando casas válidas ou seja sem 11 b Construa um AFD que reconheça se uma cadeia de 128 bits tem tamanho exato de 128 Fundamentos Teoricos da Computacao Faculdade Cotemig nao contem o padrao 11 c Justifique se a linguagem gerada e regular d E possıvel representar a linguagem dos tabuleiros validos com uma gramatica regular Por quˆe e Descreva uma modificacao que permitiria detectar se o tabuleiro esta em sua posicao inicial completa Dica A ER para reconhecer cadeias com 64 pares de bits validos ie 00 01 ou 10 pode ser expressa como 00011064 Isso corresponde a 128 bits validos em duplas cada dupla representando uma casa do tabuleiro Desafio opcional como vocˆe construiria um AFD minimizado para essa linguagem Quan tos estados seriam necessarios Referˆencia cruzada essa linguagem e regular porque pode ser reconhecida por um AFD que verifica O tamanho total da cadeia contagem de duplas A validade de cada par de bits A ausˆencia do padrao invalido 11 AFD para cadeias com pares validos 00 01 10 Este AFD aceita cadeias com pares de bits formados por 00 01 ou 10 Qualquer ocorrˆencia do par 11 leva ao erro q0 q1 q2 qerr 0 1 0 1 0 1 01 O autˆomato lˆe os bits dois a dois Se encontrar o par 11 transita para um estado de erro qerr A aceitacao depende de terminar no estado q0 apos 128 bits 64 pares 8 a L₁ aⁿbⁿ n 0 Esta linguagem não é regular porque requer memória para lembrar o número de as para garantir que corresponda ao número de bs É uma linguagem livre de contexto Pode ser gerada por uma gramática livre de contexto Gramática de exemplo S aSb ε b L₂ aⁿbᵐ n m 0 Esta linguagem é regular Pode ser representada por uma expressão regular como ab Também pode ser gerada por uma gramática regular Gramática de exemplo S aS B B bB ε c L₃ aⁿbⁿcⁿ n 0 Esta linguagem não é livre de contexto Requer memória para comparar três contagens a b c É uma linguagem sensível ao contexto Uma gramática sensível ao contexto seria necessária para gerar essa linguagem d L₄ w a b w é palíndromo Esta linguagem não é regular porque requer memória para comparar a primeira metade da string com a segunda metade invertida É uma linguagem livre de contexto Pode ser gerada por uma gramática livre de contexto Gramática de exemplo S aSa bSb a b ε a Para gerar a palavra aabb usando a gramática dada podemos seguir os seguintes passos de derivação 1 Começamos com o símbolo inicial S 2 Aplicamos a produção S aSb duas vezes para gerar dois as e dois bs S aSb aaSbb 3 Agora aplicamos a produção S A aaSbb aaAbb 4 Finalmente aplicamos a produção A λ onde λ representa a string vazia aaAbb aabb Portanto a derivação completa é S aSb aaSbb aaAbb aabb b Para gerar a palavra aaabbb usando a gramática dada podemos seguir os seguintes passos de derivação 1 Começamos com o símbolo inicial S 2 Aplicamos a produção S aSb três vezes para gerar três as e três bs S aSb aaSbb aaaSbbb 3 Agora aplicamos a produção S A aaaSbbb aaaAbbb 4 Finalmente aplicamos a produção A λ onde λ representa a string vazia aaaAbbb aaabbb Portanto a derivação completa é S aSb aaSbb aaaSbbb aaaAbbb aaabbb c Com base nessas derivações podemos descrever um padrão geral para as palavras geradas por essa gramática A gramática gera palavras da forma aⁿbⁿ onde n é um número inteiro não negativo Isso significa que a palavra terá um número igual de as seguidos por um número igual de bs d A linguagem gerada por essa gramática não é regular A razão para isso é que linguagens regulares não podem contar ou lembrar um número arbitrário de ocorrências de um símbolo para então corresponder a um número igual de ocorrências de outro símbolo A gramática em questão requer que o número de as seja igual ao número de bs o que exige uma forma de memória que as linguagens regulares não possuem Linguagens que exigem essa forma de correspondência são tipicamente linguagens livres de contexto mas não regulares 3 a Dois exemplos de palavras que podem ser geradas por essa gramática são 1 ab Esta é a derivação mais direta usando a regra S ab 2 aab Esta palavra pode ser derivada usando as regras S aS seguido por S ab resultando em aab b Análise do padrão das palavras Simetria Não há uma simetria estrita A gramática permite gerar palavras com a e b em várias ordens e quantidades Balanceamento Não há um balanceamento obrigatório A gramática pode gerar palavras com mais as do que bs mais bs do que as ou quantidades iguais c A gramática não permite derivar palavras com qualquer número de as e bs sem restrições Existem restrições impostas pelas regras de produção Por exemplo a regra S ab introduz uma restrição de que a palavra deve ter pelo menos um a e um b As regras S aS e S Sb permitem adicionar as e bs respectivamente mas sempre a partir de um S não terminal d Classificação da linguagem A linguagem é livre de contexto Justificativa As regras de produção da gramática têm a forma A α onde A é um não terminal e α é uma sequência de terminais e não terminais Isso está de acordo com a definição de gramáticas livres de contexto Não é regular porque a regra S bSa exige que a ordem dos símbolos seja lembrada o que não pode ser feito por um autômato finito determinístico AFD Não é sensível ao contexto nem irrestrita pois as regras são mais restritas do que as permitidas nessas categorias e Tipo de reconhecedor Um autômato com pilha AP pode ser usado para reconhecer a linguagem Justificativa A necessidade de manter o controle da ordem dos símbolos como na regra S bSa exige uma estrutura de memória que um autômato finito determinístico AFD não possui Um autômato com pilha pode armazenar símbolos na pilha e usálos para garantir que a ordem correta seja seguida Uma máquina de Turing MT também poderia reconhecer a linguagem mas é uma ferramenta mais poderosa do que o necessário para uma linguagem livre de contexto 4 a Notação Formal de uma Gramática G como uma Quádrupla Uma gramática formal G é definida como uma quádrupla G V T P S Onde V Variáveis ou NãoTerminais É um conjunto finito de símbolos que representam categorias sintáticas ou construções da linguagem Eles são usados para derivar strings na linguagem T Terminais É um conjunto finito de símbolos que formam as strings da linguagem Estes são os símbolos que aparecem na saída final da derivação P Produções É um conjunto finito de regras de produção da forma α β onde α é uma string contendo pelo menos um símbolo nãoterminal e β é uma string de símbolos terminais eou nãoterminais As produções definem como os nãoterminais podem ser substituídos por outras combinações de símbolos S Símbolo Inicial É um símbolo nãoterminal especial que representa o ponto de partida para a derivação de strings na linguagem Papel no Processo de Derivação O processo de derivação começa com o símbolo inicial S As regras de produção em P são aplicadas sequencialmente para substituir nãoterminais por outras strings até que a string resultante contenha apenas símbolos terminais Essa string terminal é então uma string válida na linguagem gerada pela gramática G b Notação Formal de um AFD como uma 5úpla Um Autômato Finito Determinístico AFD é definido como uma 5úpla M Q Σ δ q₀ F Onde Q Estados É um conjunto finito de estados Σ Alfabeto É um conjunto finito de símbolos de entrada δ Função de Transição É uma função que mapeia um estado e um símbolo de entrada para um único estado ou seja δ Q Σ Q q₀ Estado Inicial É o estado em que o autômato começa o processamento q₀ Q F Estados de Aceitação ou Finais É um conjunto de estados em que o autômato aceita a entrada F Q Significado de Cada Elemento O AFD lê uma string de entrada símbolo por símbolo A função de transição δ determina como o autômato se move entre os estados com base no símbolo de entrada atual Se após ler toda a string de entrada o autômato estiver em um estado de aceitação a string é aceita caso contrário é rejeitada c Comparação entre Gramática e AFD Elementos das Estruturas Gramática Define a sintaxe de uma linguagem através de regras de produção AFD Define um mecanismo para reconhecer strings pertencentes a uma linguagem Relações entre as Notações Formais Ambas são notações formais usadas na teoria da computação para descrever linguagens Gramáticas geram linguagens enquanto AFDs reconhecem linguagens Correspondência entre Regras de Produção e Função de Transição Em termos gerais pode haver uma correspondência indireta Para uma gramática regular é possível construir um AFD que reconheça a mesma linguagem gerada pela gramática As regras de produção da gramática regular podem ser vistas como definindo as transições entre os estados do AFD d Resposta sobre AFD com Múltiplos Estados Iniciais ou de Aceitação Múltiplos Estados Iniciais Não um AFD não pode ter mais de um estado inicial Por definição um AFD tem exatamente um estado inicial Múltiplos Estados de Aceitação Sim um AFD pode ter múltiplos estados de aceitação O conjunto F pode conter qualquer número de estados de Q incluindo todos alguns ou nenhum 5 a O autômato funciona da seguinte forma ele lê a entrada símbolo por símbolo Ele se mantém no estado inicial até ler um a Quando lê um a ele vai para o segundo estado Se a partir do segundo estado ele lê um b ele vai para o estado final indicando que a palavra termina com ab Se em qualquer estado ele lê um símbolo que não o leva ao estado final ou seja lê um b no estado inicial ou um a no segundo estado ele permanece no estado atual O autômato aceita a palavra se ao final da leitura ele estiver no estado final b Sim a representação AFD reconhece as palavras de L O autômato começa no estado inicial Se a entrada começa com b ele permanece no estado inicial Se a entrada começa com a ele transita para o próximo estado A partir desse estado se ele lê b ele vai para o estado final que é um estado de aceitação Se ele lê a novamente ele volta para o estado intermediário O estado final tem um loop com a e b garantindo que qualquer sequência após ab não afete a aceitação c A notação formal do AFD como uma 5úpla é Q q0 q1 q2 conjunto de estados Σ a b alfabeto δ função de transição δq0 a q1 δq0 b q0 δq1 a q1 δq1 b q2 δq2 a q2 δq2 b q2 q0 estado inicial F q2 conjunto de estados finais d Teste das palavras ab Sim q0 q1 q2 aab Sim q0 q1 q1 q2 aba Não q0 q1 q2 q1 abab Sim q0 q1 q2 q0 q1 q2 baba Não q0 q0 q1 q2 q1 6 a Definição dos componentes da gramática V S A B Conjunto de símbolos nãoterminais onde S representa o estado inicial A e B representam os outros estados do AFD T a b Alfabeto da linguagem contendo os símbolos terminais a e b S Símbolo inicial da gramática correspondente ao estado inicial do AFD b Produções P com base nas transições do AFD As produções são construídas de forma que simulem as transições do AFD Para garantir que a string termine com ab as produções devem refletir essa exigência As produções fornecidas no enunciado parecem ter um erro pois não garantem que a string termine com ab As produções corretas seriam S rightarrow aA mid bS A rightarrow aA mid bB B rightarrow lambda c Justificativa da produção B λ A produção B λ é crucial porque B representa o estado de aceitação No AFD o estado B ou q2 como mencionado é o estado final que indica que a string terminou com ab Finalização da derivação Em gramáticas regulares um nãoterminal que representa o estado final pode derivar em λ string vazia Isso significa que ao atingir o estado B a derivação pode ser finalizada indicando que a palavra foi aceita termina com ab d Teste da gramática derivando as palavras 1 ab S Rightarrow aA Rightarrow abB Rightarrow ab 2 aab S Rightarrow aA Rightarrow aaA Rightarrow aabB Rightarrow aab 3 abab S Rightarrow aA Rightarrow abB Rightarrow abaA Rightarrow ababB Rightarrow abab e Comparação do processo de derivação com o comportamento do AFD Sim o processo de derivação na gramática e o comportamento do AFD reconhecem exatamente as mesmas palavras A gramática foi construída para simular o comportamento do AFD garantindo que apenas as strings que terminam com ab sejam aceitas Cada passo na derivação corresponde a uma transição no AFD e a aceitação da palavra derivação completa ocorre quando o AFD atinge um estado final 7 Parte 1 Notação Formal Um AFND é formalmente definido como uma 5tupla M Q Σ δ q0 F onde 1 Q é um conjunto finito de estados 2 Σ é um alfabeto finito de símbolos de entrada 3 δ Q Σ PQ é a função de transição que mapeia um estado e um símbolo de entrada para um conjunto de estados possíveis 4 q0 Q é o estado inicial 5 F Q é o conjunto de estados finais ou de aceitação A principal diferença entre um AFND e um AFD reside na função de transição δ Em um AFD δ mapeia um estado e um símbolo para um único estado ou seja a transição é determinística Em um AFND δ pode mapear um estado e um símbolo para um conjunto de estados permitindo múltiplas transições possíveis ou nenhuma transição implícita Parte 2 Exemplo Prático Dado o AFND a Elementos formais do AFND M Q q0 q1 q2 Σ a b q0 é o estado inicial F q2 Função de transição δ detalhada abaixo b Função de transição δ δq0 a q0 q1 δq0 b q0 δq1 a Ø δq1 b q2 δq2 a Ø δq2 b Ø c Simulação do reconhecimento das palavras ab Caminho 1 q0aq0bq0 Rejeitada Caminho 2 q0aq1bq2 Aceita bab Caminho 1 q0bq0aq0bq0 Rejeitada Caminho 2 q0bq0aq1bq2 Aceita aab Caminho 1 q0aq0aq0bq0 Rejeitada Caminho 2 q0aq0aq1bq2 Aceita Caminho 3 q0aq1abloqueio Rejeitada bbb Caminho 1 q0bq0bq0bq0 Rejeitada d Para cada palavra ab Sequências de transições q0aq0bq0 q0aq1bq2 Aceita Sim bab Sequências de transições q0bq0aq0bq0 q0bq0aq1bq2 Aceita Sim aab Sequências de transições q0aq0aq0bq0 q0aq0aq1bq2 q0aq1abloqueio Aceita Sim bbb Sequências de transições q0bq0bq0bq0 Aceita Não Parte 3 Reflexão Diferenças entre AFD e AFND Em um AFD para cada estado e símbolo de entrada há exatamente uma transição possível Em um AFND pode haver nenhuma uma ou múltiplas transições possíveis AFDs são mais simples de implementar mas AFNDs podem ser mais fáceis de construir para certos problemas Conversão de AFND para AFD Sim todo AFND pode ser convertido em um AFD equivalente usando o algoritmo de construção de subconjuntos Este algoritmo cria estados no AFD que representam conjuntos de estados do AFND Linguagem reconhecida pelo AFND é regular Sim a linguagem reconhecida por este AFND é regular AFNDs e AFDs reconhecem linguagens regulares A regularidade pode ser comprovada pela existência de um AFD equivalente ou pela construção de uma expressão regular que descreva a mesma linguagem Neste caso a linguagem aceita pelo autômato pode ser descrita como abab que é uma expressão regular 8 a Liste todos os subconjuntos possíveis de Q representando os estados do AFD Os subconjuntos possíveis de Q q0 q1 q2 são conjunto vazio q0 q1 q2 q0 q1 q0 q2 q1 q2 q0 q1 q2 b Construa a função de transição δ do AFD com base na movimentação por subconjuntos Para construir a função de transição δ precisamos calcular as transições para cada subconjunto de estados com cada símbolo do alfabeto Σ a b 1 δ a δ b O conjunto vazio sempre transiciona para o conjunto vazio 2 δq0 a δq0 a q0 q1 δq0 b δq0 b q0 3 δq1 a δq1 a δq1 b δq1 b q2 4 δq2 a δq2 a δq2 b δq2 b 5 δq0 q1 a δq0 a U δq1 a q0 q1 U q0 q1 δq0 q1 b δq0 b U δq1 b q0 6 δq0 q2 a δq0 a U δq2 a q0 q1 U q0 q1 δq0 q2 b δq0 b U δq2 b q0 U q0 7 δq1 q2 a δq1 a U δq2 a U δq1 q2 b δq1 b U δq2 b q2 U q2 8 δq0 q1 q2 a δq0 a U δq1 a U δq2 a q0 q1 U U q0 q1 δq0 q1 q2 b δq0 b U δq1 b U δq2 b q0 U q2 U q0 q2 Tabela de Transição do AFD Estado a b q0 q0 q1 q0 q1 q2 q2 q0 q1 q0 q1 q0 q2 q0 q2 q0 q1 q0 q1 q2 q2 q0 q1 q2 q0 q1 q0 q2 c Determine o estado inicial do AFD O estado inicial do AFD é o conjunto que contém o estado inicial do AFND que é q0 d Determine quais subconjuntos são estados de aceitação Os estados de aceitação do AFD são os subconjuntos que contêm o estado de aceitação do AFND que é q2 Portanto os estados de aceitação são q2 q0 q2 q1 q2 q0 q1 q2 Reflexão O AFD resultante tem um número maior de estados 8 estados em comparação com o AFND original 3 estados Isso é comum ao converter um AFND para um AFD pois o AFD precisa representar todas as possíveis combinações de estados que o AFND pode estar em um determinado momento A complexidade também aumenta pois a tabela de transição do AFD é maior e mais complexa de analisar do que a função de transição do AFND original 9 a Descrição informal da linguagem A linguagem definida pela expressão regular abaabb é o conjunto de todas as strings formadas pelas letras a e b que terminam com aa ou bb O prefixo ab significa que qualquer combinação de as e bs incluindo a string vazia pode preceder a terminação aa ou bb b Expansão da linguagem 10 palavras distintas 1 aa 2 bb 3 aaa 4 aab 5 bba 6 bbb 7 aaaa 8 aabb 9 bbaa 10 bbbb c Autômato Finito Determinístico AFD Um AFD para essa linguagem pode ser construído com os seguintes estados q0 Estado inicial q1 Leu a q2 Leu b q3 Leu aa estado final q4 Leu bb estado final q5 Leu a após b q6 Leu b após a As transições seriam δq0 a q1 δq0 b q2 δq1 a q3 δq1 b q5 δq2 a q6 δq2 b q4 δq3 a q3 δq3 b q5 δq4 a q6 δq4 b q4 δq5 a q3 δq5 b q4 δq6 a q3 δq6 b q4 Estados finais q3 q4 d Gramática Regular à Direita G V T P S V Variáveis S A B T Terminais a b P Produções S aA bB aa bb A aA bB aa bb B aA bB aa bb S Símbolo Inicial S e Discussão Relação entre expressões regulares autômatos finitos e gramáticas regulares Expressões regulares autômatos finitos AFDs ou AFNs e gramáticas regulares são formalismos equivalentes para descrever linguagens regulares Qualquer linguagem que pode ser descrita por uma expressão regular pode ser reconhecida por um autômato finito e gerada por uma gramática regular e viceversa Toda linguagem regular pode ser descrita por uma expressão regular Sim por definição Uma linguagem é considerada regular se e somente se pode ser descrita por uma expressão regular Toda ER pode ser reconhecida por um AFD Sim Existe um algoritmo para converter qualquer expressão regular em um Autômato Finito NãoDeterminístico AFN e subsequentemente em um Autômato Finito Determinístico AFD equivalente 10 a Expressão regular ER que reconhece cadeias com exatamente 128 bits representando casas válidas ou seja sem 11 ER 00011064 Esta expressão regular indica que a cadeia deve ser composta por exatamente 64 pares de bits onde cada par pode ser 00 01 ou 10 b Autômato Finito Determinístico AFD que reconhece uma cadeia de 128 bits Um AFD para reconhecer uma cadeia de 128 bits teria 129 estados 0 a 128 O estado inicial seria o estado 0 Para cada bit lido o autômato transitária para o próximo estado Se após ler 128 bits o autômato estiver no estado 128 a cadeia é aceita Caso contrário é rejeitada c Justificar se a linguagem gerada é regular A linguagem gerada é regular porque pode ser definida por uma expressão regular como mostrado no item a e pode ser reconhecida por um AFD como descrito no item b Linguagens que podem ser expressas por expressões regulares ou reconhecidas por AFDs são por definição regulares d É possível representar a linguagem dos tabuleiros válidos com uma gramática regular Sim é possível Uma gramática regular pode ser construída para gerar todas as combinações de 64 pares de bits válidos 00 01 10 Cada regra da gramática geraria um par de bits válido e após 64 regras serem aplicadas a cadeia estaria completa e Descrever uma modificação que permitiria detectar se o tabuleiro está em sua posição inicial completa Para detectar se o tabuleiro está na posição inicial completa seria necessário verificar se os pares de bits correspondem à configuração inicial esperada Isso pode ser feito comparando a cadeia de 128 bits com uma cadeia predefinida que representa a posição inicial do tabuleiro Se as duas cadeias forem iguais o tabuleiro está na posição inicial Dica A ER para reconhecer cadeias com 64 pares de bits válidos ie 00 01 ou 10 pode ser expressa como 00011064 Isso corresponde a 128 bits válidos em duplas cada dupla representando uma casa do tabuleiro Desafio opcional Como você construiria um AFD minimizado para essa linguagem Quantos estados seriam necessários Para construir um AFD minimizado você precisaria identificar e combinar estados equivalentes No caso da linguagem dos tabuleiros válidos o AFD minimizado teria um estado inicial um estado de aceitação e um estado de erro O AFD leria os bits dois a dois Se encontrar o par 11 transita para o estado de erro Se ler 64 pares válidos 00 01 ou 10 sem encontrar 11 transita para o estado de aceitação Referência cruzada Essa linguagem é regular porque pode ser reconhecida por um AFD que verifica O tamanho total da cadeia contagem de duplas A validade de cada par de bits A ausência do padrão inválido 11 AFD para cadeias com pares válidos 00 01 10 O AFD aceita cadeias com pares de bits formados por 00 01 ou 10 Qualquer ocorrência do par 11 leva ao erro O autômato lê os bits dois a dois Se encontrar o par 11 transita para um estado de erro A aceitação depende de terminar no estado q0 após 128 bits 64 pares