Formal Language and Parsing Constructs, Simplified¶

I fell down a Wikipedia rabbit-hole so you don't have to.

No knowldege is assumed besides a good grasp of programming and some basic set algebra.

You should read this page in order; some notation and concepts explained earlier are used further on.

This page remains under construction, and will likely never be complete.

λ¶

(the lowercase Greek letter lambda)

One of two primary conventions to represent the empty string, and the one used on this page. (the other being epsilon)

regex¶

An informal class of Regular Expressions; they exist in many

Kleene Star¶

The Kleene Star , some_set*, means "any element from this set, repeated zero or more times". For example, {ab, c}* is {λ, ab, c, abab, abc, cab, cc, abcc, ...}.

This is almost certainly the origin of the regex * quantifier ((ab|c)* matches λ, ab, c, abc, cab, cc, abcc, etc.)

Kleen Plus¶

The same as the Kleene Star, but not including λ. It parallels the regex + operator.

First published: 2020-11-28
Last updated: 2020-11-28