Homework 4 - Context Free Grammars and Regular Expressions

Abstract:

write this here

---

Problem 01

Let $AL{L}_{DFA}=\{⟨A⟩\mid \text{A is a DFA and }\mathcal{L}(A)={\Sigma }^{\ast }\}$. Show that $AL{L}_{DFA}$ is decidable.

---

Problem 02

Let $A{ϵ}_{CFG}=\{⟨G⟩\mid \text{G is a context-free grammar and G generates }ϵ\}$. Show that $A{ϵ}_{CFG}$ is decidable.

---

Problem 03

Consider the following context-free grammar:

$$\begin{array}{rl}S& \to aA\mid Bb\mid C\\ A& \to aa\mid B\mid C\\ B& \to bb\mid A\mid C\\ C& \to c\mid ϵ\end{array}$$

Recall that $A_{CFG}=\{⟨G,w⟩\mid \text{G is a CFG and G generates string w}\}$

1. Is $⟨w,G⟩\in A_{CFG}$?
2. Is $⟨G⟩\in A_{CFG}$?
3. Is $⟨G,abb⟩\in A_{CFG}$?
4. Is $⟨G,ϵ⟩\in A_{CFG}$?
5. Is $⟨G,abc⟩\in A_{CFG}$?
6. Is $⟨G,ac⟩\in A_{CFG}$?

---

Problem 04

Let $A=\{⟨R,S⟩\mid \text{R and S are regular expressions and }\mathcal{L}(R)\subseteq \mathcal{L}(S)\}$. Show that $A$ is decidable.