1
$\begingroup$

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\}$

Improve this question
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ – Marie.L Feb 20 '19 at 11:37
  • $\begingroup$ I mean $L(b^*c^*)$ \ $\{\epsilon\}$ $\endgroup$ – Marie.L Feb 20 '19 at 11:50
  • $\begingroup$ $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. $\endgroup$ – John L. Feb 20 '19 at 14:24
  • $\begingroup$ "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. $\endgroup$ – John L. Feb 20 '19 at 14:29
  • $\begingroup$ 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}\}$ $\endgroup$ – Marie.L Feb 20 '19 at 14:41

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.