I know that if a language $L_1$ and a language $L_2$ are regular, then $L1/L2$ is regular.

When we construct a DFA $M'=(Q, \Sigma, \delta, q_0, F)$, for each state $i$ we can make $i$ the start state (we'll represent is using $L'i$) and if $L'i \cap L_2 \neq 0$ then put $q_i$ in $F'$ in $M'$.

I understand the process of constructing an automaton M if both languages are regular, but what if L1 is regular but L2 is any language? How would I construct an automaton for this?

Thank you!

  • $\begingroup$ What does $L'i$ denote? $\endgroup$
    – DylanSp
    Feb 15, 2016 at 14:22
  • $\begingroup$ Also, any finite language is regular, so the question as it stands is a finite regular language and another, not necessarily regular language. (Just checking this is what you mean) $\endgroup$ Feb 15, 2016 at 14:24
  • $\begingroup$ @LukeMathieson you are right, correct with those two, let me fix it up. So if L1 is a regular language and L2 is any language, not necessarily regular $\endgroup$ Feb 15, 2016 at 14:31
  • $\begingroup$ @DylanSp sorry, let me specify that. When I make i the start state, that's representing Li'. $\endgroup$ Feb 15, 2016 at 14:35
  • 5
    $\begingroup$ Actually, I did some better searching and I am guessing the answer to this question (they asked more questions in one post, but just look at the top paragraph) would answer what I am asking cs.stackexchange.com/questions/34006/… . Correct? Should I delete my question then? (Wanting to check on the proper etiquette :) ) $\endgroup$ Feb 15, 2016 at 14:42


Browse other questions tagged or ask your own question.