STEP-BY-STEP LESSON · §12.1
Formal Languages and Regular Expressions
Read a language as a set of strings and build regular expressions.
Before you begin
Sets and membership
A set records which objects belong to it. Repetition and listing order do not change a set. x∈A says that x is an element; A⊆B says every element of A is also in B.
Concatenation
Concatenation appends one word after another without reordering their symbols. For languages L,M, LM contains every uv with u∈L and v∈M. It combines words, not numerical products.
Symbols
- Σ
- alphabet: permitted symbols
- ε
- empty string
- L*
- zero or more concatenated words from L
Definitions and notation for this topic
Alphabet, empty word and length
Σ; ε; |w|
An alphabet Σ is a finite set of permitted symbols. A word or string is a finite sequence of them. ε is the empty word and |w| is the number of symbols in w.
Σ names a set here, whereas ∑ denotes summation. The bars in |w| denote string length, not absolute value or divisibility. A word’s order matters.
Separate glossary example
Over Σ={0,1}, |010|=3 and |ε|=0. The language {ε} contains one word; the empty language ∅ contains none.
Concatenation and Kleene star
uv; KL; L*
uv appends word v after u. For languages K,L, KL={uv:u∈K,v∈L}. L* contains concatenations of any finite number of words from L, including zero words.
Zero concatenated words give ε, so ε belongs to every L*, even ∅*={ε}. The star applies to the preceding language or grouped regular expression; concatenation need not commute.
Separate glossary example
If K={a,b} and L={01}, then KL={a01,b01}. If L={01}, then L*={ε,01,0101,…}.
Step by step
Step 1 / 6
Distinguish symbols from words
An alphabet is a finite set of symbols. A word is a finite sequence of symbols; ε has length 0.
A language is a set of such words, not one long sentence.
Worked example
Which words does (01)* describe?
- The parentheses group the two-symbol word 01; the star repeats this whole block.
- Zero repetitions give ε; one gives 01; two give 0101.
- Then 010101, and so on. 0011 does not qualify: it is not a concatenation of 01 blocks.
Optional self-check
Does the language ∅* equal ∅ or {ε}? Explain using zero repetitions.
Show answer
It equals {ε}. Zero repetitions always produce ε; a positive repetition cannot choose a word from an empty language.