Abstract:
write this here
Problem 01
Let ALLDFA={⟨A⟩∣A is a DFA and L(A)=Σ∗}. Show that ALLDFA is decidable.
Problem 02
Let AϵCFG={⟨G⟩∣G is a context-free grammar and G generates ϵ}. Show that AϵCFG is decidable.
Problem 03
Consider the following context-free grammar:
SABC→aA∣Bb∣C→aa∣B∣C→bb∣A∣C→c∣ϵ
Recall that ACFG={⟨G,w⟩∣G is a CFG and G generates string w}
- Is ⟨w,G⟩∈ACFG?
- Is ⟨G⟩∈ACFG?
- Is ⟨G,abb⟩∈ACFG?
- Is ⟨G,ϵ⟩∈ACFG?
- Is ⟨G,abc⟩∈ACFG?
- Is ⟨G,ac⟩∈ACFG?
Problem 04
Let A={⟨R,S⟩∣R and S are regular expressions and L(R)⊆L(S)}. Show that A is decidable.