Fun Stuff > CHATTER
Can't Think of a Breaking Bad Pun For the Title: Let's Do Some Math!
Carl-E:
Welp, my work here is done!
I figured if anyone would crank it out, it would have been you... and Fermat's sum of two squares theorem was a nice easter egg!
Have fun proving it...
Loki:
--- Quote from: Carl-E on 24 Mar 2015, 08:02 ---Welp, my work here is done!
I figured if anyone would crank it out, it would have been you... and Fermat's sum of two squares theorem was a nice easter egg!
--- End quote ---
o.O I am far from being the most math adept person on the forum (not counting you, of course). We have physicists amd actual rocket scientists here.
--- Quote ---Have fun proving it...
--- End quote ---
Welp. Uh. I can do one direction. That's already half of the work, right? :-D The rest is left as an exercise.
LTK:
This article piques my interest even though I have virtually no understanding of the kind of mathematics it deals with.
http://www.scientificamerican.com/article/mathematicians-chase-moonshine-s-shadow/
ankhtahr:
This isn't math per se, but I think it's close enough to put it here.
So I'm writing my exam on theoretical computer science tomorrow, and I'm still having trouble with one, or rather two things: the pumping lemma for regular and for context free languages.
Can somebody here explain to me what e.g. a general approach to proving that a language isn't regular using the pumping lemma would be? I think I can grasp the general idea of the lemma, but I'm struggling with how to apply it to tasks. Here's an example task from a test exam:
A language L is defined as follows:
Prove that L is not regular, using the pumping lemma. (Hint: Use words in the form )
I guess it'll go in the direction that pumping the prefix or the suffix of the middle one will break it, and pumping the middle won't work either, but how do I really approach that task?
Loki:
(click to show/hide)First of all, that should be
(I would detract at least half a point for that).
Okay. The general idea is as follows. We want to check if a language is regular, ie if there exists a (deterministic) finite automaton that accepts L (ie all words in L and only the words in L).
Let's assume L is regular, then there is such an automaton A. Let's assume it's minimal (the minimal automaton for a given language is unique) and has n states.
Then in order for it to accept words with more than n letters, it has to visit some states multiple times (this is called the pigeon hole principle). So there must be a loop in the automaton.
That also means that we can this loop an arbitrary number of times, so our words in L(A) keep getting longer and longer.
The pumping lemma now states:
L is regular iff
there exists some n >=1 such that
for each word w in L with length of at least n,
there exists a breakdown (Zerlegung) of the word in three parts x, y and z (w=xyz)
such that the following conditions are true at the same time:
1) y is not empty
2) length(xy)<=n
3) for each i>=0, x(y^i)z is in L.
Plainly speaking: y is the part that would be looped in our run on the automaton A. We should also be able to not loop this at all and still be in the language.
So we now take some word of length at least n. For that, we know that we are looping some portion of the run.
The task helpfully provides the word 0^n10^n, which is also what I would have taken.
Now, we need to find a breakdown of the word such that the conditions 1 and 2 hold.
In particular, length(xy) is at most n, but xyz it also spans the whole word. So we have the following case:
x=0^k, y=0^j such that k+j<=n and j!=0 (the latter, because the length of y is not empty as per 1)
Then z = 0^m10^n (the remainder of the word). Note that m is 0 iff k+j=n.
Now, consider what happens if we set i=2 and look at x(y^i)z. This becomes
x(y^2)z
=0^k(0^(2*j))0^m10^n
=0^(n+j)10^n which is not in the language.
As an alternative, we could also look at i=0. Then we get 0^(n-j)10^n which is also not in the language.
Now we have done a proof by contradiction. We assumed L was regular. Then the conditions 1 to 3 must hold true. However, we broke condition 3. Thus, our premise is wrong and L is non-regular.
Basically, in order to prove a language L is non-regular:
* you find a word in L which has at least size n
* you consider how a breakdown with conditions 1 and 2 would look like
* you consider what happens if you set the i in condition 3 to some arbitrary values which are not equal to 1. Usually, 0 or 2 will do the trick.
(click to show/hide)The idea for context-free languages is more or less: you have a grammar. You have a finite set of production rules. If you want words of arbitrary length, there must be some non-terminal which you "visit" twice (ie whose production rules you take). This is better stated in the diagram:
https://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages#Formal_statement
Actually, the article explains that one better than I could. The general look at this will also be as above:
--- Quote ---Now we have done a proof by contradiction. We assumed L was regular context-free. Then the conditions 1 to 3 must hold true. However, we broke condition 3. Thus, our premise is wrong and L is non-regular not context-free.
Basically, in order to prove a language L is non-regular not context-free:
* you find a word in L which has at least size n
* you consider how a breakdown with conditions 1 and 2 would look like
* you consider what happens if you set the i in condition 3 to some arbitrary values which are not equal to 1. Usually, 0 or 2 will do the trick.
--- End quote ---
Good luck!
Navigation
[0] Message Index
[#] Next page
[*] Previous page
Go to full version