Let Σ be a finite alphabet and L ⊆ Σ be a language. Let Σ0 ⊆ Σ. For each string w = w1 · · · wn ∈ Σ , define res(w, Σ 0 ) = y1 · · · yn where yi = wi if wi ∈ Σ 0 , and yi = if wi ∈ Σ \ Σ 0 , for each 1 ≤ i ≤ n. (For example res(abracadabra, {a, b}) = abaaaba.) Then define res(L, Σ 0 ) = {res(w, Σ 0 ) : w ∈ L}
I have a very general direction and thought process for these problems, however, i am not completely sure i could construct a viable proof for the following problems. If anyone could point me in the right direction, that would be much appreciated.
(a) Show that if L ⊆ Σ* ? is regular and Σ0 ⊆ Σ, res(L, Σ 0 ) must be regular.
i know for this one, a DFA cannot be made for this language. So i will have to figure out a different way. A subset of any regular language is not necessarily regular.
(b) Show that if L ⊆ Σ* is context-free and Σ0 ⊆ Σ, res(L, Σ 0 ) must be context-free.
I know that for this problem, one way to solve it would be to provide a context free grammar
(c) Show that if L ⊆ Σ* and res(L, Σ 0 ) is regular whenever Σ0 ⊂ Σ, L need not be regular.
For this question, we can say that even if L is not regular, that the empty language is a regular subset of this language. This would be true in all languages (whether it is regular or not)
HINTS: For the first question, start with a right-regular grammar for $L$. Keep all productions of the form $X\to\epsilon$ and all productions of the form $X\to x$ and $X\to xY$ such that $x\in\Sigma_0$. If $x\in\Sigma\setminus\Sigma_0$, replace each production of the form $X\to x$ with $X\to\epsilon$; what should you do with the productions of the form $X\to xY$?
Alternatively, you could start with a DFA for $L$ and change it to an NFA for $\operatorname{res}(L,\Sigma_0)$ by replacing certain transitions with $\epsilon$-transitions; which ones?
For the second question you can adapt my first suggestion above to show how to modify a context-free grammar for $L$ to a context-free grammar for $\operatorname{res}(L,\Sigma_0)$.
For the third question try using $\Sigma=\{0,1\}$ and taking $L$ to be a very commonly used example of a context-free language that is not regular.