tag:blogger.com,1999:blog-2811876938195306723.post6997860532916900090..comments2023-07-07T01:27:13.382-07:00Comments on Absolutely Regular: Concatenation implies star?Aryehhttp://www.blogger.com/profile/14913393383227385317noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-2811876938195306723.post-49467596665121687992007-03-14T14:04:00.000-07:002007-03-14T14:04:00.000-07:00Noam wrote: Ivan, I don't think that proof works. ...Noam wrote: <BR/><I><BR/>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.</I><BR/><BR/>What exactly is L^∞ ? I can't imagine constructing one... <BR/><BR/>Leo wrote:<BR/><I>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! </I><BR/><BR/>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?bclark76https://www.blogger.com/profile/15651064487051288710noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-66963436983531365302007-02-16T04:31:00.000-08:002007-02-16T04:31:00.000-08:00Nicely done, Ivan. It's a simple example but this ...Nicely done, Ivan. It's a simple example but this stuff can get confusing (especially if one forgets that U is not a <I>language</I> but a <I>family</I> of languages). I actually had the wrong answer to this originally (which I won't describe to avoid injecting further confusion into the thread).Aryehhttps://www.blogger.com/profile/14913393383227385317noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-79408227558306638942007-02-16T02:42:00.000-08:002007-02-16T02:42:00.000-08:00U = { L0, L1 } where Li = L(i^*) = {i^n | n is nat...U = { L0, L1 } where Li = L(i^*) = {i^n | n is natural} for i = 0,1Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-26087035519027919782007-02-15T18:38:00.000-08:002007-02-15T18:38:00.000-08:00Noam -- that's exactly right. It's analogous to th...Noam -- that's exactly right. It's analogous to the difference between <I>finite</I> and <I>countable</I> additivity in measure theory.<BR/><BR/>Here's an easy one (unless I'm bungling something up) -- does closure of U under star imply closure under concatenation?Aryehhttps://www.blogger.com/profile/14913393383227385317noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-46051358131374341272007-02-15T13:11:00.000-08:002007-02-15T13:11:00.000-08:00sorry if my second post wasn't clear -- what I mea...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.Unknownhttps://www.blogger.com/profile/08267082150222777180noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-73080990083665668032007-02-13T10:27:00.000-08:002007-02-13T10:27:00.000-08:00So the counterexample I had in mind is where U is ...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!Aryehhttps://www.blogger.com/profile/14913393383227385317noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-91441695152541978482007-02-13T08:45:00.000-08:002007-02-13T08:45:00.000-08:00oops, ignore most of what I wrote above...Ivan, I ...oops, ignore most of what I wrote above...<BR/><BR/>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.Unknownhttps://www.blogger.com/profile/08267082150222777180noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-1835088866483510842007-02-13T03:15:00.000-08:002007-02-13T03:15:00.000-08:00However strange it may sound at first glimpse, the...However strange it may sound at first glimpse, the student's statement appears to be true. What about the following (roughly sketched) proof:<BR/><BR/>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.<BR/><BR/>What do you think?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-36918972167242194932007-02-12T22:43:00.000-08:002007-02-12T22:43:00.000-08:00isn't that just induction?but regarding the counte...isn't that just induction?<BR/><BR/>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.Unknownhttps://www.blogger.com/profile/08267082150222777180noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-52673231537845489892007-02-12T10:38:00.000-08:002007-02-12T10:38:00.000-08:00...and of course jks meant that U is a subset of {......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?<BR/><BR/>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)?Aryehhttps://www.blogger.com/profile/14913393383227385317noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-81120951539341524582007-02-12T09:08:00.000-08:002007-02-12T09:08:00.000-08:00Ack, you have an even simpler counterexample than ...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?Aryehhttps://www.blogger.com/profile/14913393383227385317noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-78485353925137050272007-02-12T04:28:00.000-08:002007-02-12T04:28:00.000-08:00Surely U can be closed under concatenation without...Surely <I>U</I> can be closed under concatenation without including the empty string?Jouni Seppänenhttps://www.blogger.com/profile/16069683652129533073noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-4009209540463733552007-02-12T01:33:00.000-08:002007-02-12T01:33:00.000-08:00A grating misnomer I encountered a number of times...A grating misnomer I encountered a number of times while grading was "concatenation is closed", and the like. It's not the <I>operation</I> that's closed -- rather, the <I>set</I> is closed under an operation.Aryehhttps://www.blogger.com/profile/14913393383227385317noreply@blogger.com