Gestalte GoConqr mit. Was sollen wir als Nächstes hinzufügen?

Mindmap

TC

Daniel Rodrigues Portugiesisch

Inhalt der Mindmap

TC

  1. Gramáticas livres de contexto

    • Definição formal
      • <V,E,R,S>
    • Derivações
      • Inferência recursiva
      • Derivações
        • Zero ou mais passos de derivação (*)
        • Mais a esquerda (ou direita)
      • Árvore de derivação
        • Ambiguidade
    • Forma normal de Chomsky
      • Regras
        • A -> BC
        • A -> a
      • Algoritmo
        • 1. Símbolo inicial não pode aparecer na direita
        • 2. Remover os "e" (apenas a variável inicial pode conter)
        • 3. Regras do tipo A -> B não são permitidas (regras com 1 variável)
        • 4. Regras do tipo A -> ABC não são permitidas (apenas dois símbolos)
        • 5. Regras A -> aB não são permitidas (não misturar variáveis com terminais)
    • Autômatos de pilha
      • Definição formal
        • <Q, Σ, Γ, δ, q0, F>
  2. Máquinas de turing

    • Classes
      • Turing decidível
        • A máquina sempre para
      • Turing reconhecível
        • A máquina para em algumas entradas e entra em loop em outras
        • Não dá para saber se a máquina entrou em loop
    • Enumeradores
      • Imprime todas as palavras da linguagem que a máquina reconhece
    • Tese de Church-Turing
      • Você pode incluir qualquer coisa em uma descrição de alto nível, desde você possa escrever um programa de computador para fazer isso.
    • Composição
      • Unidade de controle
      • Fita Infinita
      • Um cabeçote
    • Definição formal
    • Decidibilidade
      • Máquina de Turing universal (U)
        • Simula uma máquina de turing M com uma palavra w
        • Se M entra em loop, U também
        • Linguagem de U (Amt)
          • São as palavras aceitas por M
      • Codificação
        • Qualquer objeto pode ser codificado como uma string na fita
        • <M, w>

Informationen

Beschreibung
Mindmap am TC, erstellt von Daniel Rodrigues am 21/11/2019.
Erstellt von
Daniel Rodrigues
Aufrufe
0
Bewertung

Mehr zu Máquinas de Turing

Feedback

Worum geht es?

Was sollen wir als Nächstes hinzufügen?