Formal proving of languages accepted by a finite automata.

419 Views Asked by At

Suppose $L_1 \cup L_2,L_1 \subseteq E^* $ are languages accepted by finite automata and $L_1\cap L_2 =\emptyset $. We need to prove that $L_2 $ is also accepted by a finite automaton.

So I've started with building an intuition, but I have a few questions.

  1. Say I've found an automaton presumably representing a language. What's the proper way of proving that it actually is a representation of the language?

  2. Is it enough to prove that, given all of the above, $L_2$ has a regular expression (since both $L_1 \cup L_2$ and $ L_1$ should have regular expressions)? Or is that a wrong way of looking at this kind of question?

1

There are 1 best solutions below

2
On BEST ANSWER

If a language $M$ is regular, then $\overline{M}=E^*\setminus M$ is regular too. Therefore $$ L_2=\overline{\overline{L_1\cup L_2}\cup L_1} $$ is regular.