Monthly Archives: October 2018

Automata Theory, Proofs, Pure Maths

Pumping Lemma

Way way off the beaten path here, but this is the best example of usage of the pumping lemma I've seen. Just need somewhere to put it... The below is taken from here. Theorem: Let L be a regular language, and w be a string. Then there exists a constant c s.t. \forall w \in L, |w| \geq c. We can break w into three strings, w=xyz, s.t.:
  • |y| > 0
  • |xy| \leq c
  • \forall k \geq 0, xy^{k}z \in L
Method to prove that a language L is not regular:
  • At first, we have to assume that L is regular.
  • So, the pumping lemma should hold for L.
  • Use the pumping lemma to obtain a contradiction:
  • Select w s.t. |w| \geq c.
  • Select y s.t. |y| \geq 1.
  • Select x s.t. |xy| \leq c
  • Assign the remaining string to z.
  • Select k s.t. the resulting string is not in L.
  Problem: Prove that L=\{a^{i}b^{i} | i \geq 0\} is not regular. Solution:
  • At first, we assume that L is regular and n is the number of states.
  • Let w=a^{n}b^{n}. Thus |w|=2n\geq n.
  • By the pumping lemma, let w=xyz, where |xy| \leq n.
  • Let x=a^{p}, y=a^{q}, and z=a^{r}b^{n}, where p+q+r=n, p \neq 0, q \neq 0, r \neq 0. Thusly |y| \neq 0.
  • Let k=2. Then xy^{2}z=a^{p}a^{2q}a^{r}b^{n}.
  • Number of a\text{'s}=(p+2q+r) = (p+q+r)+q=n+q.
  • Hence, xy^{2}z=a^{n+q}b^{n}. Since q\neq 0, xy^{2}z is not of the form a^{n}b^{n}!!!!!!!!!!!!!!!
  • Thus, xy^{2}z \notin L. Hence L is not regular.
General

Vectors

Unit 2 is "Vector algebra and statics". I opened this thinking "Ah yup. I know vectors. Easy". I see "dot product" and "cross product" explained in it, and considered how crazy-basic this unit must be. I saw arrows on force diagrams. Yup. Simple. This will be a non-unit. A breeze. Though it turns out... after getting a few pages in, I've not been asked to present vectors quite like this before, and these force diagrams look a lot different to the ones I remember somehow. Seems I do actually have to read this all carefully... I'm also used to using vectors in programming, so the fact that every vector I'm given is unnormalised also makes me feel dirty. Right, we'll see how this goes then... :/
Maths, Mechanics

Unit 1 COMPLETE!

My first unit is done! I managed to find time to complete the first assignment too. This is timely, as the course officially starts tomorrow.

This unit was interesting. Looking at the title "differential equations" I thought "Oh, okay, fine. I've done this before". Then opening up the book, I realised "Oh wait. I haven't quite done THIS before". That's when the fear crept in... how much of a learning curve would I be facing in this new unit?!

Forging through, I had to concede defeat on one or two examples, but I came out the other end confident about all the material I'd covered. Only now I've completed the assignment do I feed confident about my ability on the subject matter, but it's also one of those areas where I need to keep up the practise. 

All too often, it's the first unit that you return to at revision time and think "what IS all this?!". It's been hinted at that themes of second order differential equations reoccur throughout the module so I'm hoping I'll stay in practise. 

So I'll give the assignment a final proof-read and then submit it tomorrow on the first official day of the module. Good start.

Maths, Mechanics

Book Arrival

My books finally arrived.

I've got nine months to get all of that inside my brain. -but then I will also need to be able to write answers to questions on the subject matter at close to the speed of sound by the time of the exam...