Autômatos - UnB

1. Introdução

1.1. Autômatos, Computabilidade e Complexidade

1.1.1. Teoria da complexidade

1.1.2. Teoria da computabilidade

1.1.3. Teoria dos autômatos

1.2. Noções e Terminologia Matemáticas

1.2.1. Conjuntos

1.2.1.1. elementos/membros

1.2.1.2. conjunto, subconjunto

1.2.1.3. multiconjunto

1.2.1.4. subconjunto próprio

1.2.1.5. união, interseção, complemento

1.2.2. Sequências e uplas

1.2.2.1. sequência

1.2.2.2. upla

1.2.2.3. conjunto de partes

1.2.2.4. produto cartesiano/cruzado

1.2.3. Funções e relações

1.2.3.1. função

1.2.3.2. mapeamento

1.2.3.3. domínio, contradomínio

1.2.3.4. predicado/propriedade

1.2.3.5. argumentos

1.2.3.6. aridade

1.2.3.7. relação k-aria

1.2.3.8. relação de equivalência

1.2.4. Grafos

1.2.5. Cadeias e linguagens

1.2.6. Lógica booleana

1.3. Definições, Teoremas e Provas

1.4. Tipos de Prova

1.4.1. Prova por construção

1.4.2. Prova por contradição

1.4.3. Prova por indução

2. Linguagens regulares

2.1. Autômatos Finitos

2.1.1. Autômato finito

2.1.1.1. δ(ri, wi+1) = ri+1

2.1.2. Computação

2.1.2.1. [ NOTAÇÃO ] O autômato M reconhece a linguagem L, se L = {w / M aceita w}

2.1.3. Linguagem regular

2.1.4. Uma linguagens é regular sss um AFN a reconhece

2.1.5. [ Operações regulares ] União, concatenção e estrela

2.1.5.1. [ U ] A classe de linguagens regulares é fechada sob a operação de união

2.1.5.2. [ º ] A classe de linguagens regulares é fechada sob a operação de concatenação

2.2. Não determinísticos

2.2.1. Autômato finito não-determinístico

2.2.1.1. ri+1 pertence à δ(ri, wi+1)

2.2.2. Todo AFN tem um AFD equivalente

2.2.3. [ Operações regulares ]

2.2.3.1. [ U ] A classe de linguagens regulares é fechada sob a operação de união

2.2.3.2. [ º ] A classe de linguagens regulares é fechada sob a operação de concatenação

2.2.3.3. [ * ] A classe de linguagens regulares é fechada sob a operação de estrela

2.3. se s é qualquer cadeia de A de comprimento mínimo p, então s pode ser dividida em três partes, s=xyz, satisfazendo:

2.3.1. para cada i >= 0, xy^iz pertence à A ou seja, pode pertencer à A cadeia só com formato xz, mas ela não poderá ser bombeada

2.3.2. |y| > 0 ou seja, o comprimento de y deve ser no mínimo 1 (ou 1 loop, ou 1 ciclo) para se obter o p mínimo

2.3.3. |xy| <= p ou seja, z pode ser cadeia vazia ou não

2.4. Expressões regulares

2.4.1. Expressão regular

2.4.2. Uma linguagem é regular sss alguma expressão regular a descreve

2.4.2.1. Se uma linguagem é descrita por uma expressão regular, então ela é regular

2.4.2.2. Se uma linguagem é regular, então ela é descrita por uma expressão regular

2.4.3. Autômato finito não-determinístico generalizado

2.4.4. Para qualquer AFNG, a função "CONVERT(G)" retorna uma expressão regular equivalente à G.

2.5. Linguagens não regulares

2.5.1. Teorema : Lema do bombeamento: Se A é uma linguagem regular, então existe um número p (o comprimento do bombeamento) tal que,

2.5.2. Como provar que linguagem L não é regular usando lema do bombeamento

2.5.2.1. [ Prova por Contradição ] Supor L regular, sendo p o comprimento do bombeamento

2.5.2.2. Encontrar cadeia s, tal que |s| <= p

2.5.2.3. Provar que s não pode ser bombeada considerando que s não pode ser dividivo em s = xyz, fazendo o próximo passo

2.5.2.4. Encontrar valor i em s = xy^iz, tal que s não pertença à L

3. Notação

3.1. Definição

3.2. Teorema

3.3. Lema

3.4. Corolário

3.5. Afirmativa

4. Linguagens livre-de-contexto

4.1. Gramática

4.1.1. uAv origina uwv (se existe a regra A -> w)

4.1.2. u0 deriva un, se u0 = un (variável ou terminal), se existe sequência de derivações u0, u1, ..., un

4.1.3. Gramática é ambígua quando mesma cadeia é derivada mais à esquerda de duas formas ou mais (duas árvores sintáticas diferentes)

4.1.4. Regular

4.1.4.1. A -> aB A -> ε

4.2. Livre-do-contexto

4.2.1. Qualquer linguagem livre-de-contexto é gerada por uma gramática livre-do-contexto na forma normal de Chomsky

4.2.1.1. Abstrato: Provar que toda gramática possui uma gramática equivalente na Forma normal de Chomsky

4.2.1.2. Concreto : Detalhar as 5 regras de forma normal de chomsky, mostrando que elas valem

4.3. Forma normal de Chomsky

4.3.1. S -> ε A -> BC A -> a

4.3.1.1. Como obter:

4.3.1.2. S0 -> S

4.3.1.3. uAv => uv

4.3.1.4. A -> B ==> A -> B -> regras_de_B

4.3.1.5. A -> cB ==> A -> CB e C -> c

4.3.1.6. A -> BCD ==> A -> BZ e Z -> CD

4.4. Autômato com pilha

4.4.1. Uma linguagem é livre-do-contexto sss algum autômato com pilha a reconhece ( LLC <=> AP )

4.4.1.1. Se uma linguagem é livre-do-contexto, então algum autômato com pilha a reconhece ( LLC => AP )

4.4.1.1.1. Como LLC <=> GLC, a prova é feita convertendo a GLC em um AP

4.4.1.1.2. GLC G = (V, Σ, R, S) <=> AP P = (Q, Σ, Γ, δ, q0 F)

4.4.1.2. Se um autômato com pilha reconhece alguma linguagem, então ela é livre-do-contexto ( AP => LLC )

4.4.1.2.1. Como LLC <=> GLC, a prova é feita convertendo um AP em uma GLC

4.4.1.2.2. Características do AP

4.4.1.2.3. Seja o AP P = (Q, Σ, Γ, δ, q0 {q_aceita}) e G = (V, Σ, R, S) V = {Apq | p, q pertencem à Q}

4.4.1.2.4. Regras :

4.4.1.2.5. Apq gera cadeia x sss x pode levar P de p com pilha vazia à q com pilha vazia (NÃO tem no caderno, NÃO deve cair)

4.4.2. Para todo AFD existe um AP equivalente ( AFD => AP )

4.4.2.1. Prova: Dado o AFD M=(Q, Σ, δ, q0 F), construimos o AP equivalente P=(Q, Σ, Σ, δ', q0 F), alfabeto da pilha é o alfabeto das cadeias, e δ está definida como δ'(q, a, b) =

4.4.2.1.1. {( δ(q, a) , ε )}, se b é cadeia vazia

4.4.2.1.2. vazio, se b não é cadeia vazia

4.4.3. Começa com pilha vazia; (ri+1, b) pertence à δ(ri, wi+1, a)

4.4.4. OBS: Só é possível fazer produto cartesiano com duas APs se existirem duas pilhas.  É possível fazer AP x AFD fazendo a cópia da pilha do AP (para interseção ou união).

4.4.5. Função de Transição:   δ (QxΣxΓ) = { (QxΓ), ... } δ(estado_ataul, lê, desempilha)  = (prox_estado, empilha)

4.5. Lema do Bombeamento

4.5.1. para cada i >= 0, u v^i x y^i z

4.5.2. |vy| > 0

4.5.3. |vxy| <= p

5. Máquina de Turing

5.1. Diferenças entre AF e MT

5.1.1. MT pode escrever e ler a fita

5.1.2. A cabeça de leitura-escrita pode se mover pra Esquerda e Direita

5.1.3. A fita é infinita

5.1.4. Estados de rejeitar e aceitar fazem efeito imediato

5.2. Configuração

5.2.1. Inicial: q0 w

5.2.2. δ(qi, b) = (qk, c, D), então u a qi b v =origina=> u a c qk v

5.3. Linguagem Turing-reconhecível se alguma MT a reconhece

5.4. Linguagem é Turing-decidível se alguma MT a decide

5.5. Variantes de MTs

5.5.1. MT Parada

5.5.2. MT Multifita

5.5.3. MT Fita duplamente infinita

5.5.4. MT Não-determinística

5.5.5. MT Enumeradora

5.6. MT exemplos

5.6.1. INVERT

5.6.2. ENDMARK

5.6.3. LEFTEND

5.6.4. ERASE

5.6.5. EVEN

5.6.6. INCR

5.6.7. NEXTLEX

5.6.8. EQUAL

5.6.9. COPY

5.6.10. ENUM

5.6.11. COMP

5.6.12. ADD

5.6.13. MULT

5.6.14. SRQT

6. Decidibilidade

6.1. Linguagens Decidíveis

6.1.1. A_AFD : Problema da aceitação

6.1.1.1. A_AFN é uma linguagem decidível

6.1.1.2. A_EXP é uma linguagem decidível

6.1.2. V_AFD : Problema da vacuidade

6.1.2.1. V_AFN é uma linguagem decidível

6.1.2.2. V_EXP é uma linguagem decidível

6.1.3. EQ_AFD : Problema da equivalência

6.1.3.1. EQ_AFD_AFN é decidível

6.1.3.2. EQ_AFN_EXP é decidível

6.1.4. Livres-do-Contexto

6.1.4.1. A_GLC : Problema da aceitação

6.1.4.2. V_GLC : Problema da vacuidade

6.1.4.3. EQ_GLC : Problema da equivalência

6.1.5. Toda linguagem Livre-do-Contexo é decidível (Regular incluso)

6.2. A_MT : Problema da parada

6.2.1. Cardinalidade

6.2.1.1. Um conjunto A é CONTÁVEL se é FINITO ou CARDINALIDADE é igual a de N (naturais)

6.2.1.2. Conjunto dos racionais é contável

6.2.1.2.1. Método da diagonalização

6.2.1.2.2. Construa uma matriz pra os números racionais

6.2.1.2.3. Alinhe esses números com os naturias, pegando da diagona (esq -> dir), pulando os repetidos

6.2.1.3. Conjunto dos reais é incontável

6.2.1.3.1. Método da diagonalização:

6.2.1.3.2. Faça uma tabela de N x R

6.2.1.3.3. Pegue os elementos da diagonal dos numeros reais.

6.2.1.3.4. No número da diagonal, para cada DÍGITO depois da virgula, se < 9, some 1, se não, subtraia 1 (sei lá, qualquer coisa)

6.2.1.3.5. Esse número NÃO vai estar na tabela, POIS se estivesse na i-esima linha,  seu i-ésimo dígito estaria somado + 1

6.2.2. Algumas linguagens NÃO são Turing-reconhecíveis

6.2.3. A_MT é indecidível

6.2.3.1. Paradoxo dos catálogos

6.2.3.1.1. Suponha a linguagem DECIDÍVEL A_MT = {<M,w>| M MT, w cadeia}. <M,w> é a descrição de uma MT M específica e de uma cadeia w específica. M pode aceitar w ou não.

6.2.3.1.2. Então é possível construir uma MT H que decide a linguagem A_MT.

6.2.3.1.3. H(<M,w>) aceita se M aceita w H(<M,w>) rejeita se M não aceita w

6.2.3.1.4. Podemos construir outra MT D que faz +- o OPOSTO de H, ou seja, "aceita" se "rejeita" e vice e versa.

6.2.3.1.5. Construímos D usando H como subrotina

6.2.3.1.6. D recebe como entrada a descrição de uma MT (que pode ser inclusive a descrição de D).

6.2.3.1.7. PARADOXAL: D vai decidir se uma MT aceita sua própria descrição

6.2.3.1.8. D(<M>) aceita se M rejeita <M> D(<M>) rejeita se M aceita <M>

6.2.3.1.9. D(<D>) aceita se D rejeita <D> D(<D>) rejeita se D aceita <D> CONTRADIÇÃO => D, H não podem existir

6.2.3.2. Método da diagonalização

6.2.3.2.1. Só para visualizar, a contradição ocorre na linha de "D", coluna "<D>", na tabela da descrião:

6.3. Uma linguagem é DECIDÍVEL se e somente se ela e seu COMPLEMENTO são Turing-reconhecíveis

6.4. Provar que é decidível == Construir MT "Sobre a entrada ..."

7. Redutibilidade

7.1. Problemas Indecidíveis redutíveis à A_MT

7.1.1. PARA_MT

7.1.2. V_MT

7.1.3. REGULAR_MT

7.1.4. EQ_MT

7.2. Teorema de Rice

7.2.1. Propriedade

7.2.1.1. Exemplos

7.2.1.1.1. Fala da propriedade da LINGUAGEM: P = {<M> / M é uma MT e a cadeia abc pertence à L(M)}

7.2.1.1.2. Fala da ESTRUTURA da MT P = {<M> / M é MT com 5 estados}

7.2.2. Propriedade trivial

7.2.2.1. P = vazio

7.2.2.2. P = {<M> / M é uma MT}

7.3. Provar que indecidível ==

7.3.1. Suponha X decidível

7.3.2. D decide X

7.3.3. Usamos D para construir S que decide A_MT

7.3.4. S recebe <M,w> de entrada. Se D aceita, S aceita (M aceita w) Se D rejeita, S rejeita (M rejeita w)

7.3.5. Existe um bloco B dentro de S que vem antes de D. B é responsável pela redução

7.3.6. Construa uma M1 usando o bloco M que é a entrada de X. Observe que M1 nunca será rodada, só será usada pra provar que M não pode existir

7.3.7. Rode D sobre <M1>

7.3.8. Se D aceita, aceite. Se rejeita, rejeite. (a maioria das vezes é assim)

7.3.9. Portanto, S decide A_MT. Mas A_MT é indecidível.

7.3.10. Portanto D não existe. Então X é indecidível.

7.4. Reduções via História de Computação (Configurações)

7.5. Autômato Linearmente Limitado ALL

7.5.1. A_ALL é decidível

7.5.2. V_ALL é decidível

7.5.3. TODAS_GLC é indecidível

7.5.4. Seja M um ALL com q estados e g símbolos no alfabeto da fita. Existem exatamente  q*n*(g^n) configurações distintas de M para uma fita de comprimento n

7.5.4.1. q (estado de controle) n (posição da cabeça) g (símbolo) g*g*...*g = g^n (cadeias possíveis) 0 1      n           (fita)

7.6. Problema da correspondência de Post PCP

7.7. Redutibilidade por Mapeamento