As Máquinas de Touring

[pic 1][pic 2][pic 3][pic 4]

Alonso Ali

Abril 2020

[pic 5][pic 6][pic 7][pic 8][pic 9][pic 10][pic 11][pic 12]

[pic 13] [pic 14] [pic 15] [pic 16] [pic 17] [pic 18]        [pic 19] [pic 20]

start[pic 21][pic 22][pic 23]

---

0,1

---

0,1

[pic 24] [pic 25] [pic 26] [pic 27] [pic 28] [pic 29]        [pic 30] [pic 31]

Existe algo que um autˆomato finito n˜ao-determin´ıstico consiga fazer que um determin´ıstico n˜ao consiga?[pic 32]

[pic 33][pic 34][pic 35][pic 36][pic 37][pic 38][pic 39][pic 40]

Existe algo que um autˆomato finito n˜ao-determin´ıstico consiga fazer que um determin´ıstico n˜ao consiga?[pic 41]

NA˜O!![pic 42]

[pic 43][pic 44][pic 45][pic 46][pic 47]

[pic 48][pic 49][pic 50][pic 51][pic 52][pic 53][pic 54][pic 55]

Uma linguagem ´e regular se existe m´aquina de estados finita que a reconhe¸ca.[pic 56]

[pic 57][pic 58][pic 59][pic 60][pic 61][pic 62][pic 63][pic 64]

Uma linguagem ´e regular se existe m´aquina de estados finita que a reconhe¸ca.[pic 65]

Exemplo de linguagem NA˜O regular: {0n1n : n ∈ N}.[pic 66]

[pic 67][pic 68][pic 69][pic 70][pic 71][pic 72][pic 73][pic 74]

[pic 75] [pic 76] [pic 77] [pic 78] [pic 79] [pic 80]        [pic 81] [pic 82]

[pic 83]

[pic 84][pic 85][pic 86][pic 87][pic 88][pic 89][pic 90][pic 91]

{0 1 : n ∈ N}[pic 92]

[pic 93][pic 94]

Alonso Ali

---

M´aquinas de Turing

---

Abril 2020        6 / 26

{0 1 : n ∈ N}[pic 95]

[pic 96][pic 97]

Alonso Ali

---

M´aquinas de Turing

---

Abril 2020        7 / 26

{0 1 : n ∈ N}[pic 98]

[pic 99][pic 100]

Alonso Ali

---

M´aquinas de Turing

---

Abril 2020        8 / 26

{0 1 : n ∈ N}[pic 101]

[pic 102][pic 103]

Alonso Ali

---

M´aquinas de Turing

---

Abril 2020        9 / 26

{0 1 : n ∈ N}[pic 104]

[pic 105][pic 106]

Alonso Ali

---

M´aquinas de Turing

---

Abril 2020        10 / 26

{0 1 : n ∈ N}[pic 107]

[pic 108][pic 109]

Alonso Ali

---

M´aquinas de Turing

---

Abril 2020        11 / 26

{0 1 : n ∈ N}[pic 110]

[pic 111][pic 112]

Alonso Ali

---

M´aquinas de Turing

---

Abril 2020        12 / 26

{0 1 : n ∈ N}[pic 113]

[pic 114][pic 115]

Alonso Ali

---

M´aquinas de Turing

---

Abril 2020        13 / 26

{0 1 : n ∈ N}[pic 116]

[pic 117][pic 118]

Alonso Ali

---

M´aquinas de Turing

---

Abril 2020        14 / 26

{0 1 : n ∈ N}[pic 119]

[pic 120][pic 121]

Alonso Ali

---

M´aquinas de Turing

---

Abril 2020        15 / 26

Acabou?[pic 122]