Alphabets, strings, languages; sets, union, intersection

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• Which phase cuts the source program into words and stamps their kinds? from Lesson 0.1.3
• Give one error the lexical analyzer catches and one it cannot catch. from Lesson 0.1.3
• What does a linker report when a function is used but defined nowhere? from Lesson 0.1.2

1 · The Story

📖

The Word Desk gets organised

Mira at the Word Desk gets a new typewriter for a project. It has only a few keys, and every word she can ever type is some row of those keys in order.

Mrs. Desai gives her two lists. List G holds Gujarati food words that English speakers use: dhokla, garba, roti, chai. List H holds Hindi ones: roti, chai, bhangra, lassi. “Make me one list of every word in either list,” says Mrs. Desai, “and a list of words in both. And for the auto-complete on the typists’ screens, tell me every way a word can start.”

Mira realises she needs precise words for these things: the set of keys, a typed word, a whole list of allowed words, and joining lists in different ways.

2 · Predict First

🤔

How many different beginnings (including the empty beginning before any letter is typed, and the whole word) does the word code have? Write your guess down. The answer is in the vault.

3 · Core Concept

Sets (the tool for lists)

A set is an unordered collection of distinct elements: {roti, chai}. x ∈ A means x is an element of A. A ⊆ B means every element of A is in B. The empty set ∅ has no elements.

• Union A ∪ B: elements in A or B (or both).
• Intersection A ∩ B: elements in both.
• Difference A − B: elements of A that are not in B.

Alphabet and string

An alphabet Σ is a finite, non-empty set of symbols, for example Σ = {a, b} or Σ = {0, 1} or all ASCII characters.

A string over Σ is a finite sequence of symbols from Σ, such as abba. Its length |w| is the number of symbols: |abba| = 4.

The empty string ε has length 0. It is a string, not a symbol of Σ.

Joining strings

Concatenation xy writes x then y: if x = ab and y = ba, xy = abba. ε is neutral: εw = wε = w. Powers: w² = ww, w⁰ = ε.

Parts of a string

For w = code:

• a prefix is a beginning: ε, c, co, cod, code;
• a suffix is an ending: ε, e, de, ode, code;
• a substring is any consecutive block: od, co, de, …

A string of length n has n + 1 prefixes and n + 1 suffixes (both counts include ε and w itself). A proper prefix is one other than w. If all n symbols are different, there are n(n+1)/2 non-empty substrings.

Languages

Σ* is the set of all strings over Σ, including ε. A language over Σ is any set of strings over Σ, that is, any subset of Σ*. The set of all valid C identifiers is a language; so is the set of all C programs.

Two tiny languages that look alike but are different: ∅ (no strings at all) and {ε} (exactly one string, the empty one).

Operations on languages

• Union L ∪ M: strings in L or in M.
• Concatenation LM = { xy : x ∈ L, y ∈ M }.
• Kleene star L* = {ε} ∪ L ∪ LL ∪ LLL ∪ …: zero or more strings from L joined.
• L⁺ = LL*: one or more.

Since LM is a set, duplicates collapse: |LM| ≤ |L| × |M|.

Story → compiler term

4 · Visual

G ∪ H has 6 words, G ∩ H has 2, and G − H = { dhokla, garba }.

The 5 prefixes and 5 suffixes of code (n = 4, so n + 1 = 5 each).

5 · Worked Examples

Example 1 Easy

List the prefixes and proper prefixes of code.

Solution

Prefixes: ε, c, co, cod, code (5 = n + 1). Proper prefixes: the same without code itself: 4. Like the auto-complete list for Mira’s typists, minus the finished word.

Convention note: some books also exclude ε from proper prefixes; say which you use when it matters.

Example 2 Medium

L = {a, ab} and M = {b, ε}. Find LM and its size.

Solution

All pairs: a·b = ab, a·ε = a, ab·b = abb, ab·ε = ab. As a set: {a, ab, abb}, size 3, not 4, because ab appeared twice. Just as a word in both of Mira’s dictionaries is still listed once in the union.

Example 3 GATE

How many distinct non-empty substrings does banana have?

Solution

Length 1: b, a, n (3). Length 2: ba, an, na (3). Length 3: ban, ana, nan (3). Length 4: bana, anan, nana (3). Length 5: banan, anana (2). Length 6: banana (1). Total 15, fewer than 6·7/2 = 21 because letters repeat.

6 · Shortcuts

⚡

Counts for a string of length n: prefixes n + 1, suffixes n + 1, non-empty substrings n(n+1)/2 when all symbols are distinct (add 1 if ε counts). Valid when: the symbols are all different for the substring formula; with repeats, list them by length.

⚡

|A ∪ B| = |A| + |B| − |A ∩ B|. Valid when: finite sets.

7 · GATE Traps

⚠️

• ε is a string (of length 0), not a symbol, and not the empty set.
• ∅ ≠ {ε}: L∅ = ∅ for any L, but L{ε} = L.
• Concatenation of languages removes duplicates, so |LM| can be smaller than |L||M|.
• Check whether a question counts ε and w itself as prefixes; “proper” excludes w.

8 · Memory Hook

🧠

Alphabet = keys, string = typed word, language = a dictionary. ∪ “or”, ∩ “and”, − “but not”.

9 · Connect the Dots

We can now talk about strings and languages. The lexical analyzer must describe languages like “all valid names” or “all numbers” in one short line instead of listing infinitely many strings. The next primer gives that notation.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markPrefixes

How many prefixes (including ε and the string itself) does abcde have?

Numerical answer: ________

Q2MCQ1 markEmpty string

Which statement is true?

• (A) ∅ and {ε} are the same language
• (B) {ε} contains exactly one string
• (C) ε is a symbol of every alphabet
• (D) concatenating any language with ∅ gives the same language

Q3MSQ1 markΣ*

Let Σ = {0, 1}. Which are true?

• (A) ε ∈ Σ*
• (B) Σ* is a finite set
• (C) Every language over Σ is a subset of Σ*
• (D) 0110 ∈ Σ*

Q4NAT1 markSubstrings

How many distinct non-empty substrings does aab have?

Numerical answer: ________

Q5NAT1 markSets

A = {1, 2, 3, 4}, B = {3, 4, 5}. What is |(A ∪ B) − (A ∩ B)|?

Numerical answer: ________

11 · Rule Card

• Alphabet Σ: finite set of symbols. String: finite sequence; |w| its length; ε has length 0.
• Concatenation xy; εw = w.
• Length-n string: n + 1 prefixes, n + 1 suffixes; n(n+1)/2 non-empty substrings if symbols distinct.
• Language = set of strings ⊆ Σ*. ∅ ≠ {ε}.
• LM = {xy}; L* = {ε} ∪ L ∪ LL ∪ …; L⁺ = LL*.
• Sets: ∪, ∩, −; |A ∪ B| = |A| + |B| − |A ∩ B|.

12 · Concept Ledger

setelement ∈subset ⊆empty set ∅union ∪intersection ∩difference −alphabet Σstringlength |w|empty string εconcatenationprefix / suffix / substringΣlanguageKleene star LL⁺

13 · Answer Vault