Mind map
Linguagens formais, Autômatos e Computabilidade
Map content
Linguagens formais, Autômatos e Computabilidade
Linguagens e grámatica
- Linguagens regulares
- Autômatos
- Autômato Finito
- Deterministico
- - Dependendo do estado corrente e do simbolo lido - Pode assumir um unico estado
- Não-deterministico
- - Dependendo do estado corrente e do simbolo lido - Pode assumir um conjunto de estados alternativos
- Com movimentos varios
- - Dependendo do estado corrente e sem ler qualquer simbolo - Pode assumir um conjunto de estados
- Deterministico
- Autômato Finito
- Expressão Regular
- Grámatica Regular
- Hierarquia de Chomsky
- Sistemas de Estados Finitos
- Autômatos
- Linguagens Livre de Contexto
- Hierarquia de Chomsky
- Gramática Livre de Contexto
- Autômato com Pilha
- Arvore de Derivação
- Gramática Ambigua
- Simplificação de Grámatica
- Simbolos inuteis
- Exclusão de variaveis ou terminais não-usados
- Produções Vazias
- Da forma A -> Ɛ
- Produções que substituem variaveis
- Da forma A -> B
- Simbolos inuteis
- Forma Normal
- Forma normal de Chomsky
- A -> BC ou A -> a
- Forma normal de Greibach
- A -> aα α Palavra de Variaveis
- Forma normal de Chomsky
- Linguagens regulares
Maquina de Turing
- • São dispositivos mais genéricos que os autômatos vistos até o momento e, portanto, têm a capacidade de trabalhar e processar um número maior de linguagens. • Sua aparência básica é similar a dos autômatos. • Embora as máquinas de Turing sejam primitivas, não existe nenhum modelo computacional mais poderoso até os dias atuais. Existem apenas aperfeiçoamentos deste modelo. • As máquinas de Turing foram propostas como modelos matemáticos para representar procedimentos. • Qualquer cômputo que possa ser descrito por uma máquina de Turing, poderá ser realizado mecanicamente (Tese de Church). • De outra parte, qualquer cômputo que possa ser realizado por um computador digital, poderá ser descrito por uma máquina de Turing.
Information
- Description
- Mind Map on Linguagens formais, Autômatos e Computabilidade, created by Jubileu Silva on 29/06/2020.
- Created by
- Jubileu Silva
- Views
- 0
- Rating