What is a Formal Language?
The Rigorous definition:
Let be an alphabet and let be the set of all strings of length k over that alphabet. Then, we define to be (the union of ∑k over all natural numbers k). If , we call a language.
The Intuition Behind the Definition
Consider an alphabet (some finite set of characters), for example we can consider the letters of the English language, the ASCII symbols, the symbols (otherwise known as binary), or the symbols . We can then construct the infinite list of all the different ways we can arrange those characters (e.g. or , etc. if we’re using binary). We call these arrangements “strings”. Once we have all that machinery built up, a language is just some subset of that infinite collection of strings. The language may itself be infinite.
What are we getting at?
Well, there are two ways to look at this. On the first hand, linguists would like to study language in its abstract essence. For this, Formal Languages may come in handy (if endowed with a Grammar and possibly more). That is not the reason I will be studying Formal Languages. I’m learning about formal languages to find their applications to computing.
Apparently, with the help of a little Mathematical thinking, we can assign semantics to the strings in a language and somehow correlate them with real world problems — such as computability, the P=nP problem, cryptography, and more!