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/Word - A specific, finite 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, b, ...})- 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.

String Manipulation

• String Length (|w|) - The number of symbols in a given string.

Ex: If w="abc", then:

|w| = 3

String Concatenation

• Concatenation (u * w) - Appending the symbols of one string to the end of another.

Ex: If we have string w="abc" and string u="def", then

w * u = "abcdef"

We can also concatenate the same string to itself, n times. This is denoted with w^n, where w is the string and n is the number of times to append to itself.
Note that w^0 is equivalent to λ.

Ex: If we have w="abc", then we can create the following:

w^0 = λ
w^1 = "abc"
w^2 = "abcabc"
w^3 = "abcabcabc"

Concatenating the empty string to a non-empty string will simply result in the same string.

Ex: If we have w="abc", then:

wλ = w = "abc"
λw = w = "abc"

String Reversal

• Reverse (w^R) - Symbols of a string in reverse order.

Ex: If we have string w="abc", then:

w^R = "cba"
w * w^r = "abccba"
w^R * w = "cbaabc"
w^R * w^R = "cbacba"

Language Manipulation

• Finite Language - A language with a finite number of strings.

Ex: L = {a, aa, aab}

• Infinite Language - A language with an infinite number of strings.

Ex:

L = {a^nb^n | n ≥ 0 }
Results in {ab, aabb, aaabbb, ...}

Language Union

• Language Union (L_1 ∪ L_2) - The set that is a combination of all strings that exist in Language 1, in Language 2, or both. Note that these strings are not concatenated together.

Ex: Given L_1 = {a, aaa} and L_2 = {b, bbb}:

L_1 ∪ L_2 = {a, aaa, b, bbb}

Language Concatenation

• Language Concatenation (L_1 * L_2) - The set that is defined by the concatenation of every string in language 1 onto every string in language 2. Note that we can concatenate languages through the same syntax that we concatenate individual strings.

To put it another way, given two languages L_1 and L_2, we can concatenate them together to get:

L_1 * L_2 = { all string combinations x * y | x ∈ L_1, y ∈ L_2 }

Ex: Given L_1 = {a, aaa} and L_2 = {b, bbb}:

L_1 * L_2 = {ab, abbb, aaab, aaabbb}

Ex: Given L = {a^nb^n | n ≥ 0}:

L * L = L^2 = {a^nb^na^mb^m | n ≥ 0, m ≥ 0}

Infinite Languages

• Infinite Set of Strings (Σ^*) - The set of all words/strings from concatenating all possible symbols together, including λ.

Ex: If a, b ∈ Σ, then:

Σ^* = {λ, a, b, aa, ab, bb, ba, aaa, aab, aba, abb, ...}

• Σ^+ - Similar to Σ^*, but minus the empty string (λ).

Ex: If a, b ∈ Σ, then:

Σ^* = {a, b, aa, ab, bb, ba, aaa, aab, aba, abb, ...}

• Keleene Star Closure (L^*) - All possible combinations of all string concatenations for the given language L.
  • To define it another way, L^* = L^0 ∪ L^1 ∪ L^2 ∪ ...

Ex: If L = {a, b, c}, then:

L^0 = {λ}
L^1 = {a, b, c}
L^2 = {aa, ab, ac, ba, bb, bc, ca, cb, cc}
L^3 = {aaa, aab, aac, aba, abb, abc, aca, acb, acc, bca, bcb, bcc, ...}
...

Combining all these strings into one set gives us:
L^* = L^0 ∪ L^1 ∪ L^2 ∪ ...

• Positive Closure (L^+) - Similar to L^*, but minus the empty string (λ).

Ex: In the above example, L^+ would simply exclude L^0.