Derivations in CFGs: Leftmost & Rightmost

1. From Rules to Strings: The Derivation Process

A derivation is a sequence of steps that starts with the start symbol and ends with a string of terminals. In each step, we replace one non-terminal with the body of one of its production rules.

Let's formalize this. Given a CFG, the relation $\Rightarrow$ (read as "yields in one step") means that we can get from one string to another by applying a single production rule. For a string $\alpha A\beta$, where $A$ is a non-terminal and $\alpha$ and $\beta$ are any strings of grammar symbols (terminals or non-terminals), if there's a production $A\to \gamma$, we can write:
$\alpha A\beta \Rightarrow \alpha \gamma \beta$
This means we've replaced $A$ with $\gamma$. The string $\alpha A\beta$ is what we call a sentential form—an intermediate string containing terminals and/or non-terminals derived from the start symbol.

When we can get from a string $\alpha$ to a string $\beta$ in one or more steps, we write $\alpha \stackrel{+}{\Rightarrow }\beta$. If it takes zero or more steps (i.e., $\alpha$ can be the same as $\beta$), we use the reflexive, transitive closure, written as $\alpha \stackrel{\ast }{\Rightarrow }\beta$.

A string $w$ consisting only of terminals ($w\in {\Sigma }^{\ast }$) is in the language of the grammar $G$, denoted $L(G)$, if it can be derived from the start symbol $S$. Formally: $w\in L(G)$ if and only if $S\stackrel{+}{\Rightarrow }w$.

To see a more rigorous treatment of these definitions, you can refer to the following text.

2. Resolving Ambiguity: Leftmost and Rightmost Derivations

Consider the simple expression grammar:
$E\to E+E\mid E\ast E\mid \text{id}$

If we start with $E$ and apply the rule $E\to E+E$, our sentential form is $E+E$. Now, we have two non-terminals, the left $E$ and the right $E$. Which one should we expand next? The choice matters and can lead to different derivation sequences.

To bring order to this process, we adopt a convention. There are two standard strategies:

1. Leftmost Derivation (${\Rightarrow }_{lm}$): At each step, always expand the leftmost non-terminal in the sentential form.
2. Rightmost Derivation (${\Rightarrow }_{rm}$): At each step, always expand the rightmost non-terminal in the sentential form.

These strategies are not just for convenience; they are fundamental to the theory and practice of parsing. Most parsers are built to systematically find either a leftmost or a rightmost derivation.

Let's see these two strategies in action.

As you saw, even though the intermediate steps are different, both strategies can successfully generate the target string. Let's look at the formal definitions for these derivation types.

3. Let's Practice

Now, let's work through an example together. Consider the following grammar $G$:

• Productions:
  1. $S\to AB$
  2. $A\to aAb$
  3. $A\to \epsilon$
  4. $B\to bB$
  5. $B\to \epsilon$
• Start Symbol: $S$
• Terminals: $\{a,b\}$

Let's derive the string abbbb using a leftmost derivation. At each step, we identify the leftmost non-terminal and replace it.

1. $S{\Rightarrow }_{lm}AB$ (Rule 1)
2. ${\Rightarrow }_{lm}aAbB$ (Rule 2, replacing the leftmost non-terminal $A$)
3. ${\Rightarrow }_{lm}a\epsilon bB$ (Rule 3, replacing the new leftmost non-terminal $A$)
   • This simplifies to $abB$.
4. ${\Rightarrow }_{lm}abbB$ (Rule 4, replacing the leftmost non-terminal $B$)
   • This is $abbB$.
5. ${\Rightarrow }_{lm}abbbB$ (Rule 4, replacing $B$)
   • This is $abbbB$.
6. ${\Rightarrow }_{lm}abbb\epsilon$ (Rule 5, replacing $B$)
   • This simplifies to $abbbb$.

We have successfully derived the string. The sequence $S{\Rightarrow }_{lm}AB{\Rightarrow }_{lm}aAbB{\Rightarrow }_{lm}abB{\Rightarrow }_{lm}abbB{\Rightarrow }_{lm}abbbB{\Rightarrow }_{lm}abbbb$ is the complete leftmost derivation.

The image below shows both a leftmost and rightmost derivation for this exact problem, which is a great way to check your understanding.

An important theoretical result (stated as Proposition 7.1 in the UPenn notes) is that if a string can be generated by a grammar at all, it has both a leftmost and a rightmost derivation. This makes these two systematic approaches universally applicable.

Conclusion

In this lesson, we transitioned from the static definition of a CFG to the dynamic process of using it to generate strings. We learned that this process, called derivation, is a sequence of substitutions guided by the grammar's production rules.

Key Takeaways:

• A derivation is a sequence of applications of production rules that transforms the start symbol into a string of terminals.
• A sentential form is any intermediate string in a derivation.
• To resolve the ambiguity of which non-terminal to expand next, we use standard strategies.
• A leftmost derivation (${\Rightarrow }_{lm}$) always expands the leftmost non-terminal.
• A rightmost derivation (${\Rightarrow }_{rm}$) always expands the rightmost non-terminal.
• Any string that belongs to a context-free language has both a leftmost and a rightmost derivation.

Preview of the Next Lesson:
The sequential lists of steps in a derivation can be difficult to visualize. A much more intuitive way to represent a derivation is with a tree structure. In the next lesson, we will learn how to construct parse trees from derivations. This graphical representation will not only make derivations easier to understand but will also lead us directly to the crucial concept of grammatical ambiguity, a property that has significant implications for programming language design.