1
$\begingroup$

I have a question that says that the complement of a regular language given as: $L_1=\{a^nb^m|(n+m)<5\}$ is $L_2=\{a^nb^m|(n+m)\geq5\}$ over $\Sigma=\{a,b\}$, and therefore, we can simply construct finite automaton (FA) of $L_2$ by simply interchanging the accepting and non-accepting states of $L_1$ .

However, as per my understanding if I define the complement as: $$\bar{L}=\Sigma^*-L$$ where $\sum^*$ is every possible string, then $L_2$ can't be a complement of $L_1$ as there must also be strings that do not have order $b$ after $a$.

The given approach may work for languages like $L_3=\{w|w~\text{has an odd number of a's}\}$ and $L_4=\{w|w~\text{has an even number of a's}\}$, as disjoint sets lead to $\Sigma^*=L_3+L_4$. However, as per my understanding, this logic will not work to derive FA for $L_2=\{a^nb^m|(n+m)\geq5\}$ from FA of $L_1=\{a^nb^m|(n+m)<5\}$.

Am I correct? Or the definition of complement is different from my understanding.

$\endgroup$

1 Answer 1

1
$\begingroup$

You are correct. The definition of the complement is exactly what you wrote, and indeed it is not true to say that $L_2$ is the complement of $L_1$. However, changing the accepting and non-accepting states is in fact a correct way to generate a finite automaton for the complement language, so I think whoever wrote $L_2$ just miss-typed. It won't make a difference for the solution, so just substitute the correct complement instead of $L_2$ wherever you need to.

$\endgroup$
3
  • $\begingroup$ You mean to say that if I have an automaton for $L_1$ and I interchange its accepting and non-accepting states, then I will not get a finite automaton corresponding to $L_2$? Correct? Please check I have edited the question to correct any further ambiguity. $\endgroup$
    – Userhanu
    Sep 30, 2021 at 9:27
  • 1
    $\begingroup$ Thats correct. Swapping accepting with non-accepting will create an automaton for $\overline{L_1}$ and not for $L_2$. $\endgroup$
    – nir shahar
    Sep 30, 2021 at 10:23
  • 1
    $\begingroup$ You can try this for yourself, and see if $ba$ is accepted by that. $\endgroup$
    – nir shahar
    Sep 30, 2021 at 10:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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