patternMinor
variable exponent in expression of a formal language
Viewed 0 times
expressionexponentformallanguagevariable
Problem
Take a look at the following expression:
{(AnB)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.
{(AnB)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.
Solution
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.
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.
Context
StackExchange Computer Science Q#90612, answer score: 4
Revisions (0)
No revisions yet.