CIS 420/520 Assignment 7
Decidability
The problems here are all from the second edition of the Sipser book. If you
are using the first edition, many of the problems are the same, but the numbering
of the problems is not.
Assignments are due at the beginning of class on the due date indicated.
Use machine copy if at all possible - in any case, writing and diagrams
must be neat and legible.
Assignment 7 is due Friday, November 30.
Sipser 4.3
Let ALLDFA = { <A> | A is a DFA and L(A) = Σ*}.
Show that ALLDFA is decidable.
Sipser 4.12
Let A = { <R,S> | R and S are regular expressions and L(R) ⊆ L(S) }.
Show that A is decidable.
Sipser 4.14 (for CIS 520 students)
Show that the problem of determining whether a CFG generates all strings in 1* is decidable.
In other words, show that { <G> | G is a CFG over {0,1} and 1* ⊆ L(G) }
is a decidable language.