0
$\begingroup$

Let $B$ and $C$ be two languages on $A = \{a,b\}$:

$B = \{ w \mid w \text{ has the same number of }a\text{ and }b\text{ symbols}\}$
$C = \{ a^n b^m \mid n,m \ge 0\}$

Describe $B \cap C$ and determine whether $B$ is regular or not using only the closure property of regular languages.

I reasoned like this:

$B$ is not regular because a language is regular if there exists a DFA $M$ such that $L = L(M)$. But we know that DFAs cannot count so $B$ is not a regular language.

$$B \cap C = \{a^n b^m \mid n=m \land n,m \ge 0\}$$

which we know is not regular by the pumping lemma.

Is there a different solution using only closure properties to prove that $B$ is not regular?

$\endgroup$
8
  • $\begingroup$ What exactly is the question? Please specify exactly what your question is, and edit your question to remove the parts that are not relevant to that specific question. You don't need to show us all of the parts of the question if you are asking about only one part. $\endgroup$
    – D.W.
    Commented Dec 20, 2023 at 20:54
  • $\begingroup$ @greybeard C is regular because there isn't a condition about counting a and b. However, B ∩ C is not regular according to the pumping lemma. Is there another way to prove it using only closure properties?" $\endgroup$
    – Luca
    Commented Dec 21, 2023 at 9:59
  • $\begingroup$ @D.W Sorry, I am a new user and I still learning the rules to write a correct question. $\endgroup$
    – Luca
    Commented Dec 21, 2023 at 10:01
  • $\begingroup$ @greybeard B∪C is regular due to the closing properties of regular languages $\endgroup$
    – Luca
    Commented Dec 21, 2023 at 10:33
  • $\begingroup$ Sorry, my fault: You know $C$ to be regular. Assume $B$ was regular: What results for $B \cap C$? $\endgroup$
    – greybeard
    Commented Dec 21, 2023 at 10:43

1 Answer 1

1
$\begingroup$

You are part of the way there.

You are expected to use the closure properties to show whether $B \cap C$ is regular depending on whether $B$ and $C$ are regular. You're not doing that. Closure properties are properties such as:

  1. If $A$ is regular, then $\bar A$ (= $\Sigma^* - A$) is regular.
  2. If $A$ and $B$ are regular, then $A \cup B$ and $A \cap B$ are regular.

Your proof will depend on whether $C$ is regular, so you will need to determine that, too.

$\endgroup$

Your Answer

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

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