Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Formal languages and operations on languages

Formal languages are sets of strings over an alphabet; this note defines basic terms and operations (union, concatenation, Kleene star, complement, reversal, homomorphism, quotients, etc.), gives exact algebraic identities and closure properties (especially for regular and context-free languages), s

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Formal languages give the precise mathematical way to talk about sets of strings (programs, protocols, data formats). Engineers use these ideas when designing lexical analyzers, pattern matchers, compilers, network protocol validators and when proving properties of those systems (for example, whether a pattern can be recognized by a finite-state device).

Key ideas

Start from first principles and define every symbol.

  • Alphabet: a finite nonempty set of symbols, usually denoted Σ. Example: Σ = {a, b}.
  • String (word): a finite sequence of symbols from Σ. The empty string is ε (length 0). The length of a string x is |x|.
  • Language: any set of strings over Σ; thus L ⊆ Σ. Here Σ denotes the set of all finite strings over Σ.
  • Empty language: ∅, the language containing no strings.
  • Singleton language: {w} contains exactly the string w.

Basic operations on languages (for language(s) L, L1, L2 ⊆ Σ*):

  • Union: L1 ∪ L2 = { x | x ∈ L1 or x ∈ L2 }.
  • Intersection: L1 ∩ L2 = { x | x ∈ L1 and x ∈ L2 }.
  • Difference: L1 \ L2 = { x | x ∈ L1 and x ∉ L2 }.
  • Complement (w.r.t. Σ*): L^c = Σ* \ L.
  • Concatenation: L1 · L2 = { xy | x ∈ L1, y ∈ L2 }.
  • Power: L^0 = {ε}; L^{n+1} = L · L^n (for n ≥ 0). So L^1 = L.
  • Kleene star: L* = ⋃_{i=0}^∞ L^i (zero or more concatenations).
  • Positive closure: L+ = ⋃_{i=1}^∞ L^i = L · L* (one or more concatenations).
  • Reversal: For a string w = a1 a2 ... an, rev(w) = an ... a2 a1. For language L, rev(L) = { rev(w) | w ∈ L }.
  • Left quotient (or left quotient by a string): for x ∈ Σ*, x⁻¹ L = { y | x y ∈ L }. For a language R, R⁻¹ L = ⋃_{x∈R} x⁻¹ L.
  • Right quotient: L x⁻¹ = { y | y x ∈ L }. For a language R, L R⁻¹ = ⋃_{x∈R} L x⁻¹.
  • Homomorphism: a map h: Σ1* → Σ2* defined by mapping each symbol a ∈ Σ1 to some string h(a) ∈ Σ2*, extended to strings by h(a1...an) = h(a1)...h(an). For a language L, h(L) = { h(w) | w ∈ L }.
  • Inverse homomorphism: h⁻¹(M) = { w ∈ Σ1* | h(w) ∈ M }.
  • Substitution: a function s that maps each symbol a ∈ Σ to a language s(a) ⊆ Γ*. Extended to strings by s(a1...an) = s(a1)·...·s(an) and to languages by s(L) = ⋃_{w∈L} s(w).

Important algebraic identities and facts (state and prove or justify in exams):

  1. L* = {ε} ∪ L·L* = {ε} ∪ L*·L. (Because L* contains 0 copies (ε) or at least one: first piece shows left recursion.)
  2. (L*)* = L*. (Kleene star is idempotent.)
  3. L+ = L·L* and L* = L+ ∪ {ε}.
  4. Concatenation is associative: (L1·L2)·L3 = L1·(L2·L3). (Use concatenation of strings and reassociation.)
  5. Concatenation distributes over union: L·(M ∪ N) = (L·M) ∪ (L·N); (M ∪ N)·L = (M·L) ∪ (N·L).
  6. Concatenation is not commutative in general: L·M ≠ M·L in general (give simple counterexample: {a}·{b} = {ab} ≠ {ba} = {b}·{a}).
  7. De Morgan laws hold for set operations: (L ∪ M)^c = L^c ∩ M^c, (L ∩ M)^c = L^c ∪ M^c, where complement is relative to Σ*. Also: for reversal, rev(L·M) = rev(M)·rev(L) and rev(L*) = (rev(L))*.

Closure properties (exact statements you may be asked to prove):

  • Regular languages: closed under union, intersection, difference, complement, concatenation, Kleene star, reversal, homomorphism, inverse homomorphism, substitution (where each s(a) is regular), and left and right quotient by any language — in practice proofs use NFA/DFA constructions or regular expressions.

  • Context-free languages (CFLs): closed under union, concatenation, Kleene star, homomorphism, inverse homomorphism, and reversal. They are also closed under intersection with regular languages (i.e., L_cfl ∩ L_reg is CFL), and hence under difference with regular languages (L \ R = L ∩ R^c) since regular languages are closed under complement. Not closed under intersection or complement in general.

How to prove closure for regular languages (standard constructions students must know):

  • Union (NFA method): Given NFAs N1 = (Q1, Σ, Δ1, q1, F1), N2 = (Q2, Σ, Δ2, q2, F2), construct N with new start q0 and ε-transitions q0 → q1 and q0 → q2. Final states F1 ∪ F2. Draw: a new start state with two epsilon arrows to the two start states; include both NFAs disjointly.

  • Concatenation (NFA): connect each final state of N1 with an ε-transition to the start state of N2; make final states F2; if N1 accepts ε, handle carefully (add ε transitions appropriately).

  • Kleene star (NFA): new start state q0 which is final, add ε from q0 to old start q1, and ε from each old final back to q1 and to q0. Draw: loop structure enabling zero or more runs.

  • Complement (DFA): convert NFA to complete DFA (subset construction, ensure every state has transitions for each symbol; add trap state if needed), then complement by swapping final and non-final states.

  • Intersection (DFA product): Given DFAs D1 = (Q1, Σ, δ1, q1, F1) and D2 = (Q2, Σ, δ2, q2, F2), build D = (Q1×Q2, Σ, δ, (q1,q2), F1×F2) with δ((p,r), a) = (δ1(p,a), δ2(r,a)); D recognizes L1 ∩ L2.

For CFLs, provide grammar-based constructions: union by new start with two alternatives S → S1 | S2; concatenation S → S1 S2; and star S → S S1 | ε (where S1 is grammar for the base language). For showing non-closure under intersection, standard counterexample uses languages whose intersection gives {a^n b^n c^n}.

When an exam asks for a proof, the examiner expects either a construction (automaton/grammar) with clear description, or a rigorous algebraic/inductive argument.

Formulas

Σ — alphabet; finite nonempty set of symbols; applies always. Σ* — set of all finite strings over Σ; includes ε. ε — the empty string; length |ε| = 0. L ⊆ Σ* — a language is a set of strings; no SI unit applies. L1 ∪ L2 — union; means any string in L1 or L2. L1 ∩ L2 — intersection; means any string in both L1 and L2. L1 · L2 — concatenation; each element is xy with x ∈ L1, y ∈ L2. L^0 = {ε}; L^{n+1} = L · L^n — language power; applies for n ≥ 0. L* = ⋃_{i=0}^∞ L^i; L+ = ⋃_{i=1}^∞ L^i = L·L* — Kleene star and positive closure. rev(L) = { rev(w) | w ∈ L } — reversal of language. h: Σ1* → Σ2* — homomorphism defined by h(a) for each symbol a ∈ Σ1; extended to strings by concatenation. h(L) = { h(w) | w ∈ L }, h^{-1}(M) = { w | h(w) ∈ M } — inverse homomorphism.

(Notes: these are symbolic definitions; no physical units are involved.)

Worked examples

Example 1 — Basic computations of concatenation and star Let Σ = {a, b}. Let L1 = {a, ab} and L2 = {b, ε}.

  1. L1·L2 = { x y | x ∈ L1, y ∈ L2 } = { a·b, a·ε, ab·b, ab·ε } = { ab, a, abb, ab } = { a, ab, abb }.
    • Step: compute each pair, then remove duplicates.
  2. L2·L1 = { b·a, b·ab, ε·a, ε·ab } = { ba, bab, a, ab }.
    • Shows concatenation order matters.
  3. L1^2 = L1·L1 = { a·a, a·ab, ab·a, ab·ab } = { aa, aab, aba, abab }.
  4. L1* = {ε} ∪ L1 ∪ L1^2 ∪ ... — list first few: { ε, a, ab, aa, aab, aba, abab, ... }. Final answers: L1·L2 = { a, ab, abb } (bold in exam), L2·L1 = { a, ab, ba, bab }.

Example 2 — Prove regular languages are closed under union (NFA construction) Given DFAs or NFAs for L1 and L2, construct an NFA for L1 ∪ L2 by:

  • Draw both machines disjointly.
  • Add a new start state q0 with ε-transitions to the two original start states.
  • Make final states the union of the two final sets. Correctness sketch: any string accepted by either machine can be accepted by first taking the ε to its start and running that machine; conversely any accepting run in constructed NFA corresponds to a run in one of the components. Describe diagram: draw new start state q0 (circle with arrow) and two ε-labelled arrows to two existing start states; keep the rest of components unchanged.

Example 3 — CFLs not closed under intersection (exam model answer) Let Σ = {a, b, c}. Define L1 = { a^i b^i c^j | i, j ≥ 0 } — context-free (grammar: S → A C; A → a A b | ε; C → c C | ε). Define L2 = { a^i b^j c^j | i, j ≥ 0 } — context-free (grammar: S → A B; A → a A | ε; B → b B c | ε). Then L1 ∩ L2 = { a^n b^n c^n | n ≥ 0 } which is a well-known non-context-free language (by pumping lemma for CFLs). Hence CFLs are not closed under intersection. A full answer explains grammars for L1 and L2 and then states the intersection and cites standard result that { a^n b^n c^n } is not CFL (brief pumping lemma argument or citation required).

Common mistakes

  • Assuming concatenation is commutative: many students write L·M = M·L without proof.
  • Thinking closure properties are universal: e.g., assuming CFLs closed under intersection or complement — they are not in general.
  • When constructing NFAs for star/concatenation, forgetting to add ε-transitions from final states back to the old start (for star) or from the new start to each original start (for union).

For your exam

Types of questions: definitions, short notes, proofs of closure properties, construct automata/grammar to show closure, counterexamples for non-closure, compute L* or L^n for small languages, trace subset-construction or NFA construction, diagram-based answers.

What a full-marks answer includes:

  • Exact definitions of terms used (alphabet, string, language, ε, ∅).
  • If proving closure: a precise construction (either automaton diagram described in words or grammar rules), explanation why construction accepts exactly the desired language, and mention of edge cases (ε present or not).
  • For non-closure: give languages of the required type whose intersection/operation yields a language of a known harder class (e.g., a^n b^n c^n) and justify that target language is not in the original family (brief pumping lemma or standard theorem citation).
  • Diagrams: label start state(s), final state(s), transitions (including ε if used); when asked to draw, draw NFAs/DFA boxes with states as circles and arrows; for union, show new start with ε to each start; for star show loop εs from finals back to start and new start final.

Quick check

  1. What is L^0 for any language L?
  2. Name two operations under which regular languages are closed and two under which CFLs are not closed (in general).
  3. How do you obtain the complement of a regular language given a DFA?

Answers: 1. L^0 = {ε}. 2. Regular: closed under union and Kleene star; CFLs: not closed under intersection and complement (in general). 3. Make the DFA complete (add trap state if needed) and swap accepting and non-accepting states.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?