#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
thermoplyaeOkay, 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
thermoplyaeObviously 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 regular
There
Done
odiomundum_\cup?
thermoplyaeunion
odiomundum_oh okay
\in? lol
kmhwhere have all the ops gone ?
thermoplyae\in - element of
odiomundum_oh okay
kmhsplits have killed them one by one
odiomundum_i just attempted to show that 0^k 1^k is irregular
tell me if this makes any sense
i said n = 5
kmhodiomundum : 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 = 1
then said that uv^iw should be true for all i >= 0
0^30^i1 for all i>= 0
thermoplyaeI 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
thermoplyaeAnd 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 lol
it 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
thermoplyaeInstead, 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
thermoplyaeAnd x y^i z must be in the set
Because 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 regular
With 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 }

Page: 2 9 16 23 30 37 44 

IrcArchive

NY Lost Funds