A formal language L is a language over an alphabet Σ which is accepted by a given set of rules.
A regular language represents strings approved over a set of rules.
Regular languages can be expressed by such formats as
regular expressions or
finite state automaton.
The process of evaluating a regular language is linear (one step at a time).
What you can do with regular languages is limited.
Question: Can you represent aⁿ bⁿ with regular language? (where n is a constant that represents the number of occurrences of the character before it).
Because if it's strict rules, it can be highly useful in detecting the validity of:
URL's
email addresses
dates
or any designed expected sequence that is expected as input, such as coordinates.
These are commonly represented as regular expressions and often have support for them embedded in programming languages.
Formal languages can also be used to express a sequence events. These are commonly expressed as finite state automaton, and often used for purposes such as:
expressing simple mechanics of simple electronic systems such as a clock, automatic door, thermostat.
More complex algorithms can be expressed with non-deterministic finite state automata such as algorithms for traversing trees, searching and so forth.
Note that if a formal language can be expressed by a finite state automaton, it can also be expressed by a regular expression, and vice versa.
A formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symbols, letters, or tokens that concatenate into strings of the language.
A formal language L over an alphabet Σ is a subset of Σ*. So, for instance, a formal "language" is a set of strings (tokens, letters, symbols) that are formed or accepted using the alphabet. For example, if your alphabet is alphabet Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =, :, /, @, a - z}
Your formal language L therefore meets one of the following criteria given your alphabet:
those strings generated by some formal grammar;
those strings described or matched by a particular regular expression;
those strings accepted by some automaton, such as a Turing machine or finite-state automaton;
those strings for which some decision procedure (an algorithm that asks a sequence of related YES/NO questions) produces the answer YES.
So a formal language can be *expressed* by the use of finite-state automaton, or a regular expression.
CS Field Guide defines a Formal Language as "A set of strings accepted by some rule".
Note that any language which can be expressed as a regular expression, can also be expressed as a finite state automaton.
We will be covering Formal Languages can be described by State Automaton and Regular Expressions which we will be scribing in the next sections.
TODO: Edits for 2022: Pushdown automaton, Turing machines, halting problem.