# Difference between $L_1 = \{(a^n b^n)^m \mid n, m \ge 1\}$ and $L_2 = \{a^n b^n \mid n \ge 1\}^+$

Is there any difference between saying $$L_1 = \{(a^n b^n)^m \mid n, m \ge 1\}$$ with $$L_2 = \{a^n b^n \mid n \ge 1\}^+$$?

I know that for $$v = abab$$ we have $$v \in L_1$$ and $$v \in L_2$$

my understanding is that there is no difference between them and for $$w = abaaabbb$$ we have $$w \in L_1$$ and $$w \in L_2$$ . but I have a feeling that maybe $$w \notin L_1$$, because it doesn't have the same $$n$$ for different $$a^n b^n$$.

Also, does the same apply for Kleene star $$*$$ too? for example if we have $$L_3 = \{(a^n b^n)^m \mid n \ge 1, m \ge 0\}$$ and $$L_4 = \{a^n b^n \mid n \ge 1\}^*$$, Are $$L_3$$ and $$L_4$$ equal?

## 1 Answer

Indeed, $$abaaabbb \notin L_1$$ because the string is not of the form $$(a^nb^n)^m$$ which is the repetition of a fixed string with the same number of $$a$$ and $$b$$.

The language $$L_2$$ is the Kleene closure of $$\{a^nb^n \mid n\ge1\}$$, consisting of all arbitrary concatenations of strings of the form $$a^nb^n$$. We can choose different strings of this form, and do not have to stick with the same one each time, like in $$L_1$$. Hence $$L_2$$ contains $$abaaabbb$$.

As for your original version of the question (now edited) it contained the notation $$\{(a^nb^n)^+ \mid n\ge1\}$$. I would not denote a language that way. The Kleene plus is a language operator, which takes a language (set of strings), and turns it into a language. By writing $$\{(a^nb^n)^+ \mid n\ge1\}$$ you get the set $$(a^nb^n)^+$$ within the set brackets, which can be called a "type error".

• Thanks! I changed the question to the correct form so people with the same problem can search and find the answer. – Automata Feb 8 at 1:25