Mind map
TC
Map content
TC
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)
- Regras
- Autômatos de pilha
- Definição formal
- <Q, Σ, Γ, δ, q0, F>
- Definição formal
- Definição formal
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
- Turing decidível
- 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>
- Máquina de Turing universal (U)
- Classes
Information
- Description
- Mind Map on TC, created by Daniel Rodrigues on 21/11/2019.
- Created by
- Daniel Rodrigues
- Views
- 0
- Rating