Pumping lemma for regular languages

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

NaYoN
Posts: 8
Joined: Fri Mar 07, 2008 5:53 pm UTC

Pumping lemma for regular languages

Postby NaYoN » Sun Mar 22, 2009 3:26 pm UTC

Hello all, I have a problem with the pumping lemma.

I've been challenged to show the following isn't regular using the pumping lemma, but I'm stuck. I have a few ideas, but it's been quite a while since I've worked on this so I'm not sure whether they are correct.

The set of languages where the length of strings is the k th perfect power of an integer, for all k > 1.

I can prove its complement is not regular and show this isn't regular through closure, bu I can't do this by the pumping lemma.

I feel like I should use a factorial to denote the cycle, and pump it n times where n = (the thing I found) / k, which would make it the power of an integer, which would mean it breaks the condition and dissatisfies the lemma showing it isn't regular.

It probably should be something like p! - p or the likes of it.

I also tried to define some prime q > (a function of p), but I couldn't take that too far, since I couldn't go the "power of an integer" way.

Can anyone bounce ideas with me, so that we can get something going to work this out? I'm willing to put more effort into this to solve it, but I'm just not sure about the workings of the lemma anymore, and the definition on the wiki isn't helping either. Right now I'm wishing I hadn't thrown away my class notes from Automata Theory :(

Thanks in advance, guys.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Pumping lemma for regular languages

Postby Yakk » Sun Mar 22, 2009 5:16 pm UTC

What course and school is this for, and what professor? :) (I'm presuming you will cite all of the help you get, so this shouldn't be a problem, right?)

http://en.wikipedia.org/wiki/Pumping_le ... _languages

As a hint, what you care about is the length of the string, right?

First, reduce it to a simple case -- the case where your language contains one symbol.

Now restate the Pumping lemma for regular languages in this context.

Now restate both in terms of numbers -- restate your language in terms of numbers (no strings mentioned), and the pumping lemma in terms of numbers. Note that once remapped to numbers (and they no longer pay attention to the structure of the strings), the statements should get simpler.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

NaYoN
Posts: 8
Joined: Fri Mar 07, 2008 5:53 pm UTC

Re: Pumping lemma for regular languages

Postby NaYoN » Mon Mar 23, 2009 9:42 am UTC

Nevermind,I solved it.

If w= 0^( p^k - p! ), and we pump up i times where i = ( p!/s + 1 ), we get 0^( p^k - p! + (i - 1)*s ), which reduces to 0^p^k, which is a perfect kth power, which is not in the language, and thus by the lemma, the language is not regular.

It wasn't for any course, it was for a beer, and I got it!

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Pumping lemma for regular languages

Postby Yakk » Mon Mar 23, 2009 1:23 pm UTC

Why is 0^( p^k - p! ) in the language "The set of languages where the length of strings is the k th perfect power of an integer, for all k > 1."?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Mach1ne
Posts: 35
Joined: Tue Feb 24, 2009 5:20 pm UTC
Location: This exact location but 3 minutes from now

Re: Pumping lemma for regular languages

Postby Mach1ne » Tue Mar 24, 2009 4:09 am UTC

Maybe I am mistaken, but isn't the perfect power a number expressed as the power of another. So "The set of languages where the length of strings is the k th perfect power of an integer, for all k > 1" would be a string with length m^k where k>1 and m is some natural number > 1. Thus I too am curious how 0^(p^k - p!) is in the language, how is the length of this string is the kth perfect power?

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Pumping lemma for regular languages

Postby Yakk » Tue Mar 24, 2009 2:17 pm UTC

Maybe the OP got the question wrong, or is doing cargo-cult proofs?[1]

Because the proof as described seems really close to a valid proof.

Or maybe the language is the complement of what the OP described. Ie, the set of strings which are not the kth power of an integer?

That is close to what the proof might apply to, because of some magic variable s that shows up. Oh -- s is the length of the pumpable part? Stupid implicit variable names.

We know s < p, so s|p!, so p!/s is an integer.

Then sure, after pumping we hit p^k.

You want k to be sufficiently large, or p^k-p! won't work -- but you can make k large. Personally, I'd use p^p - p! -- p is a sufficiently large k.

So the 2nd post by the OP was a proof that the complement of the described language is not regular. Then "I can prove its complement is not regular and show this isn't regular through closure, bu I can't do this by the pumping lemma." means that he was trying to prove the complement wasn't regular and then show that it itself wasn't regular -- it wasn't that he already had a proof that the complement wasn't regular, and knew he could prove it wasn't regular by closure, and wanted a direct proof.

Ok I think I decoded what the OP was talking about. And yes, that looks like a working proof. It just wasn't a proof for what I thought you where asking for!

[1] A Cargo-Cult proof is when you do the motions of an existing proof, without getting why the proof applied in the first case, and not understanding why it really makes no sense in the current context (or missing key details, because they didn't fit the pattern). Cargo-Cult proof strategies are easy to learn and sometimes hard to notice -- you produce proofs that are close to the right proof, so you pass classes and even exams, but... (Note that the OP isn't doing a cargo-cult proof, but rather a proof surrounded by english verbage that makes the request difficult to decode!)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

NaYoN
Posts: 8
Joined: Fri Mar 07, 2008 5:53 pm UTC

Re: Pumping lemma for regular languages

Postby NaYoN » Tue Mar 24, 2009 2:27 pm UTC

oh shi-... you're right, the initial language was meant to not be a perfect power, that's my mistake


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 9 guests