I want to ask a question. How can I prove that languages are regular? Do I need to draw finite automata in order to prove or disprove?

Question: Assume that $L_1$ and $L_1 \cup L_2 \cup L_3 $ are regular languages. Is $L_2L_3$ necessarily a regular language? Prove by construction or disprove by counterexample.

  • $\begingroup$ Well to disprove it you can't find an automaton, you have to provide an example of languages that satisfy the property but such that the conclusion is not satisfied. To prove it you can either build the automaton, or use the closure properties of regular languages $\endgroup$ – Max Mar 16 '17 at 20:50
  • $\begingroup$ What is L2L3? Is it the concatenation of L2 and L3? (That is, the set of words $xy$ such that $x$ is in L2 and $y$ is in L3? $\endgroup$ – Fabio Somenzi Mar 16 '17 at 20:53
  • $\begingroup$ @FabioSomenzi, Yes, it is the concatenation of L2 and L3 $\endgroup$ – sbk Mar 16 '17 at 20:54
  • $\begingroup$ @Max how can I build the automaton? I don't know how I can prove by the automaton way. $\endgroup$ – sbk Mar 16 '17 at 20:57
  • $\begingroup$ Then ask yourself what the closure properties tell you about $L_2 \cup L_3$ and whether knowing something about the regularity of $L_2 \cup L_3$ lets you conclude about the regularity of $L_2L_3$. $\endgroup$ – Fabio Somenzi Mar 16 '17 at 21:02

To prove that a language $L$ is regular, there are 3 ways:

  1. Build a finite (deterministic or non-deterministic) automaton $M$ such that the language accepted by $M$ is equal to $L$;
  2. Build a regular expression for $L$;
  3. Use closure-properties, combine steps 1,2.

As far your question is concerned, there is a trivial solution: let $L_1$ be the set of all strings over the input alphabet, say $\{a\}^*$; now make $L_2L_3$ a non-regular language, for example, $L_2=\{a\}$ and $L_3=\{a^{p-1}: \text{p is prime}\}$.

It might be more interesting to solve the problem with $L_1=\emptyset$; that is, find $L_2,L_3$ such that $L_2 \cup L_3$ is regular and $L_2L_3$ is not regular.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.