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 regular There Done |

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 irregular tell me if this makes any sense i 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 = 1 then said that uv^iw should be true for all i >= 0 0^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 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 |

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 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 } |