Formal Language

Formal language is a set of formulae under some rules/structure. Formally, a formal language is a subset of all the finite-length words over a given alphabet.

Definition §

Formal Language ^definition

Let $\Sigma$ be a set of symbols (also called letters). ${\Sigma }^{\ast }$ is the set of all possible (finite-length) words/formulae (sequences of letters) that can be constructed from $\Sigma$. Then, the set $L$ is a formal language if:

$$L\subseteq {\Sigma }^{\ast }$$

Any formula that is an element of $L$ is well-formed under it.

Examples §

Example: Snake Case §

In programming, camel case refers to a naming convention for variables, that requires all characters to be lower case, and any spaces are replaced with an underscore (_). For example age, max_speed and hello_how_are_you are all examples of variables named in snake case. Technically, numbers are also allowed, but for the sake of simplicity, let’s only restrict ourselves to the English alphabet. Let’s define it as a formal language.

Our symbol set (alphabet/vocabulary) is:

$$\Sigma =\{A...Z,a\dots z,\_,\text{textvisiblespace}\}\text{*Here, textvisiblespace means a space character}$$

Then, our formal language, $S$ can be:

$$S=\{w:w\in (a\dots z,\_{)}^{\ast }\}$$

Here, $w$ is defined as a formula/word in $S$ and $w$ must satisfy the condition that it is any finite permutation of all lowercase letters, plus the underscore for it to be well-formed. Then, $w$ can be any of:

1. abab
2. _______ab
3. snake_case
4. ____

Examples (1) and (3) are normal, but (2) and (4), while technically allowed under $S$, aren’t exactly what we mean when we talk about snake case. Let’s have a clear set of rules for a word/formula, $w$ to belong in $S$:

• It must start with an English letter (a-z)
• Every underscore must be preceded and succeeded by an English letter i.e. we can only have one underscore between two strings of english letters.

First, we can only look at cases where we want two words, separated with an underscore. Here, we can put two symbols next to each other to concatenate them, not multiply!!

$$S=\{w_1\_w_2|w_1,w_2\in (a\dots z{)}^{\ast }\}$$

But now we #todo