## #math - Thu 8 Mar 2007 between 03:04 and 03:16

### NY Lost Funds

 odiomundum_ after someone saying it's simple to assume you have n states and k > n thermoplyae Okay, so you'll have to bear with me that 0^k 1^k is irregular if you haven't proved it before for yourself odiomundum_ k thermoplyae Obviously the Kleene star of {0, 1} is all possible strings, and so if we take the union of {0, 1} and {0^k 1^k | k \in N} we'll get nothing less than all possible strings(under the Kleene star, I mean)And the union of a finite language and an irregular language is irregular, since regular languages are closed under complementation odiomundum_ okay thermoplyae (and other mess)And so {0, 1} \cup {0^k 1^k | k \in N} is irregular, but it's Kleene star is the universal set, which is regularThereDone odiomundum_ \cup? thermoplyae union odiomundum_ oh okay\in? lol kmh where have all the ops gone ? thermoplyae \in - element of odiomundum_ oh okay kmh splits have killed them one by one odiomundum_ i just attempted to show that 0^k 1^k is irregulartell me if this makes any sensei said n = 5 kmh odiomundum : or just in the set kinda odiomundum_ yea i understand element of|z| >= n so i said |z| = 5 and z = uvw with u = 0^3, v = 0, w = 1then said that uv^iw should be true for all i >= 00^30^i1 for all i>= 0 thermoplyae I think you're getting your "for all"s and "there exist"s confused odiomundum_ and that's not true because just at i = 0, there's 0^3 and only 1^1 thermoplyae And whether or not you get to actually pick a value for the lower bound on the pumping lemma(you don't) odiomundum_ i just seriously do not understand the pumping lemma lolit just says in my book you pick an n and then it has to meet the requirements|z| >= n, and z = uvw so that |uv| <= n and |v| >= 1 then uv^iw for all i>=0 should be in L thermoplyae Instead, let p be the bound given to us by the pumping lemma. Then consider the string 0^p 1^p. If the pumping lemma were to hold for L, then we could divide up the string into x, y, z such that x = 0^(p-k), y = 0^k, z = 1^p odiomundum_ if it's not, then L is irregular thermoplyae And x y^i z must be in the setBecause for i = 2 we have 0^(p+k) 1^p, which is not in the set, the pumping lemma fails, and so L must not be regularWith lots of /correct/ PL practice you'll learn to get it right clarity_ hrm... just to make sure i'm correct.. Say we have D_n where ba=(a^1)b the smallest subgroup of D_4 that contains both a^2 and b would be { e, a, a^2, a^3, b, ab, (a^2)b, (a^3)b, ba^2 }