Language Theory Foundations - Languages: Difference between revisions
Brodriguez (talk | contribs) (Add better language concatenation definition) |
Brodriguez (talk | contribs) (Add language unions section) |
||
Line 83: | Line 83: | ||
=== Language Concatenation === | === 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: | To put it another way, given two languages L_1 and L_2, we can concatenate them together to get: | ||
Line 95: | Line 95: | ||
=== Language Union === | === Language Union === | ||
* '''Language Union''' ('''L_1 ∪ L_2''') - The set that is a combination of all strings in Language 1 and Language 2. 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} | |||
=== Infinite Languages === | |||
* '''Infinite Set of Strings''' ('''Σ^*''') - The infinite set of strings from concatenating all possible symbols together, including λ. | * '''Infinite Set of Strings''' ('''Σ^*''') - The infinite set of strings from concatenating all possible symbols together, including λ. | ||
Revision as of 17:27, 25 September 2019
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, 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 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}
Language Union
- Language Union (L_1 ∪ L_2) - The set that is a combination of all strings in Language 1 and Language 2. 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}
Infinite Languages
- Infinite Set of Strings (Σ^*) - The infinite set of 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 (λ).
- Kelene Star Closure (L^*) - All possible combinations of all strings for the given language L.
- To define it another way,
L^* = L^0 ∪ L^1 ∪ L^2 ∪ ...
- To define it another way,
- Positive Closure (L^+) - Similar to L^*, but minus the empty string (λ).