Decidable Problems

Question 1

What are the meta language classes we studied in class?

Answer 1

• A (acceptance problem)
• E (emptiness testing problem)
• EQ (equivalence testing problem)
• ALL (all string testing problem)

Question 2

Is the acceptance problem for DFAs decidable?

Answer 2

Yes

Question 3

Is the acceptance problem for NFAs decidable?

Answer 3

Yes

Question 4

Is the acceptance problem for regular expressions (RE) decidable?

Answer 4

Yes

Question 5

Is the emptiness testing problem for DFAs decidable?

Answer 5

Yes

Question 6

Is the equivalence testing problems for DFAs decidable?

Answer 6

Yes

Question 7

Is the acceptance test for CFGs decidable?

Answer 7

Yes

Question 8

Is the acceptance test for PDAs decidable?

Answer 8

Yes

Question 9

Is the emptiness test for CFGs decidable?

Answer 9

Yes

Question 10

A_M (acceptance problem for M)

Answer 10

A_M = {<M, w>: M ∈ M accepts (or generates) w}

Question 11

E_M (emptiness testing problem for M)

Answer 11

E_M = {<M>: M ∈ *M* has L(M) = ∅}</M>

Question 12

EQ_M (equivalence testing problem for M)

Answer 12

EQ_M = {<A, B>: A, B ∈ M and L(A) = L(B)}

Question 13

ALL_M (all string testing problem for M)

Answer 13

ALL_M = {<M>: M ∈ *M* has L(M) = Σ*}</M>