There are two versions of the Pumping Lemma. One is for context free grammars and one is for regular languages. This post is about the latter. The Pumping Lemma describes a property that all natural languages share. While it cannot be used by itself to prove that any given language is regular, it can be …
Tag: proof
Nov 21 2017
Proof of Kleene’s Theorem
In my last post, “Kleene’s Theorem,” I provided some useful background information about strings, regular languages, regular expressions, and finite automata before introducing the eponymously named theorem that has become one of the cornerstones of artificial intelligence and more specifically, natural language processing (NLP). Kleene’s Theorem tells us that regular expressions and finite state automata …
Jul 16 2017
The Sum of an Arithmetic Series
An arithmetic sequence of numbers, sometimes alternatively called an arithmetic progression, is a sequence of numbers in which the difference between all pairs of consecutive numbers is constant. A very simple arithmetic sequence consists of the natural numbers: 1, 2, 3, 4, … where the difference between any number and the number before it is …
Mar 09 2016
Unsigned Binary Integers and Internal Congruence
This is going to be another one of my “selfish” posts – written primarily for me to refer back to in the future and not because I believe it will benefit anyone other than me. The idea is one that I always took for granted but had a hard time proving to myself once I decided …
Jan 12 2016
Modular Exponentiation Rule Proof
It is no big secret that exponentiation is just multiplication in disguise. It is a short hand way to write an integer times itself multiple times and is especially space saving the larger the exponent becomes. In the same vein, a serious problem with calculating numbers raised to exponents is that they very quickly become …
Jan 02 2016
Modular Multiplication Rule Proof
I must stay focused. I must stay focused. I must stay … I wonder what’s new on Facebook. I don’t really feel like writing this post mostly because I know that it will be very similar to the other two I have already done: modular addition rule proof and modular subtraction rule proof, but my New …
Dec 31 2015
Modular Subtraction Rule Proof
I’ve already presented and proved the rule for modular addition, so for a sense of completeness, but mostly to satisfy my OCD, now I’ll cover the rule for modular subtraction. When doing subtraction in modular arithmetic, the rule is: If we subtract integer from integer and calculate the difference modulo , we get the same answer …
Dec 31 2015
Modular Addition Rule Proof
Addition in modular arithmetic is much simpler than it would first appear thanks to the following rule: This says that if we are adding two integers and and then calculating their sum modulo , the answer is the same as if we added modulo to modulo and then calculated that sum modulo . Note that …
Aug 13 2015
Pythagorean Theorem Proof
It may very well be the second most famous equation of all time, outshone only by that braggart Einstein’s mass–energy equivalence equation. But for those of us that aren’t theoretical physicists, the Pythagorean Theorem is likely to play a fundamental role in many of the calculations we do whether we realize it or not. Everyone knows …