Alphabets, words, languages
The vocabulary of formal languages: alphabet, word, empty word, length, concatenation, power, mirror, prefix, suffix, factor, language, Σ* and the Kleene star, with computations on finite languages.
- 27 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Understand
A few cards from the deck
Alphabet: what is it?
Show the answer
A finite set of symbols, written Σ, from which words are built: Σ = {a, b} or Σ = {0, 1}.
A word is always a word over a given alphabet: the same text is not a word over {a, b} but is one over {a, b, c}.
With u = ab and v = ba, what is vu?
- baab
- abba
- baba
- aabb
Show the answer
baab
vu writes v then u: ba then ab gives baab. Concatenation is not commutative; uv = abba is another word.
A … over an alphabet Σ is a subset of …, the set of all finite words over Σ.
Show the answer
A language over an alphabet Σ is a subset of Σ*, the set of all finite words over Σ.
Σ* is the largest language over Σ; all the others are subsets of it, from ∅ up to Σ* itself.
Empty word ε: what is it?
Show the answer
The word of length 0, which contains no letter; it is the identity element of concatenation.
For every word u, uε = εu = u. It belongs to every Σ* and is neither a letter nor the empty language.