Language Theory Foundations - Languages
Jump to navigation
Jump to search
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.