Week 3- Decidable problems for Real Life

Question 1

What are some decidable languages from the lectures?

Answer 1

L(A) = ∅
L recognised by a DFA
L recognised by a NFA
L recognised as a regular expression
L recognised by two seperate DFAs

Question 2

TRUE OR FALSE: You can use a turing machine to determine whether two different DFAs recognise the same language.

Answer 2

TRUE.