I've joined computer science classes at high school because I have a wide knowledge and a few years of experience in programming in multiple of languages, however I didn't fit in the requirements of the class, which is a specific mathematics level. I am a low level mathematics student, I don't really know formal mathematics or any proofs besides a simple proof like proving that an angle is 90 degrees.

So besides programming, there is this subject we started studying about finite deterministic automatons, stack automatons, turing machines and regular languages, etc.

I understand the concept very well, especially when it comes to building turing machines, finite and stack diagrams. At the class, we solve these automatons with diagrams, not in a formal way.

So besides that, my teacher gives us a lot of questions about union, intersection and I am getting really confused with intersection.

Surely I can understand the basic intersections with set of words:

$L = \{aab, bba, aa\}$ $L' = \{a, bbba, aab, aa\}$

So $L\cap L'$ would be $\{aab, aa\}$

I also understand basic language intersections like this:

$L = \{a^n b^n \mid n \ge 0\}$, $L' = \{a^n \mid n \ge 0\}$

$L\cap L'$ would be $\{a^n \mid n \ge 0\}$

But when it comes to something like this:

$L = \{a^{2n} b^m a^k \mid n,m \ge 0, k = m \mod 2\}$

$L'$ = set of string elements such that the length $|w|$ is even

$L\cap L'$ = I don't know the answer for

The second part of the language which defines the length of the elements (e.g on $n$, of $m$, of $k$) really confuses me in intersections and unions, I am not really sure why. Does that part matters in intersections? I am always getting lost in these cases.

How can I understand this concept a bit better mathematically?

  • $\begingroup$ This seems to be a mathematics question about operations on sets. $\endgroup$
    – Raphael
    Commented Feb 23, 2015 at 22:38
  • $\begingroup$ The intersection of two sets is the set of elements that are in both, so when $L = \{a^n b^n | n \geq 0\}$ and $L' = \{a^n | n \geq 0\}$, $L \cap L' = \{ e \}$. $\endgroup$ Commented Feb 23, 2015 at 22:42
  • 2
    $\begingroup$ The trick is to take the conjunction (i.e. and) of the conditions that define each of the sets. $\endgroup$
    – babou
    Commented Feb 24, 2015 at 0:41

1 Answer 1


In your last example, when trying to deduce $L \cap L'$, the trick is to trying to understand which strings in $L$ have even length. You can do this as follows:

$$L = \{a^{2n} b^m a^k | n,m >= 0, k = m \pmod 2\}.$$

We can forgot about the first substring of $a$'s, because they always come in pairs (or there are none. In either case, they contribute an even number of characters. Now consider $\{b^m a^k | m >= 0, k = m \pmod 2\}$. The length of the strings in this set is $m+k$. Since $k = m \pmod 2$, we have $m+k = m + m = 2m = 0 \mod 2$. Therefore, $m+k$ is always even, and so $b^m a^k$ always contributes an even number of characters as well. Since $even + even = even$, every string in $L$ is even. Therefore, $L \cap L' = L$.

  • 1
    $\begingroup$ I see, you basically break the whole thing to parts, to understand it better $\endgroup$
    – Ben Beri
    Commented Feb 23, 2015 at 22:21
  • $\begingroup$ Question, if you have this: W is string thats based on the binary elements {0, 1} L1 = {w starts with 0} L2 = {w starts with 00} So L1 intersects L2 = Ø ? $\endgroup$
    – Ben Beri
    Commented Feb 23, 2015 at 22:32
  • $\begingroup$ No, that's not true. Any string in $L_2$ will also be in $L_1$; if a string starts with a $00$, then clearly it's first bit is a $0$, and so it's in $L_1$ too. All you can say is that $L_2 \subset L_1$. $\endgroup$
    – MarkG
    Commented Feb 23, 2015 at 22:38
  • $\begingroup$ How are these set definitions called when I have them defined like {a^n b^m } and so on? I want to find more online information about it $\endgroup$
    – Ben Beri
    Commented Feb 23, 2015 at 23:08
  • $\begingroup$ They are regular languages. I suggest you read this book. $\endgroup$
    – MarkG
    Commented Feb 23, 2015 at 23:24

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.