1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

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

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.