This is tangentially related to a question I asked on the math stackexchange.

I read in a proof that if

$$ \begin{align*} L_1 &= \{w ∈ \{a, b, c\}^* : \text{$w$ has the same number of $a$, $b$, and $c$} \}, \\ R &= L(a^* b^* c^*), \end{align*} $$

then $L ∩ R = \{a^nb^nc^n: n ≥ 0\}$.

Now unless I'm fundamentally misunderstanding intersection, why is the intersection between this language and the regular set is $a^nb^nc^n$ and not something like $a^ib^jc^k$ where $i,j,k \geq 0$? Is $R$ not the set including strings like abbccc or aaabbc?

  • $\begingroup$ A word like $abbccc$ would only be in the intersection of $L1$ and $R$ if it was in both $L1$ and in $R$. $abbccc$ is not in L1, because it has a different number of a's, b's and c's (1 a, 2 b's and 3 c's). $\endgroup$ May 7 '17 at 7:45
  • $\begingroup$ @BoltonBailey and here I was looking up the properties of the kleene star. thanks $\endgroup$
    – pajkatt
    May 7 '17 at 7:48
  • $\begingroup$ @BoltonBailey Make an answer? $\endgroup$ May 7 '17 at 11:49

Because $A\cap B = \{x\mid x\in A\text{ and }x\in B\}$.


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.