0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This seems to be a mathematics question about operations on sets. $\endgroup$ – Raphael Feb 23 '15 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$ – reinierpost Feb 23 '15 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 Feb 24 '15 at 0:41
4
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ I see, you basically break the whole thing to parts, to understand it better $\endgroup$ – Ben Beri Feb 23 '15 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 Feb 23 '15 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 Feb 23 '15 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 Feb 23 '15 at 23:08
  • $\begingroup$ They are regular languages. I suggest you read this book. $\endgroup$ – MarkG Feb 23 '15 at 23:24

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.