Symbols such as epsilon, Sigma*, w^R and L1L2 look compact, but one mix-up between a string and a language changes the answer. We will build a clean model one layer at a time: alphabet, string, parts of a string, string operations, then operations on whole languages. The exact examples use w=ababa, x=ab, y=baa and L={a,bb}, so every rule can be checked rather than memorised.
Use CS Fundamentals as the broader subject hub when you want to connect this notation to automata, grammars and other core CS topics.
Alphabet, string and language: keep the three levels separate
An alphabet Sigma is a finite, non-empty set of symbols. A string is a finite sequence of symbols drawn from that alphabet. A language is any set of strings over the alphabet. Sigma* means the set of all finite strings over Sigma, including epsilon.
Take Sigma={a,b}. The objects epsilon, a, abba and baab are strings over Sigma. The objects c and a2 are not, because each contains a symbol outside the alphabet. If L={epsilon,a,ab}, then L is a language because L is a subset of Sigma*.
Keep the two empty objects separate. epsilon is one string of length zero. emptyset is a language containing no strings, while {epsilon} is a language containing exactly one string. Therefore |emptyset|=0, but |{epsilon}|=1.
An automaton consumes strings over an alphabet and accepts a language. These definitions are therefore the input layer for studying DFAs and NFAs.
Length, prefix, suffix, substring and subsequence
Fix w=ababa, with positions 1:a, 2:b, 3:a, 4:b, 5:a. Its length is |w|=5, while |epsilon|=0.
The prefixes of w are epsilon, a, ab, aba, abab, ababa. Its suffixes are epsilon, a, ba, aba, baba, ababa. A proper prefix or proper suffix excludes the whole string. Under the standard convention used here, epsilon is still proper because w is non-empty.
The string aba is both a prefix and a suffix, so it is a border of w. It is also a contiguous substring at positions 1-3 and 3-5. Similarly, bab is a substring at positions 2-4.
By contrast, aaa is a subsequence using positions 1,3,5, but it is not a substring because those positions are not contiguous. Test the positions for contiguity instead of relying on visual similarity.
Concatenation and string powers with exact values
Let x=ab and y=baa. Placing y after x gives xy=abbaa. Reversing the operand order gives yx=baaab. Since abbaa != baaab, string concatenation is not commutative.
The lengths give a direct check: |x|=2, |y|=3, and |xy|=|x|+|y|=2+3=5. In general, concatenating two strings adds their lengths.
A string power repeats the same string through concatenation. Here, x^0=epsilon, x^1=ab, x^2=abab and x^3=ababab. The length check is |x^3|=3|x|=3*2=6. Notice that x^0 is the empty string, not the empty language and not the numeral zero.
The empty string is the identity: epsilon x=x epsilon=ab. Concatenation is also associative. With these values, (xy)x=abbaaab and x(yx)=abbaaab. Associativity preserves the operand order, even though the brackets may move.
Reversal changes order, not length
Reversal writes a string's symbols in the opposite order. For x=ab, x^R=ba. For y=baa, y^R=aab. Since xy=abbaa, (xy)^R=aabba.
The order of the reversed pieces matters: y^R x^R=(aab)(ba)=aabba, which confirms (xy)^R=y^R x^R. The tempting expression x^R y^R=(ba)(aab)=baaab is different and therefore wrong.
Reversal preserves length, as |aabba|=|abbaa|=5, and reversing twice restores the original string. A palindrome is a special checkpoint: for p=abba, p^R=abba=p. Not every string is a palindrome, so equality with the reversal must not be assumed.
Union, intersection, difference and complement of languages
Keep Sigma={a,b}, and take L1={epsilon,a,ab} and L2={a,b,ab}. The finite set operations are:
Operation | Exact result |
|---|---|
|
|
|
|
|
|
|
|
Language difference is directional, which is why the last two rows differ.
A complement is meaningful only after naming its universe. Relative to Sigma*, complement(L1)=Sigma*-L1. It excludes exactly epsilon, a and ab; strings such as b, aa, ba and bb remain in the complement. Since Sigma* is infinite, there is no need to list the complement fully.
Finally, a is a string, while {a} is a one-element language. The expression a in L1 tests membership; {a} subseteq L1 tests set containment.
Language concatenation, powers and closures
Language concatenation forms every ordered pairing. For L1L2, the nine pairings are epsilon.a=a, epsilon.b=b, epsilon.ab=ab, a.a=aa, a.b=ab, a.ab=aab, ab.a=aba, ab.b=abb and ab.ab=abab. Removing the duplicate ab gives L1L2={a,b,ab,aa,aab,aba,abb,abab}, with eight distinct strings.
For a smaller closure example, let L={a,bb}. Then L^0={epsilon} and L^1={a,bb}. The four ordered pairings produce L^2={aa,abb,bba,bbbb}. A language power produces a set of strings; a string power produces one string.
The Kleene star is L*=L^0 union L^1 union L^2 union ..., while positive closure is L+=L^1 union L^2 union .... In this example, epsilon is not in L, so L*=L+ union {epsilon}. If epsilon already belongs to L, it can also belong to L+. Therefore, the claim that positive closure never contains epsilon is not generally safe.
These operations become the notation used to describe regular languages in Regular Expressions and Pumping Lemma: Worked Proof.
How questions combine the notation
Common question shapes ask you to classify an object as a symbol, string or language; expand a finite language product; identify a valid concatenation or reversal identity; or count strings of a fixed or bounded length.
For a counting example, let Gamma={0,1,2}. Since |Gamma|=3, |Gamma^2|=3^2=9. The number of strings of length at most two is |Gamma^0|+|Gamma^1|+|Gamma^2|=1+3+9=13. Excluding epsilon leaves 12 non-empty strings.
Now reuse x=ab and y=baa. The length is |x^2y^3|=2|x|+3|y|=2*2+3*3=4+9=13. The explicit string is ababbaabaabaa, whose 13 symbols confirm the formula.
Check these traps before finalising an answer:
epsilonis notemptyset.An element is not its singleton language.
A subsequence need not be a substring.
xyneed not equalyx.(xy)^Requalsy^R x^R, notx^R y^R.A complement needs a stated universe.
A language power starts with
L^0={epsilon}.
KnowledgeGate has 20+ published practice questions tagged to Basics & String Ops, which you can use to test these distinctions without treating that count as exam weightage.
The short version and the next study step
Remember four lines: strings are sequences over an alphabet; languages are sets of strings; string concatenation preserves order; language star includes the zero-fold product {epsilon}.
Now re-derive two checkpoints without looking: the six prefixes of ababa, and L^2={aa,abb,bba,bbbb} for L={a,bb}. Continue with Finite Automata: DFA vs NFA and Subset Construction. For guided depth, use Theory Of Computation / Automata Theory. If you are rebuilding several CS fundamentals together, ZERO TO HERO is the broader route.
