variable exponent in expression of a formal language

Question

Take a look at the following expression:

{(AⁿB)^m|n>0,m>0}

Or, to put it simply: the words in the language, have repeating parts consisting of, some A's followed by a single B.

There are TWO school of thoughts about this, which can be broken down, by this question:
Is the word ABAAB, a part of the language?

I say, that it's not, as each repeating part must have the same number (n) of A's in it.
Others claim that each repeating part can have it's own number of A's

I am willing to concede, that had the expression used +, instead of n>0, then each repeat, could have been different (although, I don't like this concession).

The question is: Is the variable in the inner part "locked", or can that variable have different values in each iteration of the part.

What I'd like, is a credible source that I can point to that explains which way is correct.

(ps, if my understanding of the expression is the correct one, it means the language is not regular; if I am wrong, it is regular).

Thank you all.

Answer 1

This is set-builder notation. The notation $\{ f(x_1,\ldots,x_\ell) : P(x_1,\ldots,x_\ell) \}$, for a function $f$ and a predicate $P$, is shorthand for the set $S$ such that $$ y \in S \Longleftrightarrow \exists x_1,\ldots,x_n (y = f(x_1,\ldots,x_\ell)) \land P(x_1,\ldots,x_\ell). $$ In words, an element $y$ belongs to $\{ f(x_1,\ldots,x_\ell) : P(x_1,\ldots,x_\ell) \}$ if and only if there exist $x_1,\ldots,x_\ell$ such that $y = f(x_1,\ldots,x_\ell)$ and $P(x_1,\ldots,x_\ell)$ holds. More formally, we need to specify what set the variables $x_1,\ldots,x_\ell$ are quantified over; in your case it is the integers.

In our quest to understand your set, we also need to know what the expression $(A^nB)^m$ means. We are working over the free monoid $\{A,B\}^*$ generated by $A,B$. We denote the product of two elements $x,y$ in the monoid by $xy$. For an element $x$ in the monoid, we define $x^n$ for natural numbers $n$ inductively: $x^0 = \epsilon$ ($\epsilon$ is the unit element of the monoid) and $x^{n+1} = x^nx$. Formally, there are also rules of precedence telling us how to parse the expression $(A^nB)^m$, though there isn't really much ambiguity in this case.

Following the inductive definition, we see that $A^nB$ consists of $n$ copies of $A$ followed by a copy of $B$, and that $(A^nB)^m$ consists of $m$ copies of $A^nB$. The set $\{(A^nB)^m : n,m>0\}$ consists of all words $w$ such that $w = (A^nB)^m$ for some natural $n,m$ satisfying $n>0$ and $m>0$. This is exactly your interpretation.

The above description is somewhat cursory - one can get even more formal. Most of this material is covered in basic courses on set theory and formal logic. The exception is the free monoid (usually not described in this way), which is covered in courses on formal languages.

For the record, I teach automata theory and formal languages in academia.

Answer 2

Whenever $m,n$ are chosen, there is only a single interpretation for $(A^nB)^m$. The variables are "locked" in the set builder notation $\{ \dots \mid m,n>0\}$. I mean, the string $(A^2B)^3$ equals $AABAABAAB$, there are no schools here.

If you want to have repetitions of variable length sequences of the form $A\dots AB$ then the regular expression $(A^*B)^*$ is appropriate.

The point here is that for each $m,n$ the $(A^nB)^m$ here is only a single object, not a set of strings (a language).

Consider the domain of natural numbers, which probably is better known. Let us analogously define the set $S = \{ (n+1)^m \mid m\ge 2,n>0\}$. Here it is quite clear that every $m,n$ is a single number, the $m$th power of a specific $n+1$. We would not consider choosing another $n$ for each multiplication. So we have $(2+1)(2+1)(2+1)\in S$ and not $(2+1)(5+1)(10+1)$.

The confusion is perhaps that in formal languages we consider both powers of single words and powers of languages. The $(A^*B)^*$ is an abbreviation for $\bigcup_{m\ge 0}\{ A^nB\mid n\ge 0\}^m$. In this case for any $m$ we compute the $m$th power of the language $\{ B, AB, AAB, AAAB, \dots \}$ which is the concatenation of $m$ copies of the language. Then we can choose a different string (i.e., a different $n$) in each term.

Another example that shows the difference between these confusing notations is the following. For a language $L$ its square is $L^2 = L\cdot L = \{ uv\mid u,v\in L\}$. This is the concatenation of two copies of $L$, and we may choose two diferent strings: $\{aa,b\}^2= \{aaaa,aab,baa,bb\}$. Squaring all words is different: $\mathrm{sq}(L) =\{ w^2 \mid w\in L \}$. Same example $\mathrm{sq}(\{aa,b\}) = \{aaaa,bb\}$.

But again, the formal reason is set builder notation, as in my first paragraph.