Teoria da Computação: Máquinas de Turing e Exemplos

Teoria da Computação Aula 11 Máquinas de Turing exemplos e variantes Prof Alex Torquato Souza Carneiro alexcarneirofaculdadeimpactacombr Os diagramas de Máquinas de Turing são formados de modo a resolver um problema de reconhecimento de linguagens Para obtermos um diagrama devemos modelar primeiro o comportamento desejado da Máquina de Turing Diagramas 2 Os diagramas de Máquinas de Turing são formados de modo a resolver um problema de reconhecimento de linguagens Para obtermos um diagrama devemos modelar primeiro o comportamento desejado da Máquina de Turing Por exemplo uma Máquina de Turing que reconhece a linguagem L 011 Diagramas 3 Os diagramas de Máquinas de Turing são formados de modo a resolver um problema de reconhecimento de linguagens Para obtermos um diagrama devemos modelar primeiro o comportamento desejado da Máquina de Turing Por exemplo uma Máquina de Turing que reconhece a linguagem L 011 Diagramas 4 Exemplos de strings 1 0111 001 011 101 111 0001 1001 Exemplo 1 5 Obter uma Máquina de Turing que reconhece a linguagem L 011 Exemplo 1 6 Obter uma Máquina de Turing que reconhece a linguagem L 011 Comportamento esperado 1 Exemplo 1 7 Obter uma Máquina de Turing que reconhece a linguagem L 011 Comportamento esperado 1 Exemplo 1 8 Obter uma Máquina de Turing que reconhece a linguagem L 011 Comportamento esperado 1 Exemplo 1 9 Obter uma Máquina de Turing que reconhece a linguagem L 011 Comportamento esperado 1 Exemplo 1 10 Obter uma Máquina de Turing que reconhece a linguagem L 011 Comportamento esperado 1 Exemplo 1 11 Obter uma Máquina de Turing que reconhece a linguagem L 011 Comportamento esperado 1 Exemplo 1 12 Obter uma Máquina de Turing que reconhece a linguagem L 011 Comportamento esperado 1 Exemplo 1 13 Obter uma Máquina de Turing que reconhece a linguagem L 011 Comportamento esperado 1 Exemplo 1 14 Obter uma Máquina de Turing que reconhece a linguagem L 011 Comportamento esperado 1 String aceita Exemplo 1 15 Obter uma Máquina de Turing que reconhece a linguagem L 011 A Máquina de Turing avança para a direita até que encontre o espaço final da string caso o último elemento antes do espaço seja 1 a string é aceita Comportamento esperado 1 String aceita Obter uma Máquina de Turing que reconhece a linguagem L 011 Exemplo 1 16 q0 q2 q1 1 R 0 R Exemplo 1 17 q0 q2 q1 1 R 0 R 1 R 0 R Obter uma Máquina de Turing que reconhece a linguagem L 011 Exemplo 1 18 q0 q2 q1 1 R 0 R 1 R 0 R 1 R 0 R Obter uma Máquina de Turing que reconhece a linguagem L 011 Exemplo 1 19 q0 q2 q1 qaceita 1 R 0 R 1 R 0 R R 1 R 0 R Obter uma Máquina de Turing que reconhece a linguagem L 011 Exemplo 1 20 q0 q2 q1 qrejeita qaceita 1 R 0 R 1 R 0 R R R 1 R 0 R Obter uma Máquina de Turing que reconhece a linguagem L 011 Exemplo 2 21 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Exemplo 2 22 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Exemplos de strings 01 0011 000111 00001111 Exemplo 2 23 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado 0 0 0 1 1 1 Exemplo 2 24 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado 0 0 0 1 1 1 Exemplo 2 25 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x 0 0 1 1 1 Exemplo 2 26 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x 0 0 1 1 1 Exemplo 2 27 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x 0 0 1 1 1 Exemplo 2 28 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x 0 0 1 1 1 Exemplo 2 29 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x 0 0 y 1 1 Exemplo 2 30 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x 0 0 y 1 1 Exemplo 2 31 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x 0 0 y 1 1 Exemplo 2 32 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x 0 0 y 1 1 Exemplo 2 33 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x 0 0 y 1 1 Exemplo 2 34 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x 0 y 1 1 Exemplo 2 35 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x 0 y 1 1 Exemplo 2 36 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x 0 y 1 1 Exemplo 2 37 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x 0 y 1 1 Exemplo 2 38 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x 0 y y 1 Exemplo 2 39 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x 0 y y 1 Exemplo 2 40 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x 0 y y 1 Exemplo 2 41 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x 0 y y 1 Exemplo 2 42 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x 0 y y 1 Exemplo 2 43 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x x y y 1 Exemplo 2 44 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x x y y 1 Exemplo 2 45 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x x y y 1 Exemplo 2 46 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x x y y 1 Exemplo 2 47 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x x y y y Exemplo 2 48 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x x y y y Exemplo 2 49 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x x y y y Exemplo 2 50 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x x y y y Exemplo 2 51 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x x y y y Exemplo 2 52 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x x y y y Exemplo 2 53 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x x y y y Exemplo 2 54 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x x y y y Exemplo 2 55 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Comportamento esperado x x x y y y String aceita Exemplo 2 56 Comportamento esperado x x x y y y String aceita Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 A Máquina de Turing marca o primeiro 0 como x avança para a direita até que encontre o 1 marca como y volta para a esquerda até o x se o elemento à direita for 1 repete o processo caso contrário avança até o último y Se depois do último y houver um espaço a string é aceita Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Exemplo 2 57 q0 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Exemplo 2 58 q0 1 R qrejeita Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Exemplo 2 59 q0 q1 0 x R 1 R qrejeita 0 y R Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Exemplo 2 60 q0 q1 0 x R 1 R qrejeita 0 y R q2 1 y L 0 y L Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Exemplo 2 61 q0 q1 0 x R 1 R qrejeita 0 y R q2 1 y L 0 y L x R Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Exemplo 2 62 q0 q1 0 x R 1 R qrejeita 0 y R q2 1 y L 0 y L x R q3 y R Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Exemplo 2 63 q0 q1 0 x R 1 R qrejeita 0 y R q2 1 y L 0 y L x R q3 y R y R Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Exemplo 2 64 q0 q1 0 x R 1 R qrejeita 0 y R q2 1 y L 0 y L x R q3 y R y R qaceita R Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Exemplo 2 65 q0 q1 0 x R 1 R qrejeita 0 y R q2 1 y L 0 y L x R q3 y R y R qaceita R 1 R Obter uma Máquina de Turing que reconhece a linguagem L 0n1n n 0 Exemplo 2 66 q0 q1 0 x R 1 R qrejeita 0 y R q2 1 y L 0 y L x R q3 y R y R qaceita R 1 R qrejeita R Exemplo 3 67 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 68 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplos de strings 012 001122 000111222 000011112222 Exemplo 3 69 Comportamento esperado 0 0 1 1 2 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 70 Comportamento esperado 0 0 1 1 2 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 71 Comportamento esperado x 0 1 1 2 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 72 Comportamento esperado x 0 1 1 2 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 73 Comportamento esperado x 0 1 1 2 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 74 Comportamento esperado x 0 y 1 2 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 75 Comportamento esperado x 0 y 1 2 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 76 Comportamento esperado x 0 y 1 2 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 77 Comportamento esperado x 0 y 1 z 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 78 Comportamento esperado x 0 y 1 z 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 79 Comportamento esperado x 0 y 1 z 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 80 Comportamento esperado x 0 y 1 z 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 81 Comportamento esperado x 0 y 1 z 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 82 Comportamento esperado x 0 y 1 z 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 83 Comportamento esperado x x y 1 z 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 84 Comportamento esperado x x y 1 z 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 85 Comportamento esperado x x y 1 z 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 86 Comportamento esperado x x y y z 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 87 Comportamento esperado x x y y z 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 88 Comportamento esperado x x y y z 2 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 89 Comportamento esperado x x y y z z Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 90 Comportamento esperado x x y y z z Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 91 Comportamento esperado x x y y z z Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 92 Comportamento esperado x x y y z z Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 93 Comportamento esperado x x y y z z Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 94 Comportamento esperado x x y y z z Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 95 Comportamento esperado x x y y z z Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 96 Comportamento esperado x x y y z z Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 97 Comportamento esperado x x y y z z Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 98 Comportamento esperado x x y y z z Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 Exemplo 3 99 Comportamento esperado x x y y z z Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 String aceita Exemplo 3 100 Obter uma Máquina de Turing que reconhece a linguagem L 0n1n2n n 0 q0 q1 0 x R 1 R qrejeita 0 y R q3 1 y R 0 1 x y L x R q4 y R y z R qaceita R 1 2 R qrejeita 2 R q2 1 z R 2 z L R Variantes da Máquina de Turing Definição da Máquina de Turing Máquina de Turing 102 Definição da Máquina de Turing Q 𝚺 𝚪 𝛅 q0 qaceitação qrejeição Máquina de Turing 103 Definição da Máquina de Turing Q 𝚺 𝚪 𝛅 q0 qaceitação qrejeição Q conjunto de estados 𝚺 alfabeto sem contar o espaço em branco 𝚪 alfabeto da fita incluindo o espaço em branco 𝛅 Q x 𝚪 Q x 𝚪 x L R função de transição q0 estado inicial qaceitação estados de aceitação qrejeição estados de rejeição Máquina de Turing 104 Definição da Máquina de Turing Q 𝚺 𝚪 𝛅 q0 qaceitação qrejeição Q conjunto de estados 𝚺 alfabeto sem contar o espaço em branco 𝚪 alfabeto da fita incluindo o espaço em branco 𝛅 Q x 𝚪 Q x 𝚪 x L R função de transição q0 estado inicial qaceitação estados de aceitação qrejeição estados de rejeição Máquina de Turing 105 L Left R Right Variantes Tanto a Máquina de Turing formal que já definimos como suas variantes reconhecem as mesmas linguagens 106 Variantes Tanto a Máquina de Turing formal que já definimos como suas variantes reconhecem as mesmas linguagens Semelhante ao que observamos nos AFD e AFND 107 Máquina de Turing com múltiplas fitas 108 Máquina de Turing com múltiplas fitas 109 Máquina de Turing com múltiplas fitas A ideia da Máquina de Turing com múltiplas fitas multifita é aumentar a liberdade de quem está construindo o modelo 110 Máquina de Turing com múltiplas fitas A ideia da Máquina de Turing com múltiplas fitas multifita é aumentar a liberdade de quem está construindo o modelo Por outro lado com mais fitas temos uma maior complexidade para o modelo que poderá ser gerado 111 Máquina de Turing com múltiplas fitas A ideia da Máquina de Turing com múltiplas fitas multifita é aumentar a liberdade de quem está construindo o modelo Por outro lado com mais fitas temos uma maior complexidade para o modelo que poderá ser gerado 𝛅 Q x 𝚪k Q x 𝚪k x L RPk função de transição Modelo com k fitas 112 Máquina de Turing com múltiplas fitas Em uma Máquina de Turing Multifita a string encontrase inicialmente na fita 1 e as demais estão vazias 113 Máquina de Turing com múltiplas fitas Em uma Máquina de Turing Multifita a string encontrase inicialmente na fita 1 e as demais estão vazias A leitura e a escrita em uma Máquina de Turing Multifita ocorre de forma independente em cada fita 114 Máquina de Turing com múltiplas fitas Toda Máquina de Turing Multifita tem uma Máquina de Turing de fita equivalente com uma única fita 115 Máquina de Turing com múltiplas fitas Toda Máquina de Turing Multifita tem uma Máquina de Turing de fita equivalente com uma única fita Uma aplicação das Máquinas de Turing Multifita é a geração de strings nas fitas 2 em diante a partir da string presente na fita 1 116 Máquina de Turing NãoDeterminísticas 117 Máquina de Turing NãoDeterminísticas Assim como os autômatos que podemos ter modelos não determinísticos ao introduzirmos a ideia de múltiplas instâncias de um mesmo autômato as Máquinas de Turing também apresentam a possibilidade de termos múltiplas instâncias simultâneas 118 Máquina de Turing NãoDeterminísticas Assim como os autômatos que podemos ter modelos não determinísticos ao introduzirmos a ideia de múltiplas instâncias de um mesmo autômato as Máquinas de Turing também apresentam a possibilidade de termos múltiplas instâncias simultâneas 𝛅 Q x 𝚪 𝓟Q x 𝚪 x L R 119 Máquina de Turing NãoDeterminísticas Toda Máquina de Turing NãoDeterminística tem uma Máquina de Turing Determinística equivalente 120 Máquina de Turing NãoDeterminísticas Toda Máquina de Turing NãoDeterminística tem uma Máquina de Turing Determinística equivalente Assim como feito com os AFND uma Máquinas de Turing NãoDeterminística aceita uma string quando uma de suas instâncias alcança um estado de aceitação 121 Teoria da Computação Aula 10 Máquina de Turing Prof Alex Torquato Souza Carneiro alexcarneirofaculdadeimpactacombr Agenda Motivação Criptografia básica Máquina de Turing 2 Alan Turing viveu durante a Segunda Guerra mundial e foi um dos responsáveis pela vitória contra os nazistas alemães Motivação 3 Fonte httpg1globocomtecnologianoticia201312paidacomputacaoturingrecebeoperdaoreal59anosaposmorrerhtml Um dos trunfos dos alemães era a máquina Enigma que criptografava mensagens enviadas durante a guerra Motivação 4 Um dos trunfos dos alemães era a máquina Enigma que criptografava mensagens enviadas durante a guerra As mensagens enviadas faziam com que os alemães conseguissem tomar decisões e executar seus planos de forma mais eficiente que seus adversários Motivação 5 Um dos trunfos dos alemães era a máquina Enigma que criptografava mensagens enviadas durante a guerra As mensagens enviadas faziam com que os alemães conseguissem tomar decisões e executar seus planos de forma mais eficiente que seus adversários Vídeos sobre a Enigma httpswwwyoutubecomwatchvKckB5GhNnE httpswwwyoutubecomwatchvVMJeDLv2suw Motivação 6 Como as mensagens eram criptografadas era possível capturar os dados mas não recuperar a informação enviada Motivação 7 Como as mensagens eram criptografadas era possível capturar os dados mas não recuperar a informação enviada Neste cenário Alan Turing propôs um modelo matemático capaz de decriptar as mensagens alemãs Motivação 8 Como as mensagens eram criptografadas era possível capturar os dados mas não recuperar a informação enviada Neste cenário Alan Turing propôs um modelo matemático capaz de decriptar as mensagens alemãs Este modelo é chamado Máquina de Turing Motivação 9 A forma mais simples de criptografia de uma mensagem é criar um padrão de associação entre as letras Criptografia 10 A forma mais simples de criptografia de uma mensagem é criar um padrão de associação entre as letras Exemplo para cada letra da palavra associamos a letra seguinte do alfabeto Criptografia 11 A forma mais simples de criptografia de uma mensagem é criar um padrão de associação entre as letras Exemplo para cada letra da palavra associamos a letra seguinte do alfabeto Palavra original IMPACTA Palavra criptografada JNQBDUB Criptografia 12 A forma mais simples de criptografia de uma mensagem é criar um padrão de associação entre as letras Exemplo para cada letra da palavra associamos a letra seguinte do alfabeto Palavra original IMPACTA Palavra criptografada JNQBDUB I J M N P Q A B C D T U A B Criptografia 13 Para decriptar a palavra recebida devemos conhecer a regra de criptografia e a chave criptográfica Criptografia 14 Para decriptar a palavra recebida devemos conhecer a regra de criptografia e a chave criptográfica Para nosso exemplo a regra é escolher uma letra à frente da real e a chave é o valor 1 que corresponde à quantas letras devemos avançar Criptografia 15 Para decriptar a palavra recebida devemos conhecer a regra de criptografia e a chave criptográfica Para nosso exemplo a regra é escolher uma letra à frente da real e a chave é o valor 1 que corresponde à quantas letras devemos avançar Criptografia 16 Entrada A B C D E F X Y Z Saída B C D E F G Y Z A Para decriptar a palavra recebida devemos conhecer a regra de criptografia e a chave criptográfica Em outro exemplo podemos escolher a regra de escolher uma letra à frente da real porém usando uma chave de valor 5 Criptografia 17 Entrada A B C D E F X Y Z Saída F G H I J K C D E Para decriptar a palavra recebida devemos conhecer a regra de criptografia e a chave criptográfica Em outro exemplo podemos escolher a regra de escolher uma letra à frente da real porém usando uma chave de valor 12 Criptografia 18 Entrada A B C D E F X Y Z Saída M N O P Q R J K L A regra de gerar um deslocamento shift entre as letras enviadas e as recebidas é uma regra fácil de ser quebrada Criptografia 19 A regra de gerar um deslocamento shift entre as letras enviadas e as recebidas é uma regra fácil de ser quebrada Sistemas de criptografia mais sofisticados utilizam técnicas baseadas em conceitos mais avançados de matemática para codificar os dados Criptografia 20 A regra de gerar um deslocamento shift entre as letras enviadas e as recebidas é uma regra fácil de ser quebrada Sistemas de criptografia mais sofisticados utilizam técnicas baseadas em conceitos mais avançados de matemática para codificar os dados Exemplos curvas elípticas e congruência de números Criptografia 21 Voltando à criptografia baseada em deslocamento das letras correspondentes Máquina de Turing 22 Voltando à criptografia baseada em deslocamento das letras correspondentes As mensagens criptografadas eram armazenadas em fitas semelhantes a listas de símbolos Máquina de Turing 23 Voltando à criptografia baseada em deslocamento das letras correspondentes As mensagens criptografadas eram armazenadas em fitas semelhantes a listas de símbolos Portanto Alan Turing utilizou este modelo de dados como entrada para sua solução matemática Máquina de Turing 24 Máquina de Turing controle a b a b u u Máquina de Turing 26 String de entrada da Máquina de Turing Máquina de Turing 27 String de entrada da Máquina de Turing Símbolo atual acessado pela Máquina de Turing Máquinas de Turing funcionam de forma semelhante a autômatos reconhecendo strings e definindo se estas pertencem ou não a linguagens de símbolos Máquina de Turing 28 Máquinas de Turing funcionam de forma semelhante a autômatos reconhecendo strings e definindo se estas pertencem ou não a linguagens de símbolos Porém Máquinas de Turing e Autômatos apresentam diferenças fundamentais Máquina de Turing 29 A Máquina de Turing pode tanto ler os símbolos da fita como também escrever símbolos na fita Máquina de Turing 30 A Máquina de Turing pode tanto ler os símbolos da fita como também escrever símbolos na fita O elemento de controle que define qual símbolo será acessado pode moverse tanto para a direita quanto para a esquerda Máquina de Turing 31 A Máquina de Turing pode tanto ler os símbolos da fita como também escrever símbolos na fita O elemento de controle que define qual símbolo será acessado pode moverse tanto para a direita quanto para a esquerda O modelo da Máquina de Turing assume uma fita infinita Máquina de Turing 32 A Máquina de Turing pode tanto ler os símbolos da fita como também escrever símbolos na fita O elemento de controle que define qual símbolo será acessado pode moverse tanto para a direita quanto para a esquerda O modelo da Máquina de Turing assume uma fita infinita Os estados de aceitação rejeição definem a entrada de forma imediata Máquina de Turing 33 Para entender o funcionamento de uma Máquina de Turing consideremos uma string w 01 neste caso w é uma string de formada por qualquer sequência de 0s e 1s Máquina de Turing 34 Seja L uma linguagem formada pelo alfabeto de símbolos A 0 1 tal que L ww w 01 Máquina de Turing 35 Seja L uma linguagem formada pelo alfabeto de símbolos A 0 1 tal que L ww w 01 Exemplos de strings que pertencem à linguagem 00 0000 010010 11101110 Máquina de Turing 36 Uma solução para verificarmos se uma string s pertence à linguagem L é Máquina de Turing 37 Uma solução para verificarmos se uma string s pertence à linguagem L é 1 procurar pelo símbolo Máquina de Turing 38 Uma solução para verificarmos se uma string s pertence à linguagem L é 1 procurar pelo símbolo 2 voltar ao primeiro símbolo e comparálo com o primeiro símbolo após o Máquina de Turing 39 Uma solução para verificarmos se uma string s pertence à linguagem L é 1 procurar pelo símbolo 2 voltar ao primeiro símbolo e comparálo com o primeiro símbolo após o 3 voltar ao segundo símbolo e comparálo com o segundo símbolo após o Máquina de Turing 40 Uma solução para verificarmos se uma string s pertence à linguagem L é 1 procurar pelo símbolo 2 voltar ao primeiro símbolo e comparálo com o primeiro símbolo após o 3 voltar ao segundo símbolo e comparálo com o segundo símbolo após o 4 repetir este processo até que todos os símbolos sejam verificados Máquina de Turing 41 Uma solução para verificarmos se uma string s pertence à linguagem L é 1 procurar pelo símbolo 2 voltar ao primeiro símbolo e comparálo com o primeiro símbolo após o 3 voltar ao segundo símbolo e comparálo com o segundo símbolo após o 4 repetir este processo até que todos os símbolos sejam verificados Se qualquer comparação de símbolos verificar símbolos diferentes a string não é aceita Máquina de Turing 42 Uma solução para verificarmos se uma string s pertence à linguagem L é 1 procurar pelo símbolo 2 voltar ao primeiro símbolo e comparálo com o primeiro símbolo após o 3 voltar ao segundo símbolo e comparálo com o segundo símbolo após o 4 repetir este processo até que todos os símbolos sejam verificados Se qualquer comparação de símbolos verificar símbolos diferentes a string não é aceita Se a quantidade de símbolos à esquerda do for diferente da quantidade de símbolos à direita do a string não é aceita Máquina de Turing 43 Uma solução para verificarmos se uma string s pertence à linguagem L é 1 procurar pelo símbolo 2 voltar ao primeiro símbolo e comparálo com o primeiro símbolo após o 3 voltar ao segundo símbolo e comparálo com o segundo símbolo após o 4 repetir este processo até que todos os símbolos sejam verificados Se qualquer comparação de símbolos verificar símbolos diferentes a string não é aceita Se a quantidade de símbolos à esquerda do for diferente da quantidade de símbolos à direita do a string não é aceita Se todos os símbolos forem verificados corretamente e as quantidades de símbolos à direita e à esquerda do a string é aceita Máquina de Turing 44 Exemplo Máquina de Turing 45 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 46 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 47 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 48 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 49 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 50 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 51 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 52 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 53 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 54 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 55 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 56 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 57 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 58 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 59 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 60 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 61 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 62 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 63 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 64 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 65 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 66 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 67 0 0 1 1 0 0 1 1 Controle Exemplo Máquina de Turing 68 0 0 1 1 0 0 1 1 Controle String 00110011 aceita Definição da Máquina de Turing Máquina de Turing 69 Definição da Máquina de Turing Q 𝚺 𝚪 𝛅 q0 qaceitação qrejeição Máquina de Turing 70 Definição da Máquina de Turing Q 𝚺 𝚪 𝛅 q0 qaceitação qrejeição Q conjunto de estados 𝚺 alfabeto sem contar o espaço em branco 𝚪 alfabeto da fita incluindo o espaço em branco 𝛅 Q x 𝚪 Q x 𝚪 x L R função de transição q0 estado inicial qaceitação estados de aceitação qrejeição estados de rejeição Máquina de Turing 71 Definição da Máquina de Turing Q 𝚺 𝚪 𝛅 q0 qaceitação qrejeição Q conjunto de estados 𝚺 alfabeto sem contar o espaço em branco 𝚪 alfabeto da fita incluindo o espaço em branco 𝛅 Q x 𝚪 Q x 𝚪 x L R função de transição q0 estado inicial qaceitação estados de aceitação qrejeição estados de rejeição Máquina de Turing 72 L Left R Right A máquina de Turing fornece três tipos de saída para cada símbolo da fita Máquina de Turing 73 A máquina de Turing fornece três tipos de saída para cada símbolo da fita aceitação Máquina de Turing 74 A máquina de Turing fornece três tipos de saída para cada símbolo da fita aceitação rejeição Máquina de Turing 75 A máquina de Turing fornece três tipos de saída para cada símbolo da fita aceitação rejeição loop Máquina de Turing 76 A máquina de Turing fornece três tipos de saída para cada símbolo da fita aceitação rejeição loop Como os estados de aceitação e de rejeição determinam se a string é ou não pertencente à linguagem a Máquina de Turing está em estado de loop a maior parte do processamento Máquina de Turing 77 Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 78 Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 79 x x x 1 x x 1 1 Controle qazul Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 80 x x x 1 x x 1 1 Controle qazul R Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 81 x x x 1 x x 1 1 Controle qazul Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 82 x x x 1 x x 1 1 Controle qazul Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 83 x x x 1 x x x 1 Controle qvolta Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 84 x x x 1 x x x 1 Controle qvolta L Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 85 x x x 1 x x x 1 Controle qvolta Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 86 x x x 1 x x x 1 Controle qvolta L Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 87 x x x 1 x x x 1 Controle qvolta Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 88 x x x 1 x x x 1 Controle qvolta L Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 89 x x x 1 x x x 1 Controle qvolta Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 90 x x x 1 x x x 1 Controle qvolta L Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 91 x x x 1 x x x 1 Controle qvolta Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 92 x x x 1 x x x 1 Controle qazul Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 93 x x x x x x x 1 Controle qazul Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 94 x x x x x x x 1 Controle qazul R Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 95 x x x x x x x 1 Controle qazul Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 96 x x x x x x x x Controle qazul Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 97 x x x x x x x x Controle qvolta Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 98 x x x x x x x x Controle qvolta Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 99 x x x x x x x x Controle qfim Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 100 x x x x x x x x Controle qfim Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 101 x x x x x x x x Controle qaceita Como dito durante a operação da Máquina de Turing podemos escrever na fita portanto é possível marcar elementos verificados e usar os estados como memória de qual elemento lido Máquina de Turing 102 x x x x x x x x Controle qaceita A string é aceita Teoria da Computação Aula 9 Exercícios sobre LLC GLC e ACP Prof Alex Torquato Souza Carneiro alexcarneirofaculdadeimpactacombr Elabore uma gramática GLC para a linguagem L 0n12n n 0 Exercício 1 2 Elabore uma gramática GLC para a linguagem L 0n12n n 0 Solução Exercício 1 3 Elabore uma gramática GLC para a linguagem L 0n12n n 0 Solução Elementos de uma GLC G V 𝚺 R S Exercício 1 4 Elabore uma gramática GLC para a linguagem L 0n12n n 0 Solução Elementos de uma GLC G V 𝚺 R S V A Exercício 1 5 Elabore uma gramática GLC para a linguagem L 0n12n n 0 Solução Elementos de uma GLC G V 𝚺 R S V A 𝚺 0 1 2 Exercício 1 6 Elabore uma gramática GLC para a linguagem L 0n12n n 0 Solução Elementos de uma GLC G V 𝚺 R S V A 𝚺 0 1 2 R A 0A2 Exercício 1 7 Elabore uma gramática GLC para a linguagem L 0n12n n 0 Solução Elementos de uma GLC G V 𝚺 R S V A 𝚺 0 1 2 R A 0A2 A 1 Exercício 1 8 Elabore uma gramática GLC para a linguagem L 0n12n n 0 Solução Elementos de uma GLC G V 𝚺 R S V A 𝚺 0 1 2 R A 0A2 A 1 S A Exercício 1 9 Dada a GLC G V 𝚺 R S V A 𝚺 0 1 2 R A 0A2 A 1 S A Quantas substituições são necessárias para obtermos a string 000012222 Exercício 2 10 Dada a GLC G V 𝚺 R S V A 𝚺 0 1 2 R A 0A2 A 1 S A Quantas substituições são necessárias para obtermos a string 000012222 Exercício 2 11 Solução Dada a GLC G V 𝚺 R S V A 𝚺 0 1 2 R A 0A2 A 1 S A Quantas substituições são necessárias para obtermos a string 000012222 Exercício 2 12 Solução A Dada a GLC G V 𝚺 R S V A 𝚺 0 1 2 R A 0A2 A 1 S A Quantas substituições são necessárias para obtermos a string 000012222 Exercício 2 13 Solução A 0A2 1ª substituição 0A2 Dada a GLC G V 𝚺 R S V A 𝚺 0 1 2 R A 0A2 A 1 S A Quantas substituições são necessárias para obtermos a string 000012222 Exercício 2 14 Solução A 0A2 1ª substituição 0A2 A 0A2 2ª substituição 00A22 Dada a GLC G V 𝚺 R S V A 𝚺 0 1 2 R A 0A2 A 1 S A Quantas substituições são necessárias para obtermos a string 000012222 Exercício 2 15 Solução A 0A2 1ª substituição 0A2 A 0A2 2ª substituição 00A22 A 0A2 3ª substituição 000A222 Dada a GLC G V 𝚺 R S V A 𝚺 0 1 2 R A 0A2 A 1 S A Quantas substituições são necessárias para obtermos a string 000012222 Exercício 2 16 Solução A 0A2 1ª substituição 0A2 A 0A2 2ª substituição 00A22 A 0A2 3ª substituição 000A222 A 0A2 4ª substituição 0000A2222 Dada a GLC G V 𝚺 R S V A 𝚺 0 1 2 R A 0A2 A 1 S A Quantas substituições são necessárias para obtermos a string 000012222 Exercício 2 17 Solução A 0A2 1ª substituição 0A2 A 0A2 2ª substituição 00A22 A 0A2 3ª substituição 000A222 A 0A2 4ª substituição 0000A2222 A 1 5ª substituição 000012222 Elabore uma autômato com pilha ACP para reconhecer a linguagem L 0n12n n 0 Exercício 3 18 Elabore uma autômato com pilha ACP para reconhecer a linguagem L 0n12n n 0 Solução Exercício 3 19 Elabore uma autômato com pilha ACP para reconhecer a linguagem L 0n12n n 0 Solução Exercício 3 q0 Elabore uma autômato com pilha ACP para reconhecer a linguagem L 0n12n n 0 Solução Exercício 3 21 q0 q1 𝜺 𝜺 Elabore uma autômato com pilha ACP para reconhecer a linguagem L 0n12n n 0 Solução Exercício 3 22 q0 q1 𝜺 𝜺 0 𝜺 0 Elabore uma autômato com pilha ACP para reconhecer a linguagem L 0n12n n 0 Solução Exercício 3 23 q0 q1 q2 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 Elabore uma autômato com pilha ACP para reconhecer a linguagem L 0n12n n 0 Solução Exercício 3 24 q0 q1 q2 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 2 0 𝜺 Elabore uma autômato com pilha ACP para reconhecer a linguagem L 0n12n n 0 Solução Exercício 3 25 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 26 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 27 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 28 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 1 Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 29 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 1 Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 30 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 1 Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 31 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 1 Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 32 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 1 Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 33 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 1 Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 34 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 1 aceita Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 35 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 012 Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 36 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 012 Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 37 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 012 Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 38 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 012 Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 39 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 012 Pilha 0 Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 40 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 012 Pilha 0 Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 41 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 012 Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 42 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 012 Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 43 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 012 aceita Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 44 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 0022 Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 45 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 0022 Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 46 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 0022 Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 47 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 0022 Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 48 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 0022 Pilha 0 Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 49 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 0022 Pilha 0 0 Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 50 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 0022 Pilha 0 0 Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 51 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 0022 rejeitada Pilha 0 0 Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 52 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 001222 Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 53 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 001222 Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 54 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 001222 Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 55 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 001222 Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 56 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 001222 Pilha 0 Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 57 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 001222 Pilha 0 0 Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 58 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 001222 Pilha 0 0 Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 59 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 001222 Pilha 0 Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 60 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 001222 Pilha Utilize o autômato com pilha ACP para verificar se as strings 1 012 0022 001222 pertencem à linguagem L 0n12n n 0 Exercício 4 61 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 𝜺 𝜺 𝜺 𝜺 2 0 𝜺 Solução string 001222 rejeitada Pilha Descreva a linguagem reconhecida pelo AFND abaixo Exercício 5 62 q0 q1 q2 q3 𝜺 b a b a c c c Descreva a linguagem reconhecida pelo AFND abaixo Exercício 5 63 q0 q1 q2 q3 𝜺 b a b a c c c Solução Descreva a linguagem reconhecida pelo AFND abaixo Exercício 5 64 q0 q1 q2 q3 𝜺 b a b a c c c Solução As strings que compõem a linguagem são compostas por Descreva a linguagem reconhecida pelo AFND abaixo Exercício 5 65 q0 q1 q2 q3 𝜺 b a b a c c c Solução As strings que compõem a linguagem são compostas por uma sequência de as Descreva a linguagem reconhecida pelo AFND abaixo Exercício 5 66 q0 q1 q2 q3 𝜺 b a b a c c c Solução As strings que compõem a linguagem são compostas por uma sequência de as ou de bs Descreva a linguagem reconhecida pelo AFND abaixo Exercício 5 67 q0 q1 q2 q3 𝜺 b a b a c c c Solução As strings que compõem a linguagem são compostas por uma sequência de as com ou sem um b no começo ou de bs Descreva a linguagem reconhecida pelo AFND abaixo Exercício 5 68 q0 q1 q2 q3 𝜺 b a b a c c c Solução As strings que compõem a linguagem são compostas por uma sequência de as com ou sem um b no começo ou de bs com um a no começo Descreva a linguagem reconhecida pelo AFND abaixo Exercício 5 69 q0 q1 q2 q3 𝜺 b a b a c c c Solução As strings que compõem a linguagem são compostas por uma sequência de as com ou sem um b no começo ou de bs com um a no começo seguidas por um ou mais cs Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 70 q0 q1 q2 q3 𝜺 b a b a c c c Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 71 q0 q1 q2 q3 𝜺 b a b a c c c Solução Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 72 q0 q1 q2 q3 𝜺 b a b a c c c Solução 𝜺 U b Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 73 q0 q1 q2 q3 𝜺 b a b a c c c Solução 𝜺 U ba Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 74 q0 q1 q2 q3 𝜺 b a b a c c c Solução 𝜺 U ba U a Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 75 q0 q1 q2 q3 𝜺 b a b a c c c Solução 𝜺 U ba U a b Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 76 q0 q1 q2 q3 𝜺 b a b a c c c Solução 𝜺 U ba U a b c Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 77 q0 q1 q2 q3 𝜺 b a b a c c c Solução 𝜺 U ba U a b c c Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 78 q0 q1 q2 q3 𝜺 b a b a c c c Solução V S A B C Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 79 q0 q1 q2 q3 𝜺 b a b a c c c Solução V S A B C 𝚺 a b c Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 80 q0 q1 q2 q3 𝜺 b a b a c c c Solução V S A B C 𝚺 a b c R Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 81 q0 q1 q2 q3 𝜺 b a b a c c c Solução V S A B C 𝚺 a b c R S A S bA S aB Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 82 q0 q1 q2 q3 𝜺 b a b a c c c Solução V S A B C 𝚺 a b c R S A S bA S aB Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 83 q0 q1 q2 q3 𝜺 b a b a c c c Solução V S A B C 𝚺 a b c R S A S bA S aB A aA A C Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 84 q0 q1 q2 q3 𝜺 b a b a c c c Solução V S A B C 𝚺 a b c R S A S bA S aB A aA A C Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 85 q0 q1 q2 q3 𝜺 b a b a c c c Solução V S A B C 𝚺 a b c R S A S bA S aB A aA A C B bB B C Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 86 q0 q1 q2 q3 𝜺 b a b a c c c Solução V S A B C 𝚺 a b c R S A S bA S aB A aA A C B bB B C Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 87 q0 q1 q2 q3 𝜺 b a b a c c c Solução V S A B C 𝚺 a b c R S A S bA S aB A aA A C B bB B C C cC C c Apresente uma expressão regular e uma gramática livre de contexto capazes de gerar a linguagem reconhecida pelo AFND abaixo Exercício 6 88 q0 q1 q2 q3 𝜺 b a b a c c c Solução V S A B C 𝚺 a b c R S A S bA S aB A aA A C B bB B C C cC C c S S Teoria da Computação Aula 8 Autômatos com pilha Prof Alex Torquato Souza Carneiro alexcarneirofaculdadeimpactacombr Agenda Revisão Gramáticas Livres de Contexto GLC Definição Exemplos de autômatos com pilha ACP 2 Revisão Gramáticas Livres de Contexto Gramáticas livres de contexto GLC são modelos capazes de gerar linguagens livres de contexto LLC 3 Revisão Gramáticas Livres de Contexto Gramáticas livres de contexto GLC são modelos capazes de gerar linguagens livres de contexto LLC Essas linguagens apresentam propriedades que incluem as linguagens regulares e também linguagens formadas por strings que possuem símbolos aos pares por exemplo 4 Revisão Gramáticas Livres de Contexto Gramáticas livres de contexto GLC são modelos capazes de gerar linguagens livres de contexto LLC Essas linguagens apresentam propriedades que incluem as linguagens regulares e também linguagens formadas por strings que possuem símbolos aos pares por exemplo 0n1n 5 Revisão Gramáticas Livres de Contexto Gramáticas livres de contexto GLC são modelos capazes de gerar linguagens livres de contexto LLC Essas linguagens apresentam propriedades que incluem as linguagens regulares e também linguagens formadas por strings que possuem símbolos aos pares por exemplo 0n1n xnayn 6 Revisão Gramáticas Livres de Contexto Gramáticas livres de contexto GLC são modelos capazes de gerar linguagens livres de contexto LLC Essas linguagens apresentam propriedades que incluem as linguagens regulares e também linguagens formadas por strings que possuem símbolos aos pares por exemplo 0n1n xnayn 0n1m2m3n 7 Revisão Gramáticas Livres de Contexto Gramáticas livres de contexto GLC são modelos capazes de gerar linguagens livres de contexto LLC Essas linguagens apresentam propriedades que incluem as linguagens regulares e também linguagens formadas por strings que possuem símbolos aos pares por exemplo 0n1n xnayn 0n1m2m3n abnban 8 Revisão Gramáticas Livres de Contexto Utilizando GLC podemos obter modelos capazes de gerar frases coerentes com as regras de idiomas 9 Revisão Gramáticas Livres de Contexto Utilizando GLC podemos obter modelos capazes de gerar frases coerentes com as regras de idiomas V frase sujeito verbo predicado artigo substantivos substantivop verbo 𝚺 o um aluno pegou leu livro R frase sujeito verbo predicado sujeito artigo substantivos predicado artigo substantivop artigo o um substantivos aluno substantivop livro verbo pegou leu S frase 10 Revisão Gramáticas Livres de Contexto Utilizando GLC podemos obter modelos capazes de gerar frases coerentes com as regras de idiomas V frase sujeito verbo predicado artigo substantivos substantivop verbo 𝚺 o um aluno pegou leu livro R frase sujeito verbo predicado sujeito artigo substantivos predicado artigo substantivop artigo o um substantivos aluno substantivop livro verbo pegou leu S frase 11 Frases geradas o aluno leu um livro o aluno pegou um livro um aluno leu um livro um aluno pegou um livro o aluno leu o livro o aluno pegou o livro um aluno leu o livro um aluno pegou o livro Revisão Gramáticas Livres de Contexto Outra possibilidade para o uso de GLC é gerar expressões matemáticas V expr term 𝚺 n R expr termterm termterm termterm termterm term expr n S expr 12 Revisão Gramáticas Livres de Contexto Fazendo uma comparação às linguagens regulares uma GLC corresponde a uma expressão regular 13 Revisão Gramáticas Livres de Contexto Fazendo uma comparação às linguagens regulares uma GLC corresponde a uma expressão regular Ou seja podemos gerar as strings que compõem uma linguagem através de uma GLC 14 Revisão Gramáticas Livres de Contexto Fazendo uma comparação às linguagens regulares uma GLC corresponde a uma expressão regular Ou seja podemos gerar as strings que compõem uma linguagem através de uma GLC Porém também precisamos de um modelo capaz de reconhecer se uma string pertence a uma determinada LLC 15 Definição Um autômato com pilha ACP consiste em um modelo semelhante a um autômato não determinístico AFND que possui um componente extra denominado pilha 16 Definição Um autômato com pilha ACP consiste em um modelo semelhante a um autômato não determinístico AFND que possui um componente extra denominado pilha A pilha permite que o ACP armazene informações ao longo da análise de uma string e assim reconheça LLC 17 Definição Um autômato com pilha ACP consiste em um modelo semelhante a um autômato não determinístico AFND que possui um componente extra denominado pilha A pilha permite que o ACP armazene informações ao longo da análise de uma string e assim reconheça LLC O objetivo de um ACP é reconhecer uma LLC 18 Definição Uma pilha é uma estrutura de dados do tipo FILO FirstIn LastOut ou seja o primeiro elemento inserido será o último a ser removido 19 Definição Uma pilha é uma estrutura de dados do tipo FILO FirstIn LastOut ou seja o primeiro elemento inserido será o último a ser removido 20 AFND s t r i n g x y Definição Uma pilha é uma estrutura de dados do tipo FILO FirstIn LastOut ou seja o primeiro elemento inserido será o último a ser removido 21 AFND s t r i n g x y String verificada Definição Uma pilha é uma estrutura de dados do tipo FILO FirstIn LastOut ou seja o primeiro elemento inserido será o último a ser removido 22 AFND s t r i n g x y String verificada Pilha Definição A pilha é usada pelo ACP para armazenar símbolos lidos da string durante a verificação 23 Definição A pilha é usada pelo ACP para armazenar símbolos lidos da string durante a verificação O ACP pode inserir ou remover símbolos da pilha Isto irá permitir a verificação de símbolos aos pares 24 Definição Um ACP é formalmente definido como uma 6tupla com os seguintes elementos 25 Definição Um ACP é formalmente definido como uma 6tupla com os seguintes elementos Q 𝞢 𝜞 𝛅 q0 F 26 Definição Um ACP é formalmente definido como uma 6tupla com os seguintes elementos Q 𝞢 𝜞 𝛅 q0 F Q conjunto de estados 27 Definição Um ACP é formalmente definido como uma 6tupla com os seguintes elementos Q 𝞢 𝜞 𝛅 q0 F Q conjunto de estados 𝞢 alfabeto das strings reconhecidas pelo ACP 28 Definição Um ACP é formalmente definido como uma 6tupla com os seguintes elementos Q 𝞢 𝜞 𝛅 q0 F Q conjunto de estados 𝞢 alfabeto das strings reconhecidas pelo ACP 𝜞 alfabeto da pilha 29 Definição Um ACP é formalmente definido como uma 6tupla com os seguintes elementos Q 𝞢 𝜞 𝛅 q0 F Q conjunto de estados 𝞢 alfabeto das strings reconhecidas pelo ACP 𝜞 alfabeto da pilha 𝛅 função de transição 30 Definição Um ACP é formalmente definido como uma 6tupla com os seguintes elementos Q 𝞢 𝜞 𝛅 q0 F Q conjunto de estados 𝞢 alfabeto das strings reconhecidas pelo ACP 𝜞 alfabeto da pilha 𝛅 função de transição q0 estado inicial 31 Definição Um ACP é formalmente definido como uma 6tupla com os seguintes elementos Q 𝞢 𝜞 𝛅 q0 F Q conjunto de estados 𝞢 alfabeto das strings reconhecidas pelo ACP 𝜞 alfabeto da pilha 𝛅 função de transição q0 estado inicial F Q conjunto de estados de aceitação 32 Definição A função de transição 𝛅 é definida como 𝛅 Q x 𝞢𝜺 x 𝜞𝜺 𝒫Q x 𝜞𝜺 33 Definição A função de transição 𝛅 é definida como 𝛅 Q x 𝞢𝜺 x 𝜞𝜺 𝒫Q x 𝜞𝜺 em que 𝞢𝜺 𝞢 U 𝜺 e 𝜞𝜺 𝜞 U 𝜺 34 Definição A função de transição 𝛅 é definida como 𝛅 Q x 𝞢𝜺 x 𝜞𝜺 𝒫Q x 𝜞𝜺 em que 𝞢𝜺 𝞢 U 𝜺 e 𝜞𝜺 𝜞 U 𝜺 𝒫Q x 𝜞𝜺 é o conjunto das partes de Q x 𝜞𝜺 35 Definição Com essa definição podemos obter diagramas que representam os ACP 36 Exemplos de autômatos com pilha Com essa definição podemos obter diagramas que representam os ACP Linguagem L 0n1n n 0 37 Exemplos de autômatos com pilha Com essa definição podemos obter diagramas que representam os ACP Linguagem L 0n1n n 0 Exemplos 𝜺 01 0011 000111 00001111 38 Exemplos de autômatos com pilha Com essa definição podemos obter diagramas que representam os ACP Linguagem L 0n1n n 0 39 Exemplos de autômatos com pilha Com essa definição podemos obter diagramas que representam os ACP Linguagem L 0n1n n 0 40 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Exemplos de autômatos com pilha Com essa definição podemos obter diagramas que representam os ACP Linguagem L 0n1n n 0 41 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Q q0 q1 q2 q3 𝞢 0 1 𝜞 0 𝛅 função q0 q0 F q0 q3 Exemplos de autômatos com pilha a b c significa se o autômato recebe o símbolo a o símbolo b no topo da pilha é substituído por c Exemplos de autômatos com pilha a b c significa se o autômato recebe o símbolo a o símbolo b no topo da pilha é substituído por c Se a 𝜺 o autômato faz a transição sem ler qualquer símbolo da string Exemplos de autômatos com pilha a b c significa se o autômato recebe o símbolo a o símbolo b no topo da pilha é substituído por c Se a 𝜺 o autômato faz a transição sem ler qualquer símbolo da string Se b 𝜺 o autômato faz a transição sem ler ou remover qualquer símbolo da pilha Exemplos de autômatos com pilha a b c significa se o autômato recebe o símbolo a o símbolo b no topo da pilha é substituído por c Se a 𝜺 o autômato faz a transição sem ler qualquer símbolo da string Se b 𝜺 o autômato faz a transição sem ler ou remover qualquer símbolo da pilha Se c 𝜺 o autômato não escreve na pilha nesta transição Exemplos de autômatos com pilha a b c significa se o autômato recebe o símbolo a o símbolo b no topo da pilha é substituído por c Se a 𝜺 o autômato faz a transição sem ler qualquer símbolo da string Se b 𝜺 o autômato faz a transição sem ler ou remover qualquer símbolo da pilha Se c 𝜺 o autômato não escreve na pilha nesta transição Apenas insere c na pilha Exemplos de autômatos com pilha a b c significa se o autômato recebe o símbolo a o símbolo b no topo da pilha é substituído por c Se a 𝜺 o autômato faz a transição sem ler qualquer símbolo da string Se b 𝜺 o autômato faz a transição sem ler ou remover qualquer símbolo da pilha Se c 𝜺 o autômato não escreve na pilha nesta transição Apenas insere c na pilha Apenas remove b da pilha Exemplos de autômatos com pilha String 0 1 𝛆 Pilha 0 𝛆 0 𝛆 0 𝛆 q0 q1 q1 q10 q2𝛆 q2 q2𝛆 q3𝛆 q3 Exemplos de autômatos com pilha String 0 1 𝛆 Pilha 0 𝛆 0 𝛆 0 𝛆 q0 q1 q1 q10 q2𝛆 q2 q2𝛆 q3𝛆 q3 Insere um na primeira posição da pilha Exemplos de autômatos com pilha String 0 1 𝛆 Pilha 0 𝛆 0 𝛆 0 𝛆 q0 q1 q1 q10 q2𝛆 q2 q2𝛆 q3𝛆 q3 Insere 0 enquanto o símbolo da string for 0 Exemplos de autômatos com pilha String 0 1 𝛆 Pilha 0 𝛆 0 𝛆 0 𝛆 q0 q1 q1 q10 q2𝛆 q2 q2𝛆 q3𝛆 q3 Remove 1 enquanto o símbolo da string for 1 Exemplos de autômatos com pilha String 0 1 𝛆 Pilha 0 𝛆 0 𝛆 0 𝛆 q0 q1 q1 q10 q2𝛆 q2 q2𝛆 q3𝛆 q3 Muda para o estado q3 e aceita a string se o último elemento restante da pilha for Exemplos de autômatos com pilha Linguagem L 0n1n n 0 53 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha String 0 0 0 0 1 1 1 1 Exemplos de autômatos com pilha Linguagem L 0n1n n 0 54 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha String 0 0 0 0 1 1 1 1 Exemplos de autômatos com pilha Linguagem L 0n1n n 0 55 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha 0 String 0 0 0 0 1 1 1 1 Exemplos de autômatos com pilha Linguagem L 0n1n n 0 56 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha 0 0 String 0 0 0 0 1 1 1 1 Exemplos de autômatos com pilha Linguagem L 0n1n n 0 57 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha 0 0 0 String 0 0 0 0 1 1 1 1 Exemplos de autômatos com pilha Linguagem L 0n1n n 0 58 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha 0 0 0 0 String 0 0 0 0 1 1 1 1 Exemplos de autômatos com pilha Linguagem L 0n1n n 0 59 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha 0 0 0 String 0 0 0 0 1 1 1 1 Exemplos de autômatos com pilha Linguagem L 0n1n n 0 60 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha 0 0 String 0 0 0 0 1 1 1 1 Exemplos de autômatos com pilha Linguagem L 0n1n n 0 61 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha 0 String 0 0 0 0 1 1 1 1 Exemplos de autômatos com pilha Linguagem L 0n1n n 0 62 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha String 0 0 0 0 1 1 1 1 Exemplos de autômatos com pilha Linguagem L 0n1n n 0 63 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha String 0 0 0 0 1 1 1 1 Exemplos de autômatos com pilha Linguagem L 0n1n n 0 64 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha String 0 0 0 0 1 1 1 1 A string é aceita Exemplos de autômatos com pilha Linguagem L 0n1n n 0 65 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha String 0 0 1 Exemplos de autômatos com pilha Linguagem L 0n1n n 0 66 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha String 0 0 1 Exemplos de autômatos com pilha Linguagem L 0n1n n 0 67 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha 0 String 0 0 1 Exemplos de autômatos com pilha Linguagem L 0n1n n 0 68 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha 0 0 String 0 0 1 Exemplos de autômatos com pilha Linguagem L 0n1n n 0 69 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha 0 String 0 0 1 Exemplos de autômatos com pilha Linguagem L 0n1n n 0 70 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 𝜺 1 0 𝜺 Pilha 0 String 0 0 1 A string é rejeitada Exemplos de autômatos com pilha Linguagem L 0n1n2m3m n 0 e m 0 71 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 1 0 𝜺 Pilha 2 𝜺 2 q4 3 2 𝜺 q5 3 2 𝜺 𝜺 𝜺 𝜺 𝜺 Exemplos de autômatos com pilha Linguagem L 0n1n2m3m n 0 e m 0 72 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 1 0 𝜺 Pilha String 0 0 1 1 2 3 2 𝜺 2 q4 3 2 𝜺 q5 3 2 𝜺 𝜺 𝜺 𝜺 𝜺 Exemplos de autômatos com pilha Linguagem L 0n1n2m3m n 0 e m 0 73 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 1 0 𝜺 Pilha String 0 0 1 1 2 3 2 𝜺 2 q4 3 2 𝜺 q5 3 2 𝜺 𝜺 𝜺 𝜺 𝜺 Exemplos de autômatos com pilha Linguagem L 0n1n2m3m n 0 e m 0 74 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 1 0 𝜺 Pilha 0 String 0 0 1 1 2 3 2 𝜺 2 q4 3 2 𝜺 q5 3 2 𝜺 𝜺 𝜺 𝜺 𝜺 Exemplos de autômatos com pilha Linguagem L 0n1n2m3m n 0 e m 0 75 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 1 0 𝜺 Pilha 0 0 String 0 0 1 1 2 3 2 𝜺 2 q4 3 2 𝜺 q5 3 2 𝜺 𝜺 𝜺 𝜺 𝜺 Exemplos de autômatos com pilha Linguagem L 0n1n2m3m n 0 e m 0 76 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 1 0 𝜺 Pilha 0 String 0 0 1 1 2 3 2 𝜺 2 q4 3 2 𝜺 q5 3 2 𝜺 𝜺 𝜺 𝜺 𝜺 Exemplos de autômatos com pilha Linguagem L 0n1n2m3m n 0 e m 0 77 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 1 0 𝜺 Pilha String 0 0 1 1 2 3 2 𝜺 2 q4 3 2 𝜺 q5 3 2 𝜺 𝜺 𝜺 𝜺 𝜺 Exemplos de autômatos com pilha Linguagem L 0n1n2m3m n 0 e m 0 78 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 1 0 𝜺 Pilha String 0 0 1 1 2 3 2 𝜺 2 q4 3 2 𝜺 q5 3 2 𝜺 𝜺 𝜺 𝜺 𝜺 Exemplos de autômatos com pilha Linguagem L 0n1n2m3m n 0 e m 0 79 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 1 0 𝜺 Pilha 2 String 0 0 1 1 2 3 2 𝜺 2 q4 3 2 𝜺 q5 3 2 𝜺 𝜺 𝜺 𝜺 𝜺 Exemplos de autômatos com pilha Linguagem L 0n1n2m3m n 0 e m 0 80 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 1 0 𝜺 Pilha String 0 0 1 1 2 3 2 𝜺 2 q4 3 2 𝜺 q5 3 2 𝜺 𝜺 𝜺 𝜺 𝜺 Exemplos de autômatos com pilha Linguagem L 0n1n2m3m n 0 e m 0 81 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 1 0 𝜺 Pilha String 0 0 1 1 2 3 2 𝜺 2 q4 3 2 𝜺 q5 3 2 𝜺 𝜺 𝜺 𝜺 𝜺 Exemplos de autômatos com pilha Linguagem L 0n1n2m3m n 0 e m 0 82 q0 q1 q2 q3 𝜺 𝜺 0 𝜺 0 1 0 𝜺 𝜺 1 0 𝜺 Pilha String 0 0 1 1 2 3 2 𝜺 2 q4 3 2 𝜺 q5 3 2 𝜺 𝜺 𝜺 A string é aceita 𝜺 𝜺 Teoria da Computação Aula 7 Linguagens livres de contexto Prof Alex Torquato Souza Carneiro alexcarneirofaculdadeimpactacombr Agenda Gramáticas Gramáticas livres de contexto Linguagens livres de contexto Ambiguidade 2 Gramatérias Definição Segundo o dicionário podemos definir uma gramática como Gramáticas 4 Segundo o dicionário podemos definir uma gramática como um conjunto de regras que regem o uso de uma língua especialmente o modo como as unidades desta se combinam entre si para formar unidades maiores Gramáticas 5 Em computação uma gramática pode definir certos elementos que apresentam estruturas recursivas Gramáticas 6 Em computação uma gramática pode definir certos elementos que apresentam estruturas recursivas Exemplos Análise de dados organizados hierarquicamente como arquivos XML ou JSON Gramáticas 7 Em computação uma gramática pode definir certos elementos que apresentam estruturas recursivas Exemplos Análise de dados organizados hierarquicamente como arquivos XML ou JSON Processamento de sentenças como expressões matemáticas Gramáticas 8 Em computação uma gramática pode definir certos elementos que apresentam estruturas recursivas Exemplos Análise de dados organizados hierarquicamente como arquivos XML ou JSON Processamento de sentenças como expressões matemáticas Processamento de linguagem natural Gramáticas 9 Nosso primeiro contato com o conceito de gramática normalmente ocorre nos primeiros anos do ensino básico quando aprendemos as regras de colocação das palavras Gramáticas 10 Nosso primeiro contato com o conceito de gramática normalmente ocorre nos primeiros anos do ensino básico quando aprendemos as regras de colocação das palavras Sujeito verbo predicado Gramáticas 11 Nosso primeiro contato com o conceito de gramática normalmente ocorre nos primeiros anos do ensino básico quando aprendemos as regras de colocação das palavras Sujeito verbo predicado Exemplos Gramáticas 12 Nosso primeiro contato com o conceito de gramática normalmente ocorre nos primeiros anos do ensino básico quando aprendemos as regras de colocação das palavras Sujeito verbo predicado Exemplos Eu estou aqui Gramáticas 13 Nosso primeiro contato com o conceito de gramática normalmente ocorre nos primeiros anos do ensino básico quando aprendemos as regras de colocação das palavras Sujeito verbo predicado Exemplos Eu estou aqui Ele vai embora Gramáticas 14 A estrutura recursiva surge por exemplo quando múltiplas palavras assumem as funções de sujeito verbo ou predicado Professores e alunos pegam ônibus Gramáticas 15 A estrutura recursiva surge por exemplo quando múltiplas palavras assumem as funções de sujeito verbo ou predicado Professores e alunos pegam ônibus Professores e alunos pegam ônibus fretado Gramáticas 16 A estrutura recursiva surge por exemplo quando múltiplas palavras assumem as funções de sujeito verbo ou predicado Professores e alunos pegam ônibus Professores e alunos pegam ônibus fretado Professores e alunos pegam ônibus fretado para vir à aula Gramáticas 17 Definimos então o conceito de gramática livre de contexto Gramáticas livres de contexto 18 Definimos então o conceito de gramática livre de contexto conjunto de variáveis símbolos terminais e regras de substituição que são aplicados recursivamente para a criação de strings Gramáticas livres de contexto 19 Exemplo A 0A A A1 A 𝛆 Gramáticas livres de contexto 20 Exemplo A 0A A A1 A 𝛆 Começamos todas as strings definidas por esta gramática com a variável A Gramáticas livres de contexto 21 Exemplo A 0A A A1 A 𝛆 Começamos todas as strings definidas por esta gramática com a variável A Usamos as regras de substituição para obter as strings Gramáticas livres de contexto 22 Exemplo A 0A A A1 A 𝛆 Começamos todas as strings definidas por esta gramática com a variável A Usamos as regras de substituição para obter as strings Ao final das substituições deveremos ter apenas símbolos terminais Gramáticas livres de contexto 23 Exemplo A 0A A A1 A 𝛆 Gramáticas livres de contexto 24 A Exemplo A 0A A A1 A 𝛆 Gramáticas livres de contexto 25 A A 0A Exemplo A 0A A A1 A 𝛆 Gramáticas livres de contexto 26 A A 0A 0A Exemplo A 0A A A1 A 𝛆 Gramáticas livres de contexto 27 A A 0A 0A A 0A Exemplo A 0A A A1 A 𝛆 Gramáticas livres de contexto 28 A A 0A 0A A 0A 00A Exemplo A 0A A A1 A 𝛆 Gramáticas livres de contexto 29 A A 0A 0A A 0A 00A A A1 Exemplo A 0A A A1 A 𝛆 Gramáticas livres de contexto 30 A A 0A 0A A 0A 00A A A1 00A1 Exemplo A 0A A A1 A 𝛆 Gramáticas livres de contexto 31 A A 0A 0A A 0A 00A A A1 00A1 A A1 Exemplo A 0A A A1 A 𝛆 Gramáticas livres de contexto 32 A A 0A 0A A 0A 00A A A1 00A1 A A1 00A11 Exemplo A 0A A A1 A 𝛆 Gramáticas livres de contexto 33 A A 0A 0A A 0A 00A A A1 00A1 A A1 00A11 A A1 Exemplo A 0A A A1 A 𝛆 Gramáticas livres de contexto 34 A A 0A 0A A 0A 00A A A1 00A1 A A1 00A11 A A1 00A111 Exemplo A 0A A A1 A 𝛆 Gramáticas livres de contexto 35 A A 0A 0A A 0A 00A A A1 00A1 A A1 00A11 A A1 00A111 A 𝛆 Exemplo A 0A A A1 A 𝛆 Gramáticas livres de contexto 36 A A 0A 0A A 0A 00A A A1 00A1 A A1 00A11 A A1 00A111 A 𝛆 00111 Exemplo A 0A A A1 A 𝛆 Gramáticas livres de contexto 37 A A 0A 0A A 0A 00A A A1 00A1 A A1 00A11 A A1 00A111 A 𝛆 00111 00111 é uma string que pertence à linguagem formada pela gramática Exemplo A 0A1 A 𝛆 Gramáticas livres de contexto 38 Exemplo A 0A1 A 𝛆 Gramáticas livres de contexto 39 A Exemplo A 0A1 A 𝛆 Gramáticas livres de contexto 40 A A 0A1 Exemplo A 0A1 A 𝛆 Gramáticas livres de contexto 41 A A 0A1 0A1 Exemplo A 0A1 A 𝛆 Gramáticas livres de contexto 42 A A 0A1 0A1 A 0A1 Exemplo A 0A1 A 𝛆 Gramáticas livres de contexto 43 A A 0A1 0A1 A 0A1 00A11 Exemplo A 0A1 A 𝛆 Gramáticas livres de contexto 44 A A 0A1 0A1 A 0A1 00A11 A 0A1 Exemplo A 0A1 A 𝛆 Gramáticas livres de contexto 45 A A 0A1 0A1 A 0A1 00A11 A 0A1 000A111 Exemplo A 0A1 A 𝛆 Gramáticas livres de contexto 46 A A 0A1 0A1 A 0A1 00A11 A 0A1 000A111 A 𝛆 Exemplo A 0A1 A 𝛆 Gramáticas livres de contexto 47 A A 0A1 0A1 A 0A1 00A11 A 0A1 000A111 A 𝛆 000111 Exemplo A 0A1 A 𝛆 Gramáticas livres de contexto 48 A A 0A1 0A1 A 0A1 00A11 A 0A1 000A111 A 𝛆 000111 000111 é uma string que pertence à linguagem formada pela gramática Exemplo A 0A2 A B B 1 Gramáticas livres de contexto 49 Exemplo A 0A2 A B B 1 Gramáticas livres de contexto 50 A Exemplo A 0A2 A B B 1 Gramáticas livres de contexto 51 A A 0A2 Exemplo A 0A2 A B B 1 Gramáticas livres de contexto 52 A A 0A2 0A2 Exemplo A 0A2 A B B 1 Gramáticas livres de contexto 53 A A 0A2 0A2 A 0A2 Exemplo A 0A2 A B B 1 Gramáticas livres de contexto 54 A A 0A2 0A2 A 0A2 00A22 Exemplo A 0A2 A B B 1 Gramáticas livres de contexto 55 A A 0A2 0A2 A 0A2 00A22 A 0A2 Exemplo A 0A2 A B B 1 Gramáticas livres de contexto 56 A A 0A2 0A2 A 0A2 00A22 A 0A2 000A222 Exemplo A 0A2 A B B 1 Gramáticas livres de contexto 57 A A 0A2 0A2 A 0A2 00A22 A 0A2 000A222 A B Exemplo A 0A2 A B B 1 Gramáticas livres de contexto 58 A A 0A2 0A2 A 0A2 00A22 A 0A2 000A222 A B 000B222 Exemplo A 0A2 A B B 1 Gramáticas livres de contexto 59 A A 0A2 0A2 A 0A2 00A22 A 0A2 000A222 A B 000B222 B 1 Exemplo A 0A2 A B B 1 Gramáticas livres de contexto 60 A A 0A2 0A2 A 0A2 00A22 A 0A2 000A222 A B 000B222 B 1 0001222 Exemplo A 0A2 A B B 1 Gramáticas livres de contexto 61 A A 0A2 0A2 A 0A2 00A22 A 0A2 000A222 A B 000B222 B 1 0001222 0001222 é uma string que pertence à linguagem formada pela gramática Matematicamente definimos uma gramática livre de contexto G como uma 4tupla V 𝚺 R S em que Gramáticas livres de contexto 62 Matematicamente definimos uma gramática livre de contexto G como uma 4tupla V 𝚺 R S em que V é um conjunto finito composto pelas variáveis Gramáticas livres de contexto 63 Matematicamente definimos uma gramática livre de contexto G como uma 4tupla V 𝚺 R S em que V é um conjunto finito composto pelas variáveis 𝚺 é um conjunto finito composto pelos símbolos terminais alfabeto Gramáticas livres de contexto 64 Matematicamente definimos uma gramática livre de contexto G como uma 4tupla V 𝚺 R S em que V é um conjunto finito composto pelas variáveis 𝚺 é um conjunto finito composto pelos símbolos terminais alfabeto R é o conjunto de regras de substituição Gramáticas livres de contexto 65 Matematicamente definimos uma gramática livre de contexto G como uma 4tupla V 𝚺 R S em que V é um conjunto finito composto pelas variáveis 𝚺 é um conjunto finito composto pelos símbolos terminais alfabeto R é o conjunto de regras de substituição S S V é a variável inicial da gramática Gramáticas livres de contexto 66 Como dito gramáticas são úteis para tratarmos de elementos que apresentam estruturas hierárquicas Gramáticas livres de contexto 67 Como dito gramáticas são úteis para tratarmos de elementos que apresentam estruturas hierárquicas Vamos montar uma gramática capaz de escrever frases Gramáticas livres de contexto 68 Como dito gramáticas são úteis para tratarmos de elementos que apresentam estruturas hierárquicas Vamos montar uma gramática capaz de escrever frases Gramáticas livres de contexto 69 Frase Como dito gramáticas são úteis para tratarmos de elementos que apresentam estruturas hierárquicas Vamos montar uma gramática capaz de escrever frases Gramáticas livres de contexto 70 Frase Sujeito Predicado Verbo Como dito gramáticas são úteis para tratarmos de elementos que apresentam estruturas hierárquicas Vamos montar uma gramática capaz de escrever frases Gramáticas livres de contexto 71 Frase Sujeito Predicado Verbo Artigo Substantivo Como dito gramáticas são úteis para tratarmos de elementos que apresentam estruturas hierárquicas Vamos montar uma gramática capaz de escrever frases Gramáticas livres de contexto 72 Frase Sujeito Predicado Verbo Artigo Substantivo Artigo Substantivo Consideremos a gramática G V frase sujeito verbo predicado artigo substantivos substantivop verbo Gramáticas livres de contexto 73 Consideremos a gramática G V frase sujeito verbo predicado artigo substantivos substantivop verbo 𝚺 o um aluno pegou leu livro Gramáticas livres de contexto 74 Consideremos a gramática G V frase sujeito verbo predicado artigo substantivos substantivop verbo 𝚺 o um aluno pegou leu livro R frase sujeito verbo predicado sujeito artigo substantivos predicado artigo substantivop artigo o um substantivos aluno substantivop livro verbo pegou leu Gramáticas livres de contexto 75 Consideremos a gramática G V frase sujeito verbo predicado artigo substantivos substantivop verbo 𝚺 o um aluno pegou leu livro R frase sujeito verbo predicado sujeito artigo substantivos predicado artigo substantivop artigo o um substantivos aluno substantivop livro verbo pegou leu S frase Gramáticas livres de contexto 76 frase Gramáticas livres de contexto 77 frase frase sujeito verbo predicado Gramáticas livres de contexto 78 frase frase sujeito verbo predicado sujeito verbo predicado Gramáticas livres de contexto 79 frase frase sujeito verbo predicado sujeito verbo predicado sujeito artigo substantivos Gramáticas livres de contexto 80 frase frase sujeito verbo predicado sujeito verbo predicado sujeito artigo substantivos artigo substantivos verbo predicado Gramáticas livres de contexto 81 frase frase sujeito verbo predicado sujeito verbo predicado sujeito artigo substantivos artigo substantivos verbo predicado predicado artigo substantivop Gramáticas livres de contexto 82 frase frase sujeito verbo predicado sujeito verbo predicado sujeito artigo substantivos artigo substantivos verbo predicado predicado artigo substantivop artigo substantivos verbo artigo substantivop Gramáticas livres de contexto 83 frase frase sujeito verbo predicado sujeito verbo predicado sujeito artigo substantivos artigo substantivos verbo predicado predicado artigo substantivop artigo substantivos verbo artigo substantivop artigo o Gramáticas livres de contexto 84 frase frase sujeito verbo predicado sujeito verbo predicado sujeito artigo substantivos artigo substantivos verbo predicado predicado artigo substantivop artigo substantivos verbo artigo substantivop artigo o o substantivos verbo artigo substantivop Gramáticas livres de contexto 85 frase frase sujeito verbo predicado sujeito verbo predicado sujeito artigo substantivos artigo substantivos verbo predicado predicado artigo substantivop artigo substantivos verbo artigo substantivop artigo o o substantivos verbo artigo substantivop substantivos aluno Gramáticas livres de contexto 86 frase frase sujeito verbo predicado sujeito verbo predicado sujeito artigo substantivos artigo substantivos verbo predicado predicado artigo substantivop artigo substantivos verbo artigo substantivop artigo o o substantivos verbo artigo substantivop substantivos aluno o aluno verbo artigo substantivop Gramáticas livres de contexto 87 frase frase sujeito verbo predicado sujeito verbo predicado sujeito artigo substantivos artigo substantivos verbo predicado predicado artigo substantivop artigo substantivos verbo artigo substantivop artigo o o substantivos verbo artigo substantivop substantivos aluno o aluno verbo artigo substantivop verbo leu Gramáticas livres de contexto 88 frase frase sujeito verbo predicado sujeito verbo predicado sujeito artigo substantivos artigo substantivos verbo predicado predicado artigo substantivop artigo substantivos verbo artigo substantivop artigo o o substantivos verbo artigo substantivop substantivos aluno o aluno verbo artigo substantivop verbo leu o aluno leu artigo substantivop Gramáticas livres de contexto 89 frase frase sujeito verbo predicado sujeito verbo predicado sujeito artigo substantivos artigo substantivos verbo predicado predicado artigo substantivop artigo substantivos verbo artigo substantivop artigo o o substantivos verbo artigo substantivop substantivos aluno o aluno verbo artigo substantivop verbo leu o aluno leu artigo substantivop artigo um Gramáticas livres de contexto 90 frase frase sujeito verbo predicado sujeito verbo predicado sujeito artigo substantivos artigo substantivos verbo predicado predicado artigo substantivop artigo substantivos verbo artigo substantivop artigo o o substantivos verbo artigo substantivop substantivos aluno o aluno verbo artigo substantivop verbo leu o aluno leu artigo substantivop artigo um o aluno leu um substantivop Gramáticas livres de contexto 91 frase frase sujeito verbo predicado sujeito verbo predicado sujeito artigo substantivos artigo substantivos verbo predicado predicado artigo substantivop artigo substantivos verbo artigo substantivop artigo o o substantivos verbo artigo substantivop substantivos aluno o aluno verbo artigo substantivop verbo leu o aluno leu artigo substantivop artigo um o aluno leu um substantivop substantivop livro Gramáticas livres de contexto 92 frase frase sujeito verbo predicado sujeito verbo predicado sujeito artigo substantivos artigo substantivos verbo predicado predicado artigo substantivop artigo substantivos verbo artigo substantivop artigo o o substantivos verbo artigo substantivop substantivos aluno o aluno verbo artigo substantivop verbo leu o aluno leu artigo substantivop artigo um o aluno leu um substantivop substantivop livro o aluno leu um livro Gramáticas livres de contexto 93 frase frase sujeito verbo predicado sujeito verbo predicado sujeito artigo substantivos artigo substantivos verbo predicado predicado artigo substantivop artigo substantivos verbo artigo substantivop artigo o o substantivos verbo artigo substantivop substantivos aluno o aluno verbo artigo substantivop verbo leu o aluno leu artigo substantivop artigo um o aluno leu um substantivop substantivop livro o aluno leu um livro Quais as possibilidades Gramáticas livres de contexto 94 frase frase sujeito verbo predicado sujeito verbo predicado sujeito artigo substantivos artigo substantivos verbo predicado predicado artigo substantivop artigo substantivos verbo artigo substantivop artigo o o substantivos verbo artigo substantivop substantivos aluno o aluno verbo artigo substantivop verbo leu o aluno leu artigo substantivop artigo um o aluno leu um substantivop substantivop livro o aluno leu um livro Quais as possibilidades o aluno leu um livro o aluno pegou um livro um aluno leu um livro um aluno pegou um livro um aluno leu o livro um aluno pegou o livro o aluno leu o livro o aluno pegou o livro Gramáticas livres de contexto 95 Todas as linguagens que podem ser geradas por gramáticas livres de contexto são denominadas linguagens livres de contexto Linguagens livres de contexto 96 Todas as linguagens que podem ser geradas por gramáticas livres de contexto são denominadas linguagens livres de contexto Segundo Chomsky podemos observar as seguintes relações Linguagens livres de contexto 97 Todas as linguagens que podem ser geradas por gramáticas livres de contexto são denominadas linguagens livres de contexto Segundo Chomsky podemos observar as seguintes relações Linguagens livres de contexto 98 Linguagens regulares Todas as linguagens que podem ser geradas por gramáticas livres de contexto são denominadas linguagens livres de contexto Segundo Chomsky podemos observar as seguintes relações Linguagens livres de contexto 99 Linguagens livres de contexto Linguagens regulares Todas as linguagens que podem ser geradas por gramáticas livres de contexto são denominadas linguagens livres de contexto Segundo Chomsky podemos observar as seguintes relações Linguagens livres de contexto 100 Linguagens sensíveis ao contexto Linguagens livres de contexto Linguagens regulares Todas as linguagens que podem ser geradas por gramáticas livres de contexto são denominadas linguagens livres de contexto Segundo Chomsky podemos observar as seguintes relações Linguagens livres de contexto 101 Linguagens enumeráveis recursivamente Linguagens sensíveis ao contexto Linguagens livres de contexto Linguagens regulares Todas as linguagens que podem ser geradas por uma gramática livre de contexto são denominadas linguagens livres de contexto Segundo Chomsky podemos observar as seguintes relações Linguagens livres de contexto 102 Linguagens enumeráveis recursivamente Linguagens sensíveis ao contexto Linguagens livres de contexto Linguagens regulares Estamos indo até aqui Algumas gramáticas podem gerar strings iguais seguindo diferentes substituições isto pode impactar certas aplicações Ambiguidade 103 Exemplo um gerador de expressões aritméticas Ambiguidade 104 Exemplo um gerador de expressões aritméticas G V expr 𝚺 n x R expr exprexpr exprxexpr expr n S expr Ambiguidade 105 A gramática G pode gerar a expressão n n x n de duas formas expr expr exprexpr exprexpr expr exprxexpr exprexprxexprexpr n 3 vezes n n x n Ambiguidade 106 A gramática G pode gerar a expressão n n x n de duas formas expr expr exprxexpr exprxexpr expr exprexpr exprexprxexpr expr n 3 vezes n n x n Ambiguidade 107 Uma das formas de tratar a ambiguidade é fixar uma regra de substituição Usualmente definimos que a variável mais à esquerda é sempre a prioritária para sofrer a substituição Ambiguidade 108 Uma das formas de tratar a ambiguidade é fixar uma regra de substituição Usualmente definimos que a variável mais à esquerda é sempre a prioritária para sofrer a substituição Porém ainda assim é possível que tenhamos ambiguidades na geração de linguagens através de gramáticas livres de contexto Ambiguidade 109 Teoria da Computação Aula 6 Autômatos Finitos NãoDeterminísticos AFND Prof Alex Torquato Souza Carneiro alexcarneirofaculdadeimpactacombr Agenda Autômatos Finitos NãoDeterminísticos Definição Diferenças com AFDs Exemplos 2 Quando um autômato está recebendo elementos sabemos seu estado atual e caso este receba um estímulo sabemos qual o próximo estado do sistema para qualquer que seja o estímulo Definição de AFD 3 Quando um autômato está recebendo elementos sabemos seu estado atual e caso este receba um estímulo sabemos qual o próximo estado do sistema para qualquer que seja o estímulo Isto define um autômato determinístico Definição de AFD 4 Quando um autômato está recebendo elementos sabemos seu estado atual e caso este receba um estímulo sabemos qual o próximo estado do sistema para qualquer que seja o estímulo Isto define um autômato determinístico Definição de AFD 5 q1 q2 q3 q4q4 0 1 0 0 1 1 01 Quando um autômato está recebendo elementos sabemos seu estado atual e caso este receba um estímulo sabemos qual o próximo estado do sistema para qualquer que seja o estímulo Isto define um autômato determinístico Definição de AFD 6 q1 q2 q3 q4 0 1 0 0 1 1 01 01 011 0111 Quando um autômato está recebendo elementos sabemos seu estado atual e caso este receba um estímulo sabemos qual o próximo estado do sistema para qualquer que seja o estímulo Isto define um autômato determinístico Definição de AFD 7 q1 q2 q3 q4 0 1 0 0 1 1 01 01 011 0111 011 Em um autômato não determinístico este comportamento não é observável ou seja considerado que um autômato está em um estado caso ele receba um estímulo podemos ir para diferentes estados possíveis Definição de AFND 8 Em um autômato não determinístico este comportamento não é observável ou seja considerado que um autômato está em um estado caso ele receba um estímulo podemos ir para diferentes estados possíveis Definição de AFND 9 q0 q1 q2 q3 01 1 0𝛆 1 01 Em um autômato não determinístico este comportamento não é observável ou seja considerado que um autômato está em um estado caso ele receba um estímulo podemos ir para diferentes estados possíveis Definição de AFND 10 q0 q1 q2 q3 01 1 0𝛆 1 01 Entrada 0110100 Para cada estado de um autômato nãodeterminístico podemos ter 0 1 2 saídas para outros estados inclusive com o mesmo estímulo Definição de AFND 11 qp qn b Para cada estado de um autômato nãodeterminístico podemos ter 0 1 2 saídas para outros estados inclusive com o mesmo estímulo Definição de AFND 12 qp qp1 a qn b Para cada estado de um autômato nãodeterminístico podemos ter 0 1 2 saídas para outros estados inclusive com o mesmo estímulo Definição de AFND 13 qp qp1 a qp2 a qn b Para cada estado de um autômato nãodeterminístico podemos ter 0 1 2 saídas para outros estados inclusive com o mesmo estímulo Definição de AFND 14 qp qp1 a qp2 a qp3 a qn b Para cada estado de um autômato nãodeterminístico podemos ter 0 1 2 saídas para outros estados inclusive com o mesmo estímulo Definição de AFND 15 qp qp1 a qp2 a qp3 a qn b Para cada estado de um autômato nãodeterminístico podemos ter 0 1 2 saídas para outros estados inclusive com o mesmo estímulo Definição de AFND 16 qp qp1 a qp2 a qp3 a qn b Como o autômato funciona nestes casos Quando um autômato nãodeterminístico está em um estado e recebe um estímulo que o leva para diferentes estados o autômato cria uma nova instância de si de modo que cada instância do autômato assume um dos estados possíveis Definição de AFND 17 Quando um autômato nãodeterminístico está em um estado e recebe um estímulo que o leva para diferentes estados o autômato cria uma nova instância de si de modo que cada instância do autômato assume um dos estados possíveis Definição de AFND 18 qp qp1 a qp2 a qn b Quando um autômato nãodeterminístico está em um estado e recebe um estímulo que o leva para diferentes estados o autômato cria uma nova instância de si de modo que cada instância do autômato assume um dos estados possíveis Definição de AFND 19 qp qp1 a qp2 a qn b Próxima entrada a Quando um autômato nãodeterminístico está em um estado e recebe um estímulo que o leva para diferentes estados o autômato cria uma nova instância de si de modo que cada instância do autômato assume um dos estados possíveis Definição de AFND 20 qp qp1 a qp2 a qn b Próxima entrada a 2 possíveis estados Quando um autômato nãodeterminístico está em um estado e recebe um estímulo que o leva para diferentes estados o autômato cria uma nova instância de si de modo que cada instância do autômato assume um dos estados possíveis Definição de AFND 21 qp qp1 a qp2 a qn b qp qp1 a qp2 a qn b Quando um autômato nãodeterminístico está em um estado e recebe um estímulo que o leva para diferentes estados o autômato cria uma nova instância de si de modo que cada instância do autômato assume um dos estados possíveis Definição de AFND 22 qp qp1 a qp2 a qn b qp qp1 a qp2 a qn b Quando um autômato nãodeterminístico está em um estado e recebe um estímulo que o leva para diferentes estados o autômato cria uma nova instância de si de modo que cada instância do autômato assume um dos estados possíveis Definição de AFND 23 qp qp1 a qp2 a qn b qp qp1 a qp2 a qn b Quando um autômato nãodeterminístico está em um estado e recebe um estímulo que o leva para diferentes estados o autômato cria uma nova instância de si de modo que cada instância do autômato assume um dos estados possíveis Uma vez que temos múltiplas instâncias do mesmo autômato estas são executadas em paralelo Definição de AFND 24 Se estivermos em um estado para o qual não há saída quando o autômato recebe um determinado estímulo a instância do autômato é finalizada Definição de AFND 25 Se estivermos em um estado para o qual não há saída quando o autômato recebe um determinado estímulo a instância do autômato é finalizada Definição de AFND 26 q0 q1 q2 q3 a a b a Se estivermos em um estado para o qual não há saída quando o autômato recebe um determinado estímulo a instância do autômato é finalizada Definição de AFND 27 q0 q1 q2 q3 a a b a Próxima entrada a Se estivermos em um estado para o qual não há saída quando o autômato recebe um determinado estímulo a instância do autômato é finalizada Definição de AFND 28 q0 q1 q2 q3 a a b a Próxima entrada a q0 q1 q2 q3 a a b a Se estivermos em um estado para o qual não há saída quando o autômato recebe um determinado estímulo a instância do autômato é finalizada Definição de AFND 29 q0 q1 q2 q3 a a b a q0 q1 q2 q3 a a b a Se estivermos em um estado para o qual não há saída quando o autômato recebe um determinado estímulo a instância do autômato é finalizada Definição de AFND 30 q0 q1 q2 q3 a a b a q0 q1 q2 q3 a a b a Próxima entrada a Se estivermos em um estado para o qual não há saída quando o autômato recebe um determinado estímulo a instância do autômato é finalizada Definição de AFND 31 q0 q1 q2 q3 a a b a q0 q1 q2 q3 a a b a Próxima entrada a Se estivermos em um estado para o qual não há saída quando o autômato recebe um determinado estímulo a instância do autômato é finalizada Definição de AFND 32 q0 q1 q2 q3 a a b a q0 q1 q2 q3 a a b a Próxima entrada a Se estivermos em um estado para o qual não há saída quando o autômato recebe um determinado estímulo a instância do autômato é finalizada Definição de AFND 33 q0 q1 q2 q3 a a b a Se estivermos em um estado para o qual não há saída quando o autômato recebe um determinado estímulo a instância do autômato é finalizada Uma string é reconhecida por um autômato nãodeterminístico se qualquer uma de suas instâncias estiver em um estado terminal após o último símbolo da string Definição de AFND 34 Se um autômato não determinístico apresentar saídas para 𝛆 então neste ponto o autômato cria tantas instâncias quantas sejam as saídas para 𝛆 Definição de AFND 35 qp qp2 𝛆 qp3 𝛆 qp1 𝛆 Se um autômato não determinístico apresentar saídas para 𝛆 então neste ponto o autômato cria tantas instâncias quantas sejam as saídas para 𝛆 Definição de AFND 36 qp qp2 𝛆 qp3 𝛆 qp1 𝛆 Se um autômato não determinístico apresentar saídas para 𝛆 então neste ponto o autômato cria tantas instâncias quantas sejam as saídas para 𝛆 Definição de AFND 37 qp qp2 𝛆 qp3 𝛆 qp1 𝛆 qp qp2 𝛆 qp3 𝛆 qp1 𝛆 qp qp2 𝛆 qp3 𝛆 qp1 𝛆 Se um autômato não determinístico apresentar saídas para 𝛆 então neste ponto o autômato cria tantas instâncias quantas sejam as saídas para 𝛆 Definição de AFND 38 qp qp2 𝛆 qp3 𝛆 qp1 𝛆 qp qp2 𝛆 qp3 𝛆 qp1 𝛆 qp qp2 𝛆 qp3 𝛆 qp1 𝛆 Se um autômato não determinístico apresentar saídas para 𝛆 então neste ponto o autômato cria tantas instâncias quantas sejam as saídas para 𝛆 Definição de AFND 39 qp qp2 𝛆 qp3 𝛆 qp1 𝛆 qp qp2 𝛆 qp3 𝛆 qp1 𝛆 qp qp2 𝛆 qp3 𝛆 qp1 𝛆 Se um autômato não determinístico apresentar saídas para 𝛆 então neste ponto o autômato cria tantas instâncias quantas sejam as saídas para 𝛆 Definição de AFND 40 qp qp2 𝛆 qp3 𝛆 qp1 𝛆 qp qp2 𝛆 qp3 𝛆 qp1 𝛆 qp qp2 𝛆 qp3 𝛆 qp1 𝛆 Uma das formas mais usuais de modelarmos o comportamento de um autômato nãodeterminístico é como uma árvore Definição de AFND 41 Uma das formas mais usuais de modelarmos o comportamento de um autômato nãodeterminístico é como uma árvore Sempre que um autômato recebe um estímulo avançamos para o próximo nível da árvore Definição de AFND 42 Uma das formas mais usuais de modelarmos o comportamento de um autômato nãodeterminístico é como uma árvore Sempre que um autômato recebe um estímulo avançamos para o próximo nível da árvore Caso o autômato tenha múltiplas saídas teremos múltiplos nós na árvore Definição de AFND 43 Definição de AFND Definição de AFND Definição de AFND 46 Autômato Autômato a Definição de AFND 47 Autômato Autômato a b Definição de AFND 48 Autômato Autômato a b b b Definição de AFND 49 Autômato Autômato Autômato Autômato Autômato a b b b Definição de AFND 50 Autômato Autômato Autômato Autômato Autômato a b b b a a a Definição de AFND 51 Autômato Autômato Autômato Autômato Autômato a b b b a a a a Definição de AFND 52 Autômato Autômato Autômato Autômato Autômato Autômato Autômato Autômato a b b b a a a a Podemos entender os autômatos nãodeterminísticos como uma extensão dos autômatos determinísticos Comparação entre autômatos finitos determinísticos e nãodeterminísticos 53 Podemos entender os autômatos nãodeterminísticos como uma extensão dos autômatos determinísticos Esta conclusão pode ser observada por exemplo se analisarmos o autômato determinístico com o modelo de árvore Comparação entre autômatos finitos determinísticos e nãodeterminísticos 54 Podemos entender os autômatos nãodeterminísticos como uma extensão dos autômatos determinísticos Esta conclusão pode ser observada por exemplo se analisarmos o autômato determinístico com o modelo de árvore Para o autômato determinístico a árvore se torna uma sequência linear Comparação entre autômatos finitos determinísticos e nãodeterminísticos 55 Comparação entre autômatos finitos determinísticos e nãodeterminísticos 56 Autômato Autômato Autômato Autômato a b a Em termos matemáticos um autômato finito determinístico é definido pelos elementos Alfabeto Conjunto de estados Função de transição Estado inicial Conjunto de estados terminais Comparação entre autômatos finitos determinísticos e nãodeterminísticos 57 Em termos matemáticos um autômato finito determinístico é definido pelos elementos Alfabeto Conjunto de estados Função de transição Estado inicial Conjunto de estados terminais Onde a função de transição é definida como δ Q x 𝛴 Q Comparação entre autômatos finitos determinísticos e nãodeterminísticos 58 A definição de autômato nãodeterminístico compreende os mesmos elementos porém definimos a função de transição em um outro conjunto imagem δ Q x 𝛴 𝒫 Q Comparação entre autômatos finitos determinísticos e nãodeterminísticos 59 A definição de autômato nãodeterminístico compreende os mesmos elementos porém definimos a função de transição em um outro conjunto imagem δ Q x 𝛴 𝒫 Q Em que 𝒫 Q é o conjunto das partes de Q Comparação entre autômatos finitos determinísticos e nãodeterminísticos 60 Definimos o conjunto das partes de um conjunto A como 𝒫 A Revisão conjunto das partes 61 Definimos o conjunto das partes de um conjunto A como 𝒫 A O conjunto das partes de A corresponde ao conjunto em que seus elementos são os subconjuntos de A Revisão conjunto das partes 62 Definimos o conjunto das partes de um conjunto A como 𝒫 A O conjunto das partes de A corresponde ao conjunto em que seus elementos são os subconjuntos de A Exemplo A 01 então 𝒫 A Revisão conjunto das partes 63 Definimos o conjunto das partes de um conjunto A como 𝒫 A O conjunto das partes de A corresponde ao conjunto em que seus elementos são os subconjuntos de A Exemplo A 01 então 𝒫 A 0110 Revisão conjunto das partes 64 Definimos o conjunto das partes de um conjunto A como 𝒫A O conjunto das partes de A corresponde ao conjunto em que seus elementos são os subconjuntos de A Exemplo A 01 então 𝒫 A 0110 B abc então 𝒫 B Revisão conjunto das partes 65 Definimos o conjunto das partes de um conjunto A como 𝒫 A O conjunto das partes de A corresponde ao conjunto em que seus elementos são os subconjuntos de A Exemplo A 01 então 𝒫 A 0110 B abc então 𝒫 B abcabacbcabc Revisão conjunto das partes 66 Se um conjunto A tem N elementos quantos elementos teremos em 𝒫 A Revisão conjunto das partes 67 Se um conjunto A tem N elementos quantos elementos teremos em 𝒫 A Resposta 2N Revisão conjunto das partes 68 Antes dos exemplos vamos pensar autômatos nãodeterminísticos podem fazer algo que autômatos determinísticos não são capazes Exemplos 69 Mostre um autômato que reconhece a linguagem gerada pela expressão regular a U e U i U o U ua z Exemplos 70 Mostre um autômato que reconhece a linguagem gerada pela expressão regular a U e U i U o U ua z Amostras da linguagem abc evsv ifeee o uh Exemplos 71 Mostre um autômato que reconhece a linguagem gerada pela expressão regular a U e U i U o U ua z Exemplos 72 q0 q1 aeiou bcdfghj klmnp qrstvw xyz abcdef ghijklm nopqrs tuvwxy z q2 abcdef ghijklm nopqrs tuvwxy z AFD Mostre um autômato que reconhece a linguagem gerada pela expressão regular a U e U i U o U ua z Exemplos 73 q0 q1 aeiou abcdef ghijklm nopqrs tuvwxy z AFND Mostre um autômato que reconhece a linguagem gerada pela expressão regular 0 U 10 Exemplos 74 Mostre um autômato que reconhece a linguagem gerada pela expressão regular 0 U 10 Exemplos 75 q0 q1 q2 0 1 0 1 0 1 Mostre um autômato que reconhece a linguagem gerada pela expressão regular 0 U 10 Exemplos 76 q0 q1 0 01 Apresente um AFD e um AFND que reconheçam a linguagem gerada pela expressão regular ab U cab U c Exemplos 77 Teoria da Computação Aula 5 Aplicações de Expressões Regulares Prof Alex Torquato Souza Carneiro alexcarneirofaculdadeimpactacombr Agenda Exemplos de aplicações de expressões regulares Biblioteca RE Regular Expressions Exercícios 2 Expressões regulares são especialmente úteis quando precisamos verificar se uma string apresenta um padrão conhecido Exemplos de aplicações 3 Expressões regulares são especialmente úteis quando precisamos verificar se uma string apresenta um padrão conhecido Datas ddmmaaaa ddmmaaaa aaaammdd dd de mmm de aaaa Exemplos de aplicações 4 Expressões regulares são especialmente úteis quando precisamos verificar se uma string apresenta um padrão conhecido Datas ddmmaaaa 13052000 07091995 ddmmaaaa 12102001 04071990 aaaammdd 19920120 20040228 dd de mmm de aaaa 16 de maio de 2011 Exemplos de aplicações 5 Expressões regulares são especialmente úteis quando precisamos verificar se uma string apresenta um padrão conhecido CPF xxxxxxxxxxx xxxxxxxxxxx Exemplos de aplicações 6 Expressões regulares são especialmente úteis quando precisamos verificar se uma string apresenta um padrão conhecido CPF xxxxxxxxxxx 68134527380 xxxxxxxxxxx 68134527380 Exemplos de aplicações 7 Expressões regulares são especialmente úteis quando precisamos verificar se uma string apresenta um padrão conhecido CEP xxxxxxxx xxxxxxxx Exemplos de aplicações 8 Expressões regulares são especialmente úteis quando precisamos verificar se uma string apresenta um padrão conhecido CEP xxxxxxxx 60123000 xxxxxxxx 05789001 Exemplos de aplicações 9 Expressões regulares são especialmente úteis quando precisamos verificar se uma string apresenta um padrão conhecido Placas de carro nnnxxxx Exemplos de aplicações 10 Expressões regulares são especialmente úteis quando precisamos verificar se uma string apresenta um padrão conhecido Placas de carro nnnxxxx GXX3210 Exemplos de aplicações 11 Existem várias aplicações em que precisamos identificar padrões específicos em strings porém iremos trabalhar com os exemplos apresentados Exemplos de aplicações 12 É comum encontrarmos bibliotecas para linguagens de programação que implementam os conceitos que estudamos de linguagens regulares e de expressões regulares Biblioteca RE 13 É comum encontrarmos bibliotecas para linguagens de programação que implementam os conceitos que estudamos de linguagens regulares e de expressões regulares A biblioteca re Regular Expressions disponível na linguagem Python é uma dessas Biblioteca RE 14 A biblioteca re dispõe de vários recursos alguns dos quais extrapolam o escopo de nossa disciplina porém exploraremos a função fullmatchpattern teststring que verifica se uma string atende um padrão especificado Biblioteca RE 15 A biblioteca re dispõe de vários recursos alguns dos quais extrapolam o escopo de nossa disciplina porém exploraremos a função fullmatchpattern teststring que verifica se uma string atende um padrão especificado Caso o padrão não seja atendido a função retorna None Caso o padrão seja atendido a função retorna um objeto Match válido Biblioteca RE 16 A biblioteca re implementa as operações regulares união concatenação e estrela União operador pipe Concatenação não há operador Estrela operador asterisco Biblioteca RE 17 A biblioteca re implementa as operações regulares união concatenação e estrela União operador pipe Concatenação não há operador Estrela operador asterisco Exemplo abc concatenado com cda abccda Biblioteca RE 18 A biblioteca re implementa as operações regulares união concatenação e estrela União operador pipe Concatenação não há operador Estrela operador asterisco Exemplo abc concatenado com cda U cbe abccdacbe Biblioteca RE 19 A biblioteca re implementa as operações regulares união concatenação e estrela União operador pipe Concatenação não há operador Estrela operador asterisco Exemplo abc concatenado com cda U ce abccdace Biblioteca RE 20 É recomendável usar parênteses para definir as operações com exatidão e agrupar os elementos de conjuntos Biblioteca RE 21 Código de exemplo 01 import re pattern r000 o padrão corresponde à string 000 teststring 000 a string de teste é 000 result refullmatchpattern teststring if result is not None printString s aceitateststring else printString s rejeitadateststring Biblioteca RE 22 Código de exemplo 02 import re pattern rabc o padrão corresponde à string 000 teststring 2 a string de teste é 2 result refullmatchpattern teststring if result is not None printString s aceitateststring else printString s rejeitadateststring Biblioteca RE 23 Código de exemplo 03 import re pattern rabac o padrão corresponde às strings ab U ac teststring ab a string de teste é ab result refullmatchpattern teststring if result is not None printString s aceitateststring else printString s rejeitadateststring Biblioteca RE 24 Código de exemplo 04 import re pattern rabac o padrão corresponde às strings ab U ac teststring ac a string de teste é ac result refullmatchpattern teststring if result is not None printString s aceitateststring else printString s rejeitadateststring Biblioteca RE 25 Código de exemplo 05 import re pattern rabac o padrão corresponde às strings ab U ac teststring bc a string de teste é bc result refullmatchpattern teststring if result is not None printString s aceitateststring else printString s rejeitadateststring Biblioteca RE 26 Código de exemplo 06 import re pattern rab o padrão corresponde às strings b ab aab teststring ab a string de teste é ab result refullmatchpattern teststring if result is not None printString s aceitateststring else printString s rejeitadateststring Biblioteca RE 27 Código de exemplo 06 import re pattern rab o padrão corresponde às strings b ab aab teststring aaaab a string de teste é aaaab result refullmatchpattern teststring if result is not None printString s aceitateststring else printString s rejeitadateststring Biblioteca RE 28 Código de exemplo 07 import re pattern rab o padrão corresponde às strings b ab aab teststring aaabab a string de teste é aaabab result refullmatchpattern teststring if result is not None printString s aceitateststring else printString s rejeitadateststring Biblioteca RE 29 Código de exemplo 08 import re pattern rabc o padrão corresponde às strings com a b ou c teststring cabac a string de teste é cabac result refullmatchpattern teststring if result is not None printString s aceitateststring else printString s rejeitadateststring Biblioteca RE 30 Código de exemplo 09 import re pattern rabc o padrão corresponde às strings com a b ou c teststring cabdac a string de teste é cabdac result refullmatchpattern teststring if result is not None printString s aceitateststring else printString s rejeitadateststring Biblioteca RE 31 Código de exemplo 10 import re pattern rzabc começam por z e depois seguem a b ou c teststring zac a string de teste é zac result refullmatchpattern teststring if result is not None printString s aceitateststring else printString s rejeitadateststring Biblioteca RE 32 Representação de intervalos por exemplo dígitos de 0 à 9 ou letras de a à z usamos colchetes com o primeiro e o último elementos do intervalo separados por hífen Biblioteca RE 33 Representação de intervalos por exemplo dígitos de 0 à 9 ou letras de a à z usamos colchetes com o primeiro e o último elementos do intervalo separados por hífen Exemplos 0 1 2 9 09 Biblioteca RE 34 Representação de intervalos por exemplo dígitos de 0 à 9 ou letras de a à z usamos colchetes com o primeiro e o último elementos do intervalo separados por hífen Exemplos 0 1 2 9 09 a b c z az Biblioteca RE 35 Usamos uma barra invertida para representação de símbolos especiais ou seja símbolos que possuem funções específicas com os parênteses hífen pontos etc Biblioteca RE 36 Usamos uma barra invertida para representação de símbolos especiais ou seja símbolos que possuem funções específicas com os parênteses hífen pontos etc Exemplos 789234 789234 Biblioteca RE 37 Usamos uma barra invertida para representação de símbolos especiais ou seja símbolos que possuem funções específicas com os parênteses hífen pontos etc Exemplos 789234 789234 12fev 12fev Biblioteca RE 38 Elabore e teste os padrões capazes de reconhecer as strings apresentadas nos exemplos datas CPF CEP e placas de carro Exercício 39 Teoria da Computação Aula 4 Operações e Expressões Regulares Prof Alex Torquato Souza Carneiro alexcarneirofaculdadeimpactacombr Agenda Operações regulares Recapitular linguagens regulares Definição Exemplos Expressões regulares Definição Equivalência com autômatos finitos 2 Operações regulares Definimos que Uma linguagem é chamada regular se existir um autômato finito capaz de reconhecêla 3 Operações regulares Exemplo consideremos a linguagem definida pelo conjunto de números que começam em 1 e são múltiplos de 5 1015100105110115120125130135 4 Operações regulares Exemplo consideremos a linguagem definida pelo conjunto de números que começam em 1 e são múltiplos de 5 1015100105110115120125130135 Qual o alfabeto desta linguagem 5 Operações regulares Exemplo consideremos a linguagem definida pelo conjunto de números que começam em 1 e são múltiplos de 5 1015100105110115120125130135 Qual o alfabeto desta linguagem Esta linguagem é regular 6 Operações regulares Operações regulares Operações regulares 9 q0 q1 q2 1 1 Operações regulares 10 q0 q1 q2 1 1 0129 Operações regulares 11 q0 q1 q2 1 1 q3 0129 q4 Operações regulares 12 q0 q1 q2 1 1 q3 0129 q4 05 05 Operações regulares 13 q0 q1 q2 1 1 q3 0129 q4 05 05 Operações regulares 14 q0 q1 q2 1 1 0129 q4 05 05 q3 Operações regulares 15 q0 q1 q2 1 1 0129 q4 05 05 05 05 q3 Operações regulares 16 q0 q1 q2 1 1 0129 q4 05 05 05 05 05 05 q3 Operações regulares 17 q0 q1 q2 1 1 0129 q4 05 05 05 05 05 05 10 q3 Operações regulares 18 q0 q1 q2 1 1 0129 q4 05 05 05 05 05 05 100 q3 Operações regulares 19 q0 q1 q2 1 1 0129 q4 05 05 05 05 05 05 152 q3 Operações regulares 20 q0 q1 q2 1 1 0129 q4 05 05 05 05 05 05 1205 q3 Operações regulares Como obtivemos um autômato capaz de reconhecer a linguagem formada pelo conjunto 1015100105110115120125130135 então podemos afirmar que esta é uma linguagem regular 21 Operações regulares Uma linguagem com 1 elemento exemplo BRASIL é regular 22 Operações regulares Uma linguagem com 1 elemento exemplo BRASIL é regular Sim 23 q0 q1 q2 q3 q4 q5 q6 q7 B R A S I L B R A S I L ABCZ ABCZ Operações regulares Uma linguagem com 2 elementos exemplo BRASILCHILE é regular 24 Operações regulares Uma linguagem com 2 elementos exemplo BRASILCHILE é regular Sim 25 q0 q1 q2 q3 q4 q5 q6 q11 B R A S I L BC R A S I L ABCZ q7 q8 q9 q10 C H I L E ABCZ H I L E Operações regulares Uma linguagem com N elementos é regular 26 Operações regulares Uma linguagem com N elementos é regular Sim Podemos construir um autômato formado por caminhos tais que cada um corresponda a um elemento da linguagem 27 Operações regulares Uma string sequência de elementos de um alfabeto pode ser formada por 0 1 2 elementos do alfabeto 28 Operações regulares Uma string sequência de elementos de um alfabeto pode ser formada por 0 1 2 elementos do alfabeto A string com 0 elementos é representada por 𝛆 29 Operações regulares Uma string sequência de elementos de um alfabeto pode ser formada por 0 1 2 elementos do alfabeto A string com 0 elementos é representada por 𝛆 Cada string por sua vez é um elemento de uma linguagem 30 Operações regulares Agora que temos conhecimento sobre linguagens regulares podemos definir o conceito de operações regulares 31 Operações regulares Agora que temos conhecimento sobre linguagens regulares podemos definir o conceito de operações regulares Em aritmética temos dois tipos de elementos objetos básicos números operações x 32 Operações regulares Agora que temos conhecimento sobre linguagens regulares podemos definir o conceito de operações regulares Em teoria da computação temos objetos básicos linguagens operações 33 Operações regulares Agora que temos conhecimento sobre linguagens regulares podemos definir o conceito de operações regulares Em teoria da computação temos objetos básicos linguagens operações união concatenação estrela 34 Operações regulares Sejam A a b c e B 1 2 3 duas linguagens 35 Operações regulares Sejam A a b c e B 1 2 3 duas linguagens A B a b c 1 2 3 36 Operações regulares Sejam A a b c e B 1 2 3 duas linguagens A B a b c 1 2 3 A B a1 a2 a3 b1 b2 b3 c1 c2 c3 37 Operações regulares Sejam A a b c e B 1 2 3 duas linguagens A B a b c 1 2 3 A B a1 a2 a3 b1 b2 b3 c1 c2 c3 A 𝛆 a b c aa ab ac ba bb bc ca cb cc aaa aab 38 Operações regulares Sejam A e B duas linguagens A B x x A ou x B 39 Operações regulares Sejam A e B duas linguagens A B x x A ou x B A B xy x A e y B 40 Operações regulares Sejam A e B duas linguagens A B x x A ou x B A B xy x A e y B A x1x2x3xk k 0 e xi A 41 Operações regulares As operações de união e concatenação são binárias isto é possuem dois operandos A B A B A operação estrela é unária isto é possui apenas um operando A 42 Operações regulares O resultado da aplicação de uma operação regular sobre uma linguagem regular é também uma linguagem regular 43 Operações regulares Exemplo A BRASIL CHILE CANADÁ B POR ESP ING 44 Operações regulares Exemplo A BRASIL CHILE CANADÁ B POR ESP ING Defina A B A B A 45 Operações regulares Exemplo A BRASIL CHILE CANADÁ B POR ESP ING Como poderíamos obter um linguagem tal que cada elemento correspondesse ao país com todos os idiomas porém com um símbolo de separação entre o país e o idioma BRASILPOR BRASILESPBRASILINGCHILEPOR 46 Expressões regulares Podemos expandir o conceito das operações regulares criando sentenças com as strings das linguagens 47 Expressões regulares Podemos expandir o conceito das operações regulares criando sentenças com as strings das linguagens Exemplo seja o alfabeto 01 48 Expressões regulares Podemos expandir o conceito das operações regulares criando sentenças com as strings das linguagens Exemplo seja o alfabeto 01 Desejamos obter uma linguagem regular que contemple todas as strings tais que o primeiro elemento é seguindo por uma sequência de 0s 49 Expressões regulares Podemos expandir o conceito das operações regulares criando sentenças com as strings das linguagens Exemplo seja o alfabeto 01 Desejamos obter uma linguagem regular que contemple todas as strings tais que o primeiro elemento é seguindo por uma sequência de 0s 010010000100000010000000010000 50 Expressões regulares Exemplo seja o alfabeto 01 Desejamos obter uma linguagem regular que contemple todas as strings tais que o primeiro elemento é seguindo por uma sequência de 0s 010010000100000010000000010000 Para o primeiro elemento podemos definir a união entre 0 e 1 51 Expressões regulares Exemplo seja o alfabeto 01 Desejamos obter uma linguagem regular que contemple todas as strings tais que o primeiro elemento é seguindo por uma sequência de 0s 010010000100000010000000010000 Para o primeiro elemento podemos definir a união entre 0 e 1 Para os demais elementos podemos definir a operação estrela sobre 0 52 Expressões regulares Exemplo seja o alfabeto 01 Desejamos obter uma linguagem regular que contemple todas as strings tais que o primeiro elemento é seguindo por uma sequência de 0s 010010000100000010000000010000 Para o primeiro elemento podemos definir a união entre 0 e 1 Para os demais elementos podemos definir a operação estrela sobre 0 As duas partes devem ser concatenadas 53 Expressões regulares Exemplo seja o alfabeto 01 Desejamos obter uma linguagem regular que contemple todas as strings tais que o primeiro elemento é seguindo por uma sequência de 0s 010010000100000010000000010000 Para o primeiro elemento podemos definir a união entre 0 e 1 Para os demais elementos podemos definir a operação estrela sobre 0 As duas partes devem ser concatenadas Resultado 0 10 54 Expressões regulares Simplificando a notação podemos representar um conjunto 0 ou 1 simplesmente pelo elemento 0 ou 1 Resultado 0 10 0 10 55 Expressões regulares Simplificando a notação podemos representar um conjunto 0 ou 1 simplesmente pelo elemento 0 ou 1 Resultado 0 10 0 10 Podemos representar a operação de concatenação pelo posicionamento de uma linguagem na sequência de outra Resultado 0 10 0 10 ou ainda 0 10 0 10 56 Expressões regulares Observamos que é possível obter linguagens com base em expressões regulares 57 Expressões regulares Observamos que é possível obter linguagens com base em expressões regulares Podemos então afirmar que se uma linguagem foi obtida a partir de uma expressão regular então esta é uma linguagem regular 58 Expressões regulares Observamos que é possível obter linguagens com base em expressões regulares Podemos então afirmar que se uma linguagem foi obtida a partir de uma expressão regular então esta é uma linguagem regular Usando a nossa definição de linguagem regular com base na existência de um autômato podemos concluir que existe ao menos 1 autômato associado a uma expressão regular 59 Expressões regulares Tomando o exemplo da expressão 0 10 podemos montar o autômato 60 Expressões regulares Tomando o exemplo da expressão 0 10 podemos montar o autômato 61 q0 q2 q1 01 0 1 01 Expressões regulares Qual autômato corresponde à expressão regular ae ea U 𝜀 62 Teoria da Computação Aula 3 AFD e Linguagens formais Prof Alex Torquato Souza Carneiro alexcarneirofaculdadeimpactacombr Agenda AFD Recapitulação Exemplos Linguagens formais Definição Elementos Exemplos 2 Definimos que AFD Definimos que 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 4 Elementos de um AFD AFD Elementos de um AFD Q𝛴δq0F Q conjunto finito de estados 6 AFD Elementos de um AFD Q𝛴δq0F Q conjunto finito de estados 𝛴 conjunto finito denominado alfabeto 7 AFD Elementos de um AFD Q𝛴δq0F Q conjunto finito de estados 𝛴 conjunto finito denominado alfabeto δ Q x 𝛴 Q define a função de transição 8 AFD Elementos de um AFD Q𝛴δq0F Q conjunto finito de estados 𝛴 conjunto finito denominado alfabeto δ Q x 𝛴 Q define a função de transição q0 q0 Q é o estado inicial 9 AFD Elementos de um AFD Q𝛴δq0F Q conjunto finito de estados 𝛴 conjunto finito denominado alfabeto δ Q x 𝛴 Q define a função de transição q0 q0 Q é o estado inicial F F Q é o conjunto de estados de aceitação 10 AFD Elementos de um AFD 11 q0 q1 q2 0 1 0 1 0 1 AFD Elementos de um AFD Q q0 q1 q2 12 q0 q1 q2 0 1 0 1 0 1 AFD Elementos de um AFD Q q0 q1 q2 𝛴 0 1 13 q0 q1 q2 0 1 0 1 0 1 AFD Elementos de um AFD Q q0 q1 q2 𝛴 0 1 δ Q x 𝛴 Q 14 q0 q1 q2 0 1 0 1 0 1 AFD Elementos de um AFD Q q0 q1 q2 𝛴 0 1 δ Q x 𝛴 Q 15 q0 q1 q2 0 1 0 1 0 1 δq00 q1 δq01 q2 δq10 q1 δq11 q2 δq20 q1 δq21 q2 AFD Elementos de um AFD Q q0 q1 q2 𝛴 0 1 δ Q x 𝛴 Q q0 q0 16 q0 q1 q2 0 1 0 1 0 1 δq00 q1 δq01 q2 δq10 q1 δq11 q2 δq20 q1 δq21 q2 AFD Elementos de um AFD Q q0 q1 q2 𝛴 0 1 δ Q x 𝛴 Q q0 q0 F q1 17 q0 q1 q2 0 1 0 1 0 1 δq00 q1 δq01 q2 δq10 q1 δq11 q2 δq20 q1 δq21 q2 AFD Exemplo 01 considere o alfabeto 𝛴 a b c d e vamos elaborar um autômato capaz de reconhecer strings que contenham a sequência adcbe por exemplo aadcbea ddadcbe adcbeccc eadcbead 18 AFD Exemplo 01 considere o alfabeto 𝛴 a b c d e vamos elaborar um autômato capaz de reconhecer strings que contenham a sequência adcbe por exemplo aadcbea ddadcbe adcbeccc eadcbead 19 AFD Exemplo 01 𝛴 a b c d e e contém adcbe 20 q0 AFD Exemplo 01 𝛴 a b c d e e contém adcbe 21 q0 q1 q2 q3 q4 q5q5 AFD Exemplo 01 𝛴 a b c d e e contém adcbe 22 q0 q1 q2 q3 q4 q5q5 AFD Exemplo 01 𝛴 a b c d e e contém adcbe 23 q0 q1 q2 q3 q4 q5 a d c b e q5 AFD Exemplo 01 𝛴 a b c d e e contém adcbe 24 q0 q1 q2 q3 q4 q5 a d c b e q5 a AFD Exemplo 01 𝛴 a b c d e e contém adcbe 25 q0 q1 q2 q3 q4 q5 a d c b e q5 a 𝛴 a d c b e AFD Exemplo 01 𝛴 a b c d e e contém adcbe 26 q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 01 𝛴 a b c d e e contém adcbe Q q0 q1 q2 q3 q4 q5 27 a d c b e q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 01 𝛴 a b c d e e contém adcbe Q q0 q1 q2 q3 q4 q5 𝛴 a b c d e 28 a d c b e q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 01 𝛴 a b c d e e contém adcbe Q q0 q1 q2 q3 q4 q5 𝛴 a b c d e δ Q x 𝛴 Q 29 a d c b e q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 01 𝛴 a b c d e e contém adcbe Q q0 q1 q2 q3 q4 q5 𝛴 a b c d e δ Q x 𝛴 Q 30 δq0x q0 x a δq1x q0 x d δq2x q0 x c δq3x q0 x b δq4x q0 x e δq5x q5 x 𝛴 δq0a q1 δq1d q2 δq2c q3 δq3b q4 δq4e q5 a d c b e q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 01 𝛴 a b c d e e contém adcbe Q q0 q1 q2 q3 q4 q5 𝛴 a b c d e δ Q x 𝛴 Q q0 q0 F q5 31 δq0x q0 x a δq1x q0 x d δq2x q0 x c δq3x q0 x b δq4x q0 x e δq5x q5 x 𝛴 δq0a q1 δq1d q2 δq2c q3 δq3b q4 δq4e q5 a d c b e q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 01 𝛴 a b c d e e contém adcbe Testes abcadc 32 a d c b e q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 01 𝛴 a b c d e e contém adcbe Testes abcadc 33 a d c b e q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 01 𝛴 a b c d e e contém adcbe Testes abcadc aabadcbeae 34 a d c b e q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 01 𝛴 a b c d e e contém adcbe Testes abcadc aabadcbeae 35 a d c b e q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 01 𝛴 a b c d e e contém adcbe Testes abcadc aabadcbeae 36 a d c b e q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 01 𝛴 a b c d e e contém adcbe Testes abcadc aabadcbeae aeaeabcde 37 a d c b e q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 01 𝛴 a b c d e e contém adcbe Testes abcadc aabadcbeae aeaeabcde 38 a d c b e q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 01 𝛴 a b c d e e contém adcbe Testes abcadc aabadcbeae aeaeabcde adcbeaeadcbe 39 a d c b e q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 01 𝛴 a b c d e e contém adcbe Testes abcadc aabadcbeae aeaeabcde adcbeaeadcbe 40 a d c b e q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 01 𝛴 a b c d e e contém adcbe Testes abcadc aabadcbeae aeaeabcde adcbeaeadcbe 41 a d c b e q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 01 𝛴 a b c d e e contém adcbe Testes abcadc aabadcbeae aeaeabcde adcbeaeadcbe aaddccbbeeabcde 42 a d c b e q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 01 𝛴 a b c d e e contém adcbe Testes abcadc aabadcbeae aeaeabcde adcbeaeadcbe aaddccbbeeabcde 43 a d c b e q0 q1 q2 q3 q4 q5q5 a da ca ba ea 𝛴 a a a a AFD Exemplo 02 considere o alfabeto 𝛴 0 1 2 3 4 5 6 7 8 9 vamos elaborar um autômato capaz de reconhecer strings que começam com a sequência 123 terminem com 789 e contenham 35053 por exemplo 12335053789 12365153505312789 12333335053377789 123535053737789 44 Linguagens Formais Linguagens Formais Definimos uma linguagem como um conjunto de strings formadas a partir de um alfabeto 𝛴 46 Linguagens Formais Definimos uma linguagem como um conjunto de strings formadas a partir de um alfabeto 𝛴 As strings que compõem uma linguagem podem apresentar qualquer tamanho ie qualquer quantidade de símbolos provenientes do alfabeto 𝛴 47 Linguagens Formais Definimos uma linguagem como um conjunto de strings formadas a partir de um alfabeto 𝛴 As strings que compõem uma linguagem podem apresentar qualquer tamanho ie qualquer quantidade de símbolos provenientes do alfabeto 𝛴 Observamos então que existem linguagens com uma quantidade finita de strings e outras com infinitas strings para um mesmo alfabeto 𝛴 48 Linguagens Formais A string vazia ou string de tamanho nulo é definida por 𝜖 épsilon 49 Linguagens Formais A string vazia ou string de tamanho nulo é definida por 𝜖 épsilon Uma linguagem sem strings corresponde ao conjunto vazio L 50 Linguagens Formais A string vazia ou string de tamanho nulo é definida por 𝜖 épsilon Uma linguagem sem strings corresponde ao conjunto vazio L Observamos que uma linguagem L1 𝜖 é diferente de uma linguagem L2 51 Linguagens Formais União de linguagens podemos usar o conceito de união de conjuntos em linguagens em que unimos as strings correspondentes de cada linguagem 52 Linguagens Formais União de linguagens podemos usar o conceito de união de conjuntos em linguagens em que unimos as strings correspondentes de cada linguagem Exemplo L1 0 01 012 e L2 11 12 21 L1 U L2 s s L1 ou s L2 L1 U L2 0 11 01 12 012 21 53 Linguagens Formais Concatenação de strings 54 Linguagens Formais Concatenação de strings podemos concatenar duas ou mais strings criando uma nova string que é composta pelas strings originais 55 Linguagens Formais Concatenação de strings podemos concatenar duas ou mais strings criando uma nova string que é composta pelas strings originais Exemplos com 𝛴 01 s1 00 s2 01 s3 11 s1 s2 ou s1 s2 00 01 0001 s1 s3 ou s1 s3 00 11 0011 s1 s2 s3 ou s1 s2 s3 00 01 11 000111 56 Linguagens Formais Concatenação de linguagens podemos usar o conceito de concatenação de strings em linguagens em que concatenamos as strings correspondentes de cada linguagem 57 Linguagens Formais Concatenação de linguagens podemos usar o conceito de concatenação de strings em linguagens em que concatenamos as strings correspondentes de cada linguagem Exemplo L1 0 01 012 e L2 11 12 21 L1 L2 si sj si L1 e sj L2 58 Linguagens Formais Concatenação de linguagens podemos usar o conceito de concatenação de strings em linguagens em que concatenamos as strings correspondentes de cada linguagem Exemplo L1 0 01 012 e L2 11 12 21 L1 L2 si sj si L1 e sj L2 L1 L2 011 012 021 0111 0112 0121 01211 01212 01221 59 Linguagens Formais Concatenação de linguagens podemos concatenar uma linguagem com ela própria com a seguinte notação L² L L 60 Linguagens Formais Concatenação de linguagens podemos concatenar uma linguagem com ela própria com a seguinte notação L² L L Exemplo L1 0 1 L1² L1 L1 00 01 10 11 61 Linguagens Formais Concatenação de linguagens podemos concatenar uma linguagem com ela própria com a seguinte notação L² L L Exemplo L1 0 1 L1² L1 L1 00 01 10 11 L1³ L1 L1 L1 000 001 010 011 100 101 110 111 62 Linguagens Formais Concatenação de linguagens de modo especial L0 𝜖 e Ln1 Ln L 63 Linguagens Formais Concatenação de linguagens de modo especial L0 𝜖 e Ln1 Ln L E se fizermos todas as uniões de Ln 64 Linguagens Formais Concatenação de linguagens de modo especial L0 𝜖 e Ln1 Ln L E se fizermos todas as uniões de Ln Definimos então L L0 U L1 U L2 U 65 Linguagens Formais Também podemos definir a operação sobre um alfabeto em que uma linguagem é dada pela concatenação dos símbolos de um alfabeto 66 Linguagens Formais Também podemos definir a operação sobre um alfabeto em que uma linguagem é dada pela concatenação dos símbolos de um alfabeto Seja o alfabeto A a b então A2 aa ab ba bb A3 aaa aab aba abb baa bab bba bbb 67 Linguagens Formais Também podemos definir a operação sobre um alfabeto em que uma linguagem é dada pela concatenação dos símbolos de um alfabeto Seja o alfabeto A a b então A2 aa ab ba bb A3 aaa aab aba abb baa bab bba bbb A0 𝜖 68 Linguagens Formais Também podemos definir a operação sobre um alfabeto em que uma linguagem é dada pela concatenação dos símbolos de um alfabeto Seja o alfabeto A a b então A2 aa ab ba bb A3 aaa aab aba abb baa bab bba bbb A0 𝜖 A 𝜖 a b aa ab ba bb aaa aab 69 Linguagens Formais Seja s uma string formada por símbolos de um alfabeto A sempre teremos que s A 70 Linguagens Formais Seja s uma string formada por símbolos de um alfabeto A sempre teremos que s A Se s tem n símbolos do alfabeto A também observamos que s An 71 Linguagens Formais Podemos definir padrões de strings elaborando linguagens em que todas as strings apresentam o padrão desejado 72 Linguagens Formais Podemos definir padrões de strings elaborando linguagens em que todas as strings apresentam o padrão desejado Exemplos com o alfabeto A 0 1 strings que começam com 11 73 Linguagens Formais Podemos definir padrões de strings elaborando linguagens em que todas as strings apresentam o padrão desejado Exemplos com o alfabeto A 0 1 strings que começam com 11 L1 11 e L2 0 1 𝜖 L3 L1 L2 11 110 111 1100 1101 1110 74 Linguagens Formais Podemos definir padrões de strings elaborando linguagens em que todas as strings apresentam o padrão desejado Exemplos com o alfabeto A 0 1 strings que terminam com 00 75 Linguagens Formais Podemos definir padrões de strings elaborando linguagens em que todas as strings apresentam o padrão desejado Exemplos com o alfabeto A 0 1 strings que terminam com 00 L1 00 e L2 0 1 𝜖 L3 L2 L1 00 000 100 0000 0100 1000 76 Linguagens Formais Podemos definir padrões de strings elaborando linguagens em que todas as strings apresentam o padrão desejado Exemplos com o alfabeto A 0 1 strings que começam com 11 e terminam com 00 77 Teoria da Computação Aula 2 Autômatos finitos Prof Alex Torquato Souza Carneiro alexcarneirofaculdadeimpactacombr Agenda Autômatos finitos Definição Representação por diagramas Autômatos Finitos Determinísticos AFD Exemplos 2 Autômatos finitos 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 3 Autômatos finitos 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 4 Autômatos finitos 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 5 Infância Adolescência Adulto Velhice Autômatos finitos 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 6 Início do processo Infância Adolescência Adulto Velhice Autômatos finitos 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 7 Início do processo Último estado Infância Adolescência Adulto Velhice Autômatos finitos 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 8 Autômatos finitos 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 9 Fechada Aberta Modelo para uma porta automática Autômatos finitos 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 10 Fechada Aberta Modelo para uma porta automática Alguém se aproxima Autômatos finitos 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 11 Fechada Aberta Modelo para uma porta automática Alguém se aproxima Ninguém por perto Autômatos finitos No exemplo da porta os estados são aberta fechada o estado inicial da porta é fechada o estado final para a porta é fechada 12 Autômatos 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 13 Autômatos finitos Esta representação também é denominada diagrama de estados 14 Fechada Aberta Alguém se aproxima Ninguém por perto Autômatos finitos Esta representação também é denominada diagrama de estados O estado final de um autômato é denominado estado de aceitação 15 Fechada Aberta Alguém se aproxima Ninguém por perto Autômatos finitos Alguns estados podem ser retroalimentados 16 Fechada Aberta Alguém se aproxima Ninguém por perto Autômatos finitos Alguns estados podem ser retroalimentados 17 Fechada Aberta Alguém se aproxima Ninguém por perto Alguém por perto Autômatos finitos Funcionamento Começo 18 Fechada Aberta Alguém se aproxima Ninguém por perto Alguém por perto Autômatos finitos Funcionamento Começo fechada Alguém se aproxima 19 Fechada Aberta Alguém se aproxima Ninguém por perto Alguém por perto Autômatos finitos Funcionamento Começo fechada Alguém se aproxima aberta Ninguém por perto 20 Fechada Aberta Alguém se aproxima Ninguém por perto Alguém por perto Autômatos finitos Funcionamento Começo fechada Alguém se aproxima aberta Ninguém por perto fechada Alguém se aproxima 21 Fechada Aberta Alguém se aproxima Ninguém por perto Alguém por perto Autômatos finitos Funcionamento Começo fechada Alguém se aproxima aberta Ninguém por perto fechada Alguém se aproxima aberta Alguém por perto 22 Fechada Aberta Alguém se aproxima Ninguém por perto Alguém por perto Autômatos finitos Funcionamento Começo fechada Alguém se aproxima aberta Ninguém por perto fechada Alguém se aproxima aberta Alguém por perto aberta Alguém por perto 23 Fechada Aberta Alguém se aproxima Ninguém por perto Alguém por perto Autômatos finitos Funcionamento Começo fechada Alguém se aproxima aberta Ninguém por perto fechada Alguém se aproxima aberta Alguém por perto aberta Alguém por perto aberta Ninguém por perto 24 Fechada Aberta Alguém se aproxima Ninguém por perto Alguém por perto Autômatos finitos Funcionamento Começo fechada Alguém se aproxima aberta Ninguém por perto fechada Alguém se aproxima aberta Alguém por perto aberta Alguém por perto aberta Ninguém por perto fechada 25 Fechada Aberta Alguém se aproxima Ninguém por perto Alguém por perto Autômatos finitos Usaremos os autômatos com o objetivo de identificar padrões em strings 26 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 27 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 28 q0 q1 a a b c b c 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 29 q0 q1 a a b c b c 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 30 q0 q1 a a b c b c 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 31 q0 q1 a a b c b c 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 32 q0 q1 a a b c b c s abca ok s aaab não s acabcaa 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 33 q0 q1 a a b c b c s abca ok s aaab não s acabcaa ok Autômatos finitos Definição formal um autômato finito é uma 5tupla Q𝛴δq0F Q 𝛴 δ q0 F 34 Autômatos finitos Definição formal um autômato finito é uma 5tupla Q𝛴δq0F Q conjunto finito de estados 𝛴 δ q0 F 35 Autômatos finitos Definição formal um autômato finito é uma 5tupla Q𝛴δq0F Q conjunto finito de estados 𝛴 conjunto finito denominado alfabeto δ q0 F 36 Autômatos finitos Definição formal um autômato finito é uma 5tupla Q𝛴δq0F Q conjunto finito de estados 𝛴 conjunto finito denominado alfabeto δ Q x 𝛴 Q define a função de transição q0 F 37 Autômatos finitos Definição formal um autômato finito é uma 5tupla Q𝛴δq0F Q conjunto finito de estados 𝛴 conjunto finito denominado alfabeto δ Q x 𝛴 Q define a função de transição q0 q0 Q é o estado inicial F 38 Autômatos finitos Definição formal um autômato finito é uma 5tupla Q𝛴δq0F Q conjunto finito de estados 𝛴 conjunto finito denominado alfabeto δ Q x 𝛴 Q define a função de transição q0 q0 Q é o estado inicial F F Q é o conjunto de estados de aceitação 39 Autômatos finitos O alfabeto 𝛴 corresponde aos possíveis estímulos fornecidos ao autômato 40 Autômatos finitos O alfabeto 𝛴 corresponde aos possíveis estímulos fornecidos ao autômato Em problemas computacionais elementares é comum vermos 𝛴 01 41 Autômatos finitos O alfabeto 𝛴 corresponde aos possíveis estímulos fornecidos ao autômato Em problemas computacionais elementares é comum vermos 𝛴 01 42 par ímpar 0 1 0 1 0 1 Autômatos finitos O alfabeto 𝛴 corresponde aos possíveis estímulos fornecidos ao autômato Em problemas computacionais elementares é comum vermos 𝛴 01 43 par ímpar 0 1 0 1 0 1 Verifica se um número binário é par Autômatos finitos O alfabeto 𝛴 corresponde aos possíveis estímulos fornecidos ao autômato Em problemas computacionais elementares é comum vermos 𝛴 01 44 par ímpar 0 1 0 1 0 1 Verifica se um número binário é par 0 0 1 0 0 1 0 0 Autômatos finitos A função de transição δ corresponde às condições de mudança entre os estados de acordo com os estímulos 45 Autômatos finitos 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 46 Autômatos finitos δ Q x 𝛴 Q q0 q0 Q q0parímpar 𝛴 01 F par 47 q0 par ímpar 0 1 0 1 0 1 Autômatos finitos δ Q x 𝛴 Q q0 q0 Q q0parímpar 𝛴 01 F par Q x 𝛴 q00 q01 par0 par1 ímpar0 ímpar1 48 q0 par ímpar 0 1 0 1 0 1 Autômatos finitos δ Q x 𝛴 Q q0 q0 Q q0parímpar 𝛴 01 F par Q x 𝛴 q00 q01 par0 par1 ímpar0 ímpar1 49 q0 par ímpar 0 1 0 1 0 1 Domínio da função δ Autômatos finitos δ Q x 𝛴 Q q0 q0 Q q0parímpar 𝛴 01 F par Q x 𝛴 q00 q01 par0 par1 ímpar0 ímpar1 Q q0parímpar 50 q0 par ímpar 0 1 0 1 0 1 Domínio da função δ Imagem da função δ 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 51 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² 52 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 53 Revisão sobre funções Exemplo fx x² Domínio ℝ números reais Imagem ℝ números reais não negativos 54 5 2 1 0 1 3 5 0 1 4 9 16 25 Revisão sobre funções Exemplo fx x² Domínio ℝ números reais Imagem ℝ números reais não negativos 55 5 2 1 0 1 3 5 0 1 4 9 16 25 Revisão sobre funções Exemplo fx x² Domínio ℝ números reais Imagem ℝ números reais não negativos 56 5 2 1 0 1 3 5 0 1 4 9 16 25 Revisão sobre funções Exemplo fx x² Domínio ℝ números reais Imagem ℝ números reais não negativos 57 5 2 1 0 1 3 5 0 1 4 9 16 25 Revisão sobre funções Exemplo fx x² Domínio ℝ números reais Imagem ℝ números reais não negativos 58 5 2 1 0 1 3 5 0 1 4 9 16 25 Revisão sobre funções Exemplo fx x² Domínio ℝ números reais Imagem ℝ números reais não negativos 59 5 2 1 0 1 3 5 0 1 4 9 16 25 Revisão sobre funções Exemplo fx x² Domínio ℝ números reais Imagem ℝ números reais não negativos 60 5 2 1 0 1 3 5 0 1 4 9 16 25 Autômatos finitos δ Q x 𝛴 Q q0 q0 Q q0parímpar 𝛴 01 F par δq00 61 q0 par ímpar 0 1 0 1 0 1 Autômatos finitos δ Q x 𝛴 Q q0 q0 Q q0parímpar 𝛴 01 F par δq00 par 62 q0 par ímpar 0 1 0 1 0 1 Autômatos finitos δ Q x 𝛴 Q q0 q0 Q q0parímpar 𝛴 01 F par δq00 par 63 q0 par ímpar 0 1 0 1 0 1 Estado atual Estímulo Próximo estado Autômatos finitos δ Q x 𝛴 Q q0 q0 Q q0parímpar 𝛴 01 F par δq00 par δq01 ímpar 64 q0 par ímpar 0 1 0 1 0 1 Autômatos finitos δ Q x 𝛴 Q q0 q0 Q q0parímpar 𝛴 01 F par δq00 par δq01 ímpar δpar0 par 65 q0 par ímpar 0 1 0 1 0 1 Autômatos finitos δ Q x 𝛴 Q q0 q0 Q q0parímpar 𝛴 01 F par δq00 par δq01 ímpar δpar0 par δímpar0 par 66 q0 par ímpar 0 1 0 1 0 1 Autômatos finitos δ Q x 𝛴 Q q0 q0 Q q0parímpar 𝛴 01 F par δq00 par δq01 ímpar 67 q0 par ímpar 0 1 0 1 0 1 Autômatos finitos δ Q x 𝛴 Q q0 q0 Q q0parímpar 𝛴 01 F par δq00 par δq01 ímpar δpar1 ímpar 68 q0 par ímpar 0 1 0 1 0 1 Autômatos finitos δ Q x 𝛴 Q q0 q0 Q q0parímpar 𝛴 01 F par δq00 par δq01 ímpar δpar1 ímpar δímpar1 ímpar 69 q0 par ímpar 0 1 0 1 0 1 Autômatos finitos δq00 par δq01 ímpar δpar0 par δímpar0 par δpar1 ímpar δímpar1 ímpar 70 q0 par ímpar 0 1 0 1 0 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 71 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 72 q0 q1 q2 0 1 1 0 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 73 q0 q1 q2 0 1 1 0 O que acontece com o autômato se este estiver em q1 e receber 0 O que acontece com o autômato se este estiver em q2 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 74 q0 q1 q2 0 1 1 0 O que acontece com o autômato se este estiver em q1 e receber 0 O que acontece com o autômato se este estiver em q2 e receber 1 Autômato finito não determinístico 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 75 q0 q1 q2 0 1 1 0 1 0 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 76 q0 q1 q2 0 1 1 0 1 0 Autômato finito determinístico Autômatos finitos Uso de autômatos linguagens 77 Autômatos finitos Considerando o alfabeto 𝛴 definimos uma linguagem como todas as sequências de strings que podemos formar com este alfabeto 78 Autômatos 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 79 Autômatos 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 80 Autômatos finitos Segue o conceito de linguagem regular Uma linguagem é chamada regular se existir um autômato finito capaz de reconhecêla 81 Autômatos finitos Exemplo criar um autômato que identifique gerúndios 82 Autômatos finitos Exemplo criar um autômato que identifique gerúndios Gerúndios são palavras que terminam em NDO andando estudando falando dormindo lendo enchendo 83 qndo Autômatos finitos Exemplo criar um autômato que identifique gerúndios 84 q qn qn d qndo n n d o d o 𝛴 qndo Autômatos finitos Exemplo criar um autômato que identifique gerúndios 85 q qn qn d qndo n n d o d o 𝛴 estudando qndo Autômatos finitos Exemplo criar um autômato que identifique gerúndios 86 q qn qn d qndo n n d o d o 𝛴 nadando qndo Autômatos finitos Exemplo criar um autômato que identifique gerúndios 87 q qn qn d qndo n n d o d o 𝛴 vendendo qndo Autômatos finitos Exemplo criar um autômato que identifique gerúndios 88 q qn qn d qndo n n d o d o 𝛴 achado qndo Autômatos finitos Exemplo criar um autômato que identifique gerúndios 89 q qn qn d qndo n n d o d o 𝛴 vinda Autômatos finitos Exemplo criar um autômato que identifique verbos de 1ª conjugação no infinitivo final ar 90 q q1 Autômatos finitos Exemplo criar um autômato que identifique palavras com o prefixo inter 91 q q1 Teoria da Computação Aula 1 Apresentação da disciplina Prof Alex Torquato Souza Carneiro alexcarneirofaculdadeimpactacombr Agenda Apresentação da disciplina Objetivos Avaliações Bibliografia Introdução à Teoria da Computação Histórico Conceitos Iniciais 2 Apresentação da disciplina Teoria da Computação Autômatos e linguagens Teoria da computabilidade Teoria da complexidade 3 Objetivos Conhecer os principais conceitos que compõem a ciência da computação Conhecer os limites da computação e do desenvolvimento de soluções computacionais Desenvolver habilidades de análise de soluções computacionais 4 Avaliações 5 ACs Avaliação oficial Avaliação substitutiva 5 Bibliografia HOPCROFT JE MOTWANI R ULLMAN JD Introdução a Teoria de Autômatos Linguagens e Computação Rio de Janeiro Campus 2002 SIPSER M Introduction to the Theory of Computation 3rd Ed Boston Cengage 2013 GERSTING J L Fundamentos Matemáticos para a Ciência da Computação 7ed Rio de Janeiro LTC Livros Técnicos e Científicos 2016 6 Introdução à Teoria da Computação Quais problemas podem ser resolvidos por um computador Quais não podem 7 Introdução à Teoria da Computação Quais problemas podem ser resolvidos por um computador Quais não podem Como comparar soluções computacionais diferentes para um mesmo problema Como saber se um problema é resolvível 8 Introdução à Teoria da Computação Definir os limites da computação e dos computadores é uma questão abordada desde os anos 30 9 Introdução à Teoria da Computação Definir os limites da computação e dos computadores é uma questão abordada desde os anos 30 Responder esta questão não é simples porém é necessário para a evolução da tecnologia 10 Introdução à Teoria da Computação 11 Definir os limites da computação e dos computadores é uma questão abordada desde os anos 30 Responder esta questão não é simples porém é necessário para a evolução da tecnologia A resposta deve ser dada na dimensão conceitual os recursos para o desenvolvimento de uma solução podem surgir sem a necessidade de mudança de paradigma Introdução à Teoria da Computação 12 Exemplo Deep Learning teoria desenvolvida no final da década de 50 Introdução à Teoria da Computação 13 Exemplo Deep Learning teoria desenvolvida no final da década de 50 as aplicações tornaramse viáveis nos últimos anos com a implementação dos conceitos já existentes em GPUs Graphics Processing Units Conceitos Iniciais 14 As sub áreas da Teoria da Computação Autônomos e linguagens Quais os fundamentos para a teoria da computação Conceitos Iniciais 15 As sub áreas da Teoria da Computação Autônomos e linguagens Quais os fundamentos para a teoria da computação Teoria da computabilidade Para quais problemas é possível desenvolver um algoritmo capaz de solucionálos Conceitos Iniciais 16 As sub áreas da Teoria da Computação Autônomos e linguagens Quais os fundamentos para a teoria da computação Teoria da computabilidade Para quais problemas é possível desenvolver um algoritmo capaz de solucionálos Teoria da complexidade Como comparar diferentes soluções para um mesmo problema Conceitos Iniciais 17 A base da Teoria da Computação é a matemática em especial Conceitos Iniciais 18 A base da Teoria da Computação é a matemática em especial Conjuntos Sequências Funções Conceitos Iniciais 19 A base da Teoria da Computação é a matemática em especial Conjuntos Sequências Funções Grafos Strings Lógica Conceitos Iniciais 20 Conjuntos c1 1 4 7 1 4 7 Conceitos Iniciais 21 Conjuntos c1 1 4 7 c2 2 4 6 1 4 7 2 6 Conceitos Iniciais 22 Conjuntos c1 1 4 7 c2 2 4 6 c1 c2 4 1 4 7 2 6 Conceitos Iniciais 23 Conjuntos c1 1 4 7 c2 2 4 6 c1 c2 1 2 4 6 7 1 4 7 2 6 Conceitos Iniciais 24 Conjuntos c1 1 4 7 c2 2 4 6 c1 c2 1 7 1 4 7 2 6 Conceitos Iniciais 25 Conjuntos c1 1 4 7 c2 2 4 6 c2 c1 2 6 1 4 7 2 6 Conceitos Iniciais 26 Sequências l 2 5 10 2 5 10 Conceitos Iniciais 27 Sequências l 2 5 10 2 5 10 l1 5 10 Conceitos Iniciais 28 Sequências l 2 5 10 m 1 7 12 2 5 10 1 7 12 Conceitos Iniciais 29 Sequências l 2 5 10 m 1 7 12 2 5 10 1 7 12 l m 2 5 10 1 7 12 Conceitos Iniciais 30 Sequências l 2 5 10 m 1 7 12 1 7 12 2 5 10 m l 1 7 12 2 5 10 Conceitos Iniciais Conceitos Iniciais 32 Funções y fx Conceitos Iniciais 33 Funções y fx 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 x y Conceitos Iniciais 34 Funções y fx 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 x y Conceitos Iniciais 35 Funções y fx 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 x y fx Conceitos Iniciais 36 Funções y fx 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 x y fx x 1 Conceitos Iniciais 37 Funções y fx 0 1 2 3 4 5 6 7 8 1 2 5 10 17 26 37 50 65 x y Conceitos Iniciais 38 Funções y fx 0 1 2 3 4 5 6 7 8 1 2 5 10 17 26 37 50 65 x y fx Conceitos Iniciais 39 Funções y fx 0 1 2 3 4 5 6 7 8 1 2 5 10 17 26 37 50 65 x y fx x² 1 Conceitos Iniciais 40 Grafos Grafos são conjuntos de elementos com relações que conectam alguns deles entre si Conceitos Iniciais 41 Grafos Grafos são conjuntos de elementos com relações que conectam alguns deles entre si 1 2 3 4 5 Conceitos Iniciais 42 Grafos Grafos são conjuntos de elementos com relações que conectam alguns deles entre si 1 2 3 4 5 V 1 2 3 4 5 Conceitos Iniciais 43 Grafos Grafos são conjuntos de elementos com relações que conectam alguns deles entre si 1 2 3 4 5 V 1 2 3 4 5 Conceitos Iniciais 44 Grafos Grafos são conjuntos de elementos com relações que conectam alguns deles entre si 1 2 3 4 5 V 1 2 3 4 5 A 1 2 2 3 3 4 2 4 4 5 1 5 Conceitos Iniciais 45 Strings strings são sequências de caracteres utilizadas na representação da informação textual dentro de sistemas computacionais Conceitos Iniciais 46 Strings strings são sequências de caracteres utilizadas na representação da informação textual dentro de sistemas computacionais i m p a c t a Conceitos Iniciais 47 Strings strings são sequências de caracteres utilizadas na representação da informação textual dentro de sistemas computacionais i m p a c t a Propriedades das strings comprimento alfanumérica numérica caixa alta caixa baixa etc Conceitos Iniciais 48 Strings strings são sequências de caracteres utilizadas na representação da informação textual dentro de sistemas computacionais i m p a c t a Propriedades das strings comprimento alfanumérica numérica caixa alta caixa baixa etc Operações com strings comparação concatenação normalização etc Conceitos Iniciais 49 Lógica A lógica que trataremos consiste na lógica Booleana Conceitos Iniciais 50 Lógica A lógica que trataremos consiste na lógica Booleana A lógica Booleana por sua vez é trata de variáveis que podem assumir apenas dois valores portanto variáveis binárias o que pode ser interpretado como VERDADEIRO e FALSO Conceitos Iniciais 51 Lógica A lógica que trataremos consiste na lógica Booleana A lógica Booleana por sua vez é trata de variáveis que podem assumir apenas dois valores portanto variáveis binárias o que pode ser interpretado como VERDADEIRO e FALSO Neste contexto temos as variáveis e as operações lógicas NOT AND OR XOR NAND NOR Conceitos Iniciais 52 Lógica A forma mais usual de resolvermos equações lógicas consiste em definir a tabela verdade das equações Conceitos Iniciais 53 Lógica A forma mais usual de resolvermos equações lógicas consiste em definir a tabela verdade das equações Conceitos Iniciais 54 Lógica A forma mais usual de resolvermos equações lógicas consiste em definir a tabela verdade das equações Y X1 AND X2 Conceitos Iniciais 55 Lógica A forma mais usual de resolvermos equações lógicas consiste em definir a tabela verdade das equações Y X1 AND X2 X1 X2 Y 0 0 0 0 1 0 1 0 0 1 1 1 X1 X2 Y F F F F V F V F F V V V Conceitos Iniciais 56 Lógica A forma mais usual de resolvermos equações lógicas consiste em definir a tabela verdade das equações Y X1 OR X2 Conceitos Iniciais 57 Lógica A forma mais usual de resolvermos equações lógicas consiste em definir a tabela verdade das equações Y X1 OR X2 X1 X2 Y 0 0 0 0 1 1 1 0 1 1 1 1 X1 X2 Y F F F F V V V F V V V V Conceitos Iniciais 58 Lógica A forma mais usual de resolvermos equações lógicas consiste em definir a tabela verdade das equações Y X1 XOR X2 Conceitos Iniciais 59 Lógica A forma mais usual de resolvermos equações lógicas consiste em definir a tabela verdade das equações Y X1 XOR X2 X1 X2 Y 0 0 0 0 1 1 1 0 1 1 1 0 X1 X2 Y F F F F V V V F V V V F Conceitos Iniciais 60 Lógica A forma mais usual de resolvermos equações lógicas consiste em definir a tabela verdade das equações Y X1 OR NOT X2 Conceitos Iniciais 61 Lógica A forma mais usual de resolvermos equações lógicas consiste em definir a tabela verdade das equações Y X1 OR NOT X2 X1 X2 Y 0 0 1 0 1 0 1 0 1 1 1 1 X1 X2 Y F F V F V F V F V V V V Conceitos Iniciais 62 Lógica A forma mais usual de resolvermos equações lógicas consiste em definir a tabela verdade das equações Y NOT X1 AND NOT X2 X1 X2 Y 0 0 0 1 1 0 1 1 X1 X2 Y F F F V V F V V Conceitos Iniciais 63 Lógica A forma mais usual de resolvermos equações lógicas consiste em definir a tabela verdade das equações Y NOT X1 AND NOT X2 X1 X2 Y 0 0 0 1 1 0 1 1 X1 X2 Y F F F V V F V V