Teoria da Computação: Aula 3 - AFD e Linguagens Formais

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 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 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 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