Decidibilidade de linguagem baseadas em autómatos
27 Novembro 2018, 09:30 • André Souto
Dualidade problema - linguagem.
Exemplos.
Re-capitulação de codificações para máquinas de Turing.
Decidibilidade de linguagens regulares:
-- Aceitação de uma string por um autómato (DFA e NDFA);
-- Aceitação de uma string gerada por uma expressão regular;
-- Linguagem aceite por um (N)DFA ser vazia;
-- Igualdade de linguagens de dois autómatos.