Language Operations and Sets Explained: Union, Concatenation, Kleene Star and Exam Problems
Learn why epsilon differs from the empty language, how order changes concatenation, and how small counterexamples expose false identities. Two worked languages carry every result.
KnowledgeGate Team
Exam prep & CS education

Set notation becomes error-prone when its elements are strings: order changes concatenation, duplicates change cardinality, and epsilon is confused with the empty language. Fix the alphabet and universe, expand each ordered pair, deduplicate only after expansion, and test doubtful identities with a small counterexample.
A language is a set of strings, so fix the alphabet first
An alphabet is a finite, non-empty set of symbols. A string is a finite sequence of symbols from that alphabet, and a language is any subset of all possible finite strings over it.
Take Sigma = {a, b}. Then:
Sigma^0 = {epsilon}Sigma^1 = {a, b}Sigma^2 = {aa, ab, ba, bb}Sigma^(<=2) = {epsilon, a, b, aa, ab, ba, bb}
Keep three objects separate. epsilon is the single string of length zero. {epsilon} is a language containing that string. empty-set is a language containing no strings. Similarly, a in {a, ab} describes membership, while {a} subset-of {a, ab} describes a subset. The string a and the set {a} are not interchangeable.
Use A = {epsilon, a, ab} and B = {b, ab} for the calculations below. Length of a String: TOC Notation and String Operations covers alphabet-level notation such as prefixes and subsequences; the calculations stay at the language-set level, with explicit union, difference, concatenation and closure results. The CS fundamentals courses provide the wider subject route around this topic.
Union, intersection, difference and complement
Apply ordinary set rules to the strings in A and B:
A union B = {epsilon, a, b, ab}A intersection B = {ab}A - B = {epsilon, a}B - A = {b}
The string ab appears once in the union. A language is a set, not a list or multiset.
Complement needs a stated universe. With U = Sigma^(<=2) = {epsilon, a, b, aa, ab, ba, bb}, removing every member of A gives U - A = {b, aa, ba, bb}. This bounded display is different from Sigma* - A, which contains infinitely many strings. Never calculate a complement before naming its alphabet and universe.
Union and intersection are commutative. Difference is not: the results above show that A - B and B - A differ.
Fully worked concatenation: order first, deduplicate last
Language concatenation is AB = {xy | x in A and y in B}. There are 3 x 2 = 6 ordered pairs:
epsilon.b = bepsilon.ab = aba.b = aba.ab = aabab.b = abbab.ab = abab
Only now remove the repeated ab. Thus AB = {b, ab, aab, abb, abab} and |AB| = 5, even though |A||B| = 6.
Reverse the order and expand again: b.epsilon = b, b.a = ba, b.ab = bab, ab.epsilon = ab, ab.a = aba, and ab.ab = abab. Therefore BA = {b, ba, bab, ab, aba, abab} and |BA| = 6. Since AB != BA, concatenation is not commutative.
Two identities explain the edge cases. {epsilon}A = A because the empty string changes nothing. In contrast, empty-set A = empty-set because there is no left-hand string to pair. For finite languages, the safe cardinality statement is |AB| <= |A||B|; duplicate results can make it strict.

Language powers, Kleene star and positive closure
Use a fresh language K = {a, bb}. Define K^0 = {epsilon} and K^(n+1) = K^n K. Therefore K^1 = {a, bb}. Expanding the next power gives a.a = aa, a.bb = abb, bb.a = bba, and bb.bb = bbbb, so K^2 = {aa, abb, bba, bbbb}.
Kleene star and positive closure differ at power zero:
K* = K^0 union K^1 union K^2 union ...K+ = K^1 union K^2 union ...
For this K, epsilon in K* but epsilon not-in K+, because epsilon not-in K. The conclusion changes for E = {epsilon, a}: epsilon in E+ because one positive concatenation can choose the member epsilon.
For every language L, L^0 = {epsilon}. It follows that empty-set^0 = {epsilon}, empty-set^n = empty-set for every n >= 1, and empty-set* = {epsilon}. Also, {epsilon}* = {epsilon}.

Which algebraic laws survive
Set operations give A union B = B union A and A intersection B = B intersection A, but the worked results give AB != BA. Concatenation does distribute over union: A(B union C) = AB union AC and (A union B)C = AC union BC. In each case, the selected string from the union comes from one language or the other.
A small witness can break a false identity. Let P = {a} and Q = {b}. Then ab in (P union Q)*, but ab not-in P* union Q*. Every string in P* contains only a, while every string in Q* contains only b.
The same languages refute another tempting equality. (PQ)* = {epsilon, ab, abab, ...}, whereas P*Q* = {a^i b^j | i,j >= 0} contains a and b. The sets are unequal. Regex notation later reuses union, concatenation and star as expression operators.
How objective questions combine the operations
Common tasks ask for a resulting language, its cardinality, epsilon membership, a nested expression, or whether an identity is always true. For example, evaluate (A union B) intersection Sigma^1. First, A union B = {epsilon, a, b, ab}. Since Sigma^1 = {a, b}, the intersection is {a, b}.
Try another exact item: X = {a, ab} and Y = {epsilon, b}. Expand XY as a.epsilon = a, a.b = ab, ab.epsilon = ab, and ab.b = abb. After deduplication, XY = {a, ab, abb}, so |XY| = 3, not 4.
Use this order: solve parentheses, write the universe beside a complement, expand concatenation as ordered pairs, remove duplicates, and check epsilon. Test universal-looking equalities with P = {a}, Q = {b}, or the empty language. The Theory of Computation overview places these operations within the larger subject map.
Traps and their repairs
Each plausible mistake has a direct repair:
Reading
epsilonasempty-set-> the identity element disappears -> keepepsilonas a length-zero string.Treating concatenation as a Cartesian product -> the answer contains ordered pairs -> join the characters in each pair.
Counting before deduplication ->
|AB|is wrongly reported as6-> list six products, then reduce them to five distinct strings.Assuming
AB = BA-> order is lost -> compute one witness in both directions.Taking complement without a universe -> the answer is undefined or changes -> write
Sigma* - Lor state a bounded universe.Reading star as one or more ->
epsilondisappears -> remember that star starts at power0, while plus starts at power1.
Audit the worked values: the union has 4 strings, the intersection has 1, AB has 5, BA has 6, and K^0, K^1, K^2 have 1, 2, 4 strings respectively.
The short version and your next practice step
Recall six rules: a language is a set of strings; epsilon is not the empty language; complement needs a universe; concatenation preserves order; L^0 = {epsilon}; and L* starts at power 0 while L+ starts at power 1. The main self-check is AB = {b, ab, aab, abb, abab}.
A ten-question drill can use 2 set-operation outputs, 3 concatenation outputs, 2 star-or-plus membership checks, 2 identity counterexamples, and 1 nested expression. Label each miss as universe, order, duplicate, epsilon, or closure.
First recompute BA, K^2, and the (P union Q)* counterexample on paper. Then choose the Theory of Computation / Automata Theory course for focused subject study or Zero to Hero for a broader core-CS path.
Keep learning
Formal Language Operations & Sets MCQs: 11 Solved Questions
Work through 11 solved questions on Kleene star membership, complements, concatenation duplicates, language powers, palindrome counts and empty-language algebra.
Data Warehousing and Data Mining in DBMS: Star Schema, OLAP Operations and Apriori with Worked Examples
Move from warehouse vocabulary to hand-worked answers. Build a star schema, operate on a data cube, run Apriori, and follow two k-means iterations.
Set Operations in SQL: UNION, INTERSECT and EXCEPT with Worked Examples
Learn how SQL combines compatible query results, why duplicates and column order matter, and how to calculate UNION, INTERSECT and EXCEPT outputs by hand.
Set Operations: Union, Intersection, Difference, Symmetric Difference and Complement with Worked Examples
Use one fixed Venn partition to compute five set operations, verify De Morgan's laws, solve an 80-student survey, and repair common exam mistakes.





