Results 1 to 7 of 7

Math Help - Star Operator and Grammer

  1. #1
    Member
    Joined
    Sep 2007
    Posts
    222

    Question Star Operator and Grammer

    I am not sure if this is where I can get help for it but I thought its worth a try.

    Prove that L = {a^n: n is a prime number} is not regular

    I was looking through the solution to it but don't understand it at all, could anyone help explain how to solve it?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by taurus View Post
    I am not sure if this is where I can get help for it but I thought its worth a try.

    Prove that L = {a^n: n is a prime number} is not regular

    I was looking through the solution to it but don't understand it at all, could anyone help explain how to solve it?

    Thanks
    I don't have much experience with this but I believe the pumping lemma directly applies. Based on the informal definition, if L is regular then by pumping lemma there exist integers m and n such that n > 1 and m > 0 and n + km is prime for any positive integer k, which can be disproven by letting k = n.
    Last edited by undefined; September 18th 2010 at 07:41 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2007
    Posts
    222
    n > 1 and m > 0 and n + km is prime for any positive integer k, which can be disproven by letting k = n

    Thats where I lost it, what is m? and why did you say n + km?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by taurus View Post
    n > 1 and m > 0 and n + km is prime for any positive integer k, which can be disproven by letting k = n

    Thats where I lost it, what is m? and why did you say n + km?
    So I was going based off of the informal definition, assuming "between" means there are non-empty strings on either side, and that the pumped substring had to appear at least once. Since this is not the case, a better statement would be

    there exist integers m and n such that n \ge 0 and m > 0 and n + km is prime for any non-negative integer k...

    So we have word of length p, call it w = xyz with variables named according to the pumping lemma @ Wikipedia. x and z are allowed to be empty; call their combined length n. The length of y must be nonzero, call it m. We can repeat y as many times as we want; if we repeat k times, the length of the word is n + km, and this word must be in the language by the lemma. Thus n + km is prime for all non-negative integers k, which we will prove is false. Not having n > 1 makes it slightly more work but not much.

    If n < 2 let k = 0, which gives a contradiction since neither 0 nor 1 is prime.

    If n > 1 let k = n, then n + km = n + nm = n(1 + m) which is greater than n and divisible by n, thus not prime.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2007
    Posts
    222
    AHH ok makes much more sense, I would just be confused on the km, I think I would have done m^k
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by taurus View Post
    AHH ok makes much more sense, I would just be confused on the km, I think I would have done m^k
    Ah, it's just that k, m, and n are integers, not words.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Suppose there existed a finite automaton that recognizes exactly that language, let N be the number of distinct states in it.

    Consider \epsilon=a^0,a^1,...,a^N , 2 of these must be in the same state (by pidgeonhole principle), that is a^i is in the same state as a^j for some 0\leq i<j\leq N (*).

    Now pick an arbitrary prime p\geq i , we have that since a^p is accepted, then so is a^{p + j-i} by (*) since a^{p-i}a^i and a^{p-i}a^j must be on the same state. So that for the difference between 2 consecutive primes we have \lim\sup {(p_{k+1}-p_ k)} \leq j-i ABSURD!

    Why? Because n!+2,...,n!+n are all composite, and you can picked n as large as you want. - so we can alwas find a pair of prime numbers (such that there's no other prime between them) such that the difference between them is as large as you want.

    Note: We could also have said that a^{p+r\cdot (j-i)} are accepted for all r in \mathbb{N} and pick r=p to get a contradiction

    In general, if you have an increasing sequence b_k of non-negative integers such that \lim\sup (b_{k+1}-b_k)=+\infty then the language L=\{a^{b_k}\text{: }k\in\mathbb{N}\} is not regular.

    So for example, this same trick applies to sequences like b_k =k^2 .
    Last edited by PaulRS; September 20th 2010 at 11:50 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Magic Star
    Posted in the Math Puzzles Forum
    Replies: 5
    Last Post: March 9th 2012, 11:55 AM
  2. Replies: 1
    Last Post: February 7th 2011, 02:41 AM
  3. Check this Grammer Please
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 15th 2010, 06:11 PM
  4. grammer problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 29th 2008, 09:32 PM
  5. star
    Posted in the Algebra Forum
    Replies: 7
    Last Post: August 10th 2006, 07:38 PM

Search Tags


/mathhelpforum @mathhelpforum