Language Theory Foundations - Languages

Sets of "valid strings" and how to officially define them.

Language Definition

• Alphabet (Σ) - A non-empty set of characters/symbols.
• String - A specific grouping of symbols from a given alphabet.
• Empty String (λ) - An "empty" grouping of symbols from a given alphabet. Aka, a grouping that excludes all potential symbols.
• Language - A set of strings, over the alphabet Σ.

Ex: Let's define a language L as:

L = { Strings comprised of a's and b's | Each string has at least one instance of "aa" }

We can then determine what strings are or are not within the language L:

∈ L	∉ L
aa	a
aaaa	baba
abaa	bb
baaba	ababba
baababaab	caa

For the last example, note that the string does contain the requirement "aa". However, it also contains the letter "c", which is not an allowed character for the given language.