Decidability — true or false?

Exercise and reference answers

Questions

1. Statement is true

   Yes

   Statement

   The Halting Problem is undecidable.

2. Statement is true

   Yes

   Statement

   Equivalence of two DFAs is decidable.

3. Statement is true

   No

   Statement

   Equivalence of two CFGs is decidable.

4. Statement is true

   Yes

   Statement

   The intersection of two regular languages is regular.