T or F: The subset of a regular set over {a, b, c} consisting of just those strings that don’t use the symbol c is regular.

Question

I think it is true. A subset of any regular set should still be recognized by some DFA, and is therefor regular? IS this correct? I am not sure if I am understanding the question correctly. Thanks for any clarification.

Answer 1

Let $L=\{a,b\}^*\subset\{a,b,c\}^*$. Define $M=(Q,\Sigma,\delta,q_0,F)$ by $Q=\{q_0,q_c\}, \Sigma=\{a,b,c\}$, $\delta:Q\times\Sigma$ where $$ \delta(q,i) = \begin{cases} q_0,& q=q_0\text{ and } i\ne c\\ q_c,& q=q_0\text{ and } i=c\\ q_c,& q=q_c, \end{cases} $$ and $F=\{q_0\}$. Then $M$ is a deterministic finite automaton accepting the language $L$.

Answer 2

You can use the fact that regular languages are closed under intersection and the fact that the language $\{a,b\}^*$ is a regular language over the alphabet $\{a,b,c\}$. Now, if $L$ is a regular language over the alphabet $\{a,b,c\}$, then your language $L \cap \{a,b\}^*$ is also regular.