Fix a finite alphabet -- let's take it to be {0,1} for simplicity. A language L is a collection of finite strings over {0,1}, i.e., L is a subset of {0,1}^*.
Let U be a family of languages. We say that U is closed under an operation if applying the operation to members of U always yields members of U. Suppose U is closed under concatenation -- that is, if L_1 and L_2 are in U then so is L_1 L_2 (the set of all strings with prefix in L_1 and suffix in L_2).
A student claimed in a homework problem that if U is closed under concatenation then it is closed under the star operation (L^* is the set of all strings obtained by concatenating n members of L, for n=0,1,2,...).
Is this true? Answers/discussion welcome in comments!
Subscribe to:
Post Comments (Atom)
13 comments:
A grating misnomer I encountered a number of times while grading was "concatenation is closed", and the like. It's not the operation that's closed -- rather, the set is closed under an operation.
Surely U can be closed under concatenation without including the empty string?
Ack, you have an even simpler counterexample than what I had in mind!.. OK, let's suppose that U does contain the empty string. How about now?
...and of course jks meant that U is a subset of {0,1}^+, meaning no language in U is allowed to contain the empty string -- right?
My original question can (should) be reformulated like this: if a family of languages U is closed under concatenation, is U necessarily closed under the ^+ operation (which is just like the star except that empty concatentions are not allowed)?
isn't that just induction?
but regarding the counterexample of the language containing the empty string, the student may have had another meaning of "closed under concatenation" in mind. For example, in category theory one says that a category U "has *binary* products" if for any two objects in U, their product is also in U. One says that it "has *finite* products" if there is a product object in U corresponding to any finite (possibly empty) collection of objects in U, and finally one says that it "has products" if there is a product object in U corresponding to any arbitrary (possibly infinite) collection of objects in U. So "closed under concatenation" might be taken to mean closed under concatenation of any collection of languages in U, in which case it would imply star closed.
However strange it may sound at first glimpse, the student's statement appears to be true. What about the following (roughly sketched) proof:
Let U be a family of languages and let's fix one language L in U. Because U is closed under concatenation we easily deduce that the family U_L = {LN | LN = L^n for some n} of all iterations of L is a subset of U (induction). The elements of U_L are linearly ordered (with respect to the set-prefix relation) so U_L is a complete lattice. Now consider the function f_L: U_L -> U_L which appends (concatenates) L to its argument. Clearly it preserves the order and doesn't leave U_L. By Knaster-Tarski's theorem it should have a least fixed point in U_L and this LFP is obviously L^*. Therefore L^* belongs to U (U_L is a subset of U) which finally means that U is closed under the star operation.
What do you think?
oops, ignore most of what I wrote above...
Ivan, I don't think that proof works. At best, you have that the least fixed point of f_L is the language L^∞ = {LLL...}, which is different from L^*. I think what is missing is that U be closed under (infinite) union.
So the counterexample I had in mind is where U is the class of the finite languages. It's certainly closed under concatenation, and certainly not under star. I'll have to save debugging Ivan's proof later -- gotta run to administer a midterm!
sorry if my second post wasn't clear -- what I meant was, "ignore the part in my first post where I said that concatenation closed implies star closed, because it doesn't". The hypothesis that U is closed under finite concatenation only implies that U is star closed if, in addition, U is closed under infinite union.
Noam -- that's exactly right. It's analogous to the difference between finite and countable additivity in measure theory.
Here's an easy one (unless I'm bungling something up) -- does closure of U under star imply closure under concatenation?
U = { L0, L1 } where Li = L(i^*) = {i^n | n is natural} for i = 0,1
Nicely done, Ivan. It's a simple example but this stuff can get confusing (especially if one forgets that U is not a language but a family of languages). I actually had the wrong answer to this originally (which I won't describe to avoid injecting further confusion into the thread).
Noam wrote:
Ivan, I don't think that proof works. At best, you have that the least fixed point of f_L is the language L^∞ = {LLL...}, which is different from L^*. I think what is missing is that U be closed under (infinite) union.
What exactly is L^∞ ? I can't imagine constructing one...
Leo wrote:
So the counterexample I had in mind is where U is the class of the finite languages. It's certainly closed under concatenation, and certainly not under star. I'll have to save debugging Ivan's proof later -- gotta run to administer a midterm!
If U were finite languages and L is in U, then L* is an infinite set of languages, but I don't see why each member of that infinite set of languages would not itself be a finite language. What exactly is the problem with Ivan's proof above?
Post a Comment