Take a look at the following expression:


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.


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.

| cite | improve this answer | |

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.

| cite | improve this answer | |
  • $\begingroup$ yes, this is my understanding as well. my problem is ... where is this written? $\endgroup$ – Eyal Lev Apr 12 '18 at 22:13
  • 1
    $\begingroup$ (replying after your edit of the answer) the people I need to convince are computer science teachers, that have been teaching this subject for over 5 years. just telling them "some guy on stack exchange said so" will not do. they claim that each of the 3 iterations, can have a different "n". $\endgroup$ – Eyal Lev Apr 12 '18 at 22:17
  • 1
    $\begingroup$ Only five years? They are young enough to have been at one of my classes, but probably did not pay attention. Sorry, Lets be serious. I understand your situation, and try to extend my answer with some relevant remarks. $\endgroup$ – Hendrik Jan Apr 14 '18 at 14:04

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.