Alphabet, Language, Grammar, and Derivation: Definitions and Relationships in Formal Language Theory

In formal language theory, we study how strings over symbols can be generated or recognized. Four foundational notions—Alphabet , Language , Grammar , and Derivation—connect in a precise way:

Here, a grammar generates strings via derivations; the set of all strings that can be derived forms the language. This relationship is central to how formal grammars specify languages.

Core definitions (with roles)

1. Alphabet (Σ): The basic symbol inventory.

   • Example: $\Sigma=\{a,b\}$

2. Strings and $\Sigma^{*}$:

   • A string is any finite sequence of symbols from $\Sigma$ (including the empty string).
   • $\Sigma^{*}$ denotes the set of all strings over $\Sigma$.

3. Language (L): A subset of $\Sigma^{*}$.

   • Example: $L=\{a^n b^n \mid n\ge 0\}$ over $\Sigma=\{a,b\}$

4. Grammar (G): A formal mechanism that uses production rules to generate strings.

   • Typically written $G=(V,\Sigma,R,S)$ where:
     • $V$ = variables (nonterminals),
     • $\Sigma$ = terminals (alphabet symbols),
     • $R$ = productions (rules),
     • $S$ = start symbol.

5. Derivation (⇒): The process of repeatedly applying productions starting from $S$ to reach a string.

   • Notation: $S \Rightarrow w$ for one step; $S \Rightarrow^{*} w$ for zero or more steps.

Relationship between the four terms

1) Alphabet $\Sigma$ sets the “universe” of strings

Once $\Sigma$ is fixed, every string relevant to the theory is an element of $\Sigma^{*}$. Every language is a selection from this universe.

Example: Let $\Sigma=\{0,1\}$. Then $010 \in \Sigma^{*}$.

---

2) Language $L$ is a set of strings over $\Sigma$

A language is defined as a subset of $\Sigma^{*}$:

$$L \subseteq \Sigma^{*}.$$

Example:

• $\Sigma=\{0,1\}$
• $L=\{w \in \Sigma^{*} \mid w \text{ ends with } 1\}$
  Then $001\in L$, but $000\notin L$.

---

3) Grammar $G$ generates (defines) the language

A grammar specifies which strings belong to the language by providing rules for building them.

A string $w$ over $\Sigma$ belongs to the language of $G$ exactly when there exists a derivation from the start symbol:

$$w \in L(G) \quad \text{iff} \quad S \Rightarrow^{*} w.$$

---

4) Derivation is the “witness” that a string is in the language

Membership is not just conceptual; derivations provide a constructive proof:

• Start with $S$ (the grammar’s start symbol).
• Apply productions to rewrite variables into other variables/terminals.
• After finitely many steps, if the result contains no variables (only terminals), you obtain a generated string.

Derivation trace (the same example, shown clearly)

Using $G$:

• $S \to aSb$
• $S \to ab$

Derivation for $aabb$:

$$S \Rightarrow aSb \Rightarrow a(ab)b = aabb.$$

A grammar may generate many strings; the language is the set of all strings for which such derivations exist.