# How can I create a language using set operation to prove a language is not regular?

My goal is to show, that a given language is not a regular one by using the Properties of Regular Languages.

The language is $$A \triangleq\left\{w \in \Sigma^{*} \mid |\left.w\right|_{b} \neq|w|_{c} \wedge|w|>0\right\}$$ with $$\Sigma \triangleq\{a, b, c\}$$

My idea is to use this clearly non regular language (which is given in the task, so I can/should use it) $$\left\{b^{n} c^{n} | n \in \mathbb{N}\right\}$$ to prove $$A$$ is also no regular language.

Could the following work?

$$(A\cap L(b^*c^*)) \cdot \mathrm{L}(\boldsymbol{\epsilon}) = \left\{b^{n} c^{n} | n \in \mathbb{N}\right\}$$

It looks like you are onto the right track. However, your notation is confusing me.

I would believe the following is what you are coming at.

$$\overline{(A\cap L(b^*c^*))} \cup \{\epsilon\} = \left\{b^{n} c^{n} \mid n \in \mathbb{N}\right\}$$ where $$\overline S$$ is the language of words not in $$S$$, a.k.a. the complement of $$S$$. Here are the facts that you will use.

• $$b^*c^*$$ is a regular expression.
• the intersection of two regular languages is regular.
• the complement of a regular language is regular.
• $$\{\epsilon\}$$ is a regular language.
• the union of two regular languages is regular.
• $$\{b^{n} c^{n} \mid n \in \mathbb{N}\}$$ is not regular.

I will leave the rest of reasoning to you.

• Hey, thanks for your answer. But there are two problems: First, I should not use the complement, because our proof did not mentioned it, so there is no proof for that. Second, this here $(A\cap L(b^*c^*))$ should look like $L(b^*c^*) \ \{\epsilon\}$ right? So we just need to add the empty word, right? So is there a use for the complement in this case? I believe withe the complement the language is not right. But I'am just i my first year on university, so I'm maybe wrong. Feb 20, 2019 at 11:37
• I mean $L(b^*c^*)$ \ $\{\epsilon\}$ Feb 20, 2019 at 11:50
• $A$ is the language of words with unequal number of $b$'s and $c$'s. $L(b^*c^*)$ is the language of words that are zero or more $b$'s followed by zero or more $c$'s. The intersection of them is the words that are some number of $b$'s followed by a different number of $c$'s. Feb 20, 2019 at 14:24
• "I should not use the complement". If so, I cannot see the fact "$\{b^{n} c^{n} \mid n \in \mathbb{N}\}$ is not regular." can be useful. There are, of course, many other ways to prove $A$ is non-regular. Feb 20, 2019 at 14:29
• I'm sorry I can use the complement, I saw it 5 minutes ago. But I have a question, can I just use the complement of $A$ and to this : $\overline{(A))} \cap L(b^*c^*) = \{b^{n} c^{n} \mid n \in \mathbb{N}\}$ Feb 20, 2019 at 14:41