2. Decidable

3. Undecidable

3. Undecidable

0 votes

0 votes

1. Decidable, membership problem for all language except RE is decidable

2. Decidable, run TM on all strings of length atmost k for k steps and accept if TM accepts at least one of the strings.

3. Undecidable, can be reduced to state entry problem.

2. Decidable, run TM on all strings of length atmost k for k steps and accept if TM accepts at least one of the strings.

3. Undecidable, can be reduced to state entry problem.