Conceitos Essenciais de Decidibilidade e Complexidade
Classificado em Formação e Orientação para o Emprego
Escrito em em
português com um tamanho de 6,54 KB
Capítulo 3: Linguagens e Reconhecimento
- Linguagem Turing-Reconhecível (Recursivamente Enumerável): Aceita por uma Máquina de Turing (MT).
- Linguagem Turing-Decidível (Recursiva): Aceita e rejeita por uma Máquina de Turing (MT).
Capítulo 4: Linguagens Decidíveis
Problemas de Decidibilidade Comuns:
- AAFD, AAFN (Aceitação por Autômatos Finitos).
- AEXP.REG: Se uma expressão regular gera uma dada cadeia.
- VAFD: Se um Autômato Finito Determinístico (AFD) aceita alguma cadeia (Teste de Vacuidade).
- EQAFD: Se a linguagem aceita por um AFD é igual à linguagem aceita por outro AFD.
- AGLC: Se uma Gramática Livre-do-Contexto (GLC) gera uma cadeia específica.
- VGLC: Se uma GLC gera alguma cadeia (Teste de Vacuidade).
Propriedades de Fechamento:
- A classe