โ Theory of Computation learning pathTheory of Computation ยท Module 1 of 10
Alphabets, strings and languages
The vocabulary of automata theory.
๐ Key ideas
- An alphabet (Sigma) is a finite set of symbols, such as {0, 1}.
- A string is a finite sequence of symbols; epsilon is the empty string of length 0.
- A language is a set of strings over an alphabet, finite or infinite.
- Sigma* is the set of all strings including epsilon; Sigma+ excludes epsilon.
- Operations on languages: union, concatenation and Kleene star.
๐ก Real-life example: An alphabet is like the letters of English, strings are words built from them, and a language is a dictionary that lists which words are allowed.
AlphabetFinite set of symbols
EpsilonEmpty string of length zero
LanguageSet of strings over an alphabet
Kleene starZero or more concatenations of strings from a language