You are here
Homeleftmost derivation
Primary tabs
leftmost derivation
Let $G=(\Sigma,N,P,\sigma)$ be a contextfree grammar. Recall that a word $v$ is generated by $G$ if it is

derivable from the starting symbol $\sigma$.
The second condition simply says that there is a finite sequence of derivation steps, starting from $\sigma$, and ending at $v$:
$\sigma=v_{0}\to v_{1}\to\cdots\to v_{n}=v$ 
For each derivation step $v_{i}\to v_{{i+1}}$, there is a production $X\to w$ in $P$ such that
$\displaystyle v_{i}$  $\displaystyle=$  $\displaystyle aXb,$  
$\displaystyle v_{{i+1}}$  $\displaystyle=$  $\displaystyle awb.$ 
Note that $X$ is a nonterminal (an element of $N$), and $a,b,w$ are words over $\Sigma$.
Definition. Using the notations above, if $X$ is the leftmost nonterminal occurring in $v_{i}$, then we say the derivation step $v_{i}\to v_{{i+1}}$ is leftmost. Dually, $v_{i}\to v_{{i+1}}$ is rightmost if $X$ is the rightmost nonterminal occurring in $v_{i}$.
Equivalently, $v_{i}\to v_{{i+1}}$ is leftmost (or rightmost) if $a$ (or $b$) is a word over $T$.
A derivation is said to be leftmost (or rightmost) if each of its derivation steps is leftmost (or rightmost).
Example. Let $G$ be the grammar consisting of $a,b$ as terminals, $\sigma,X,Y,Z$ as nonterminals (with $\sigma$ as the starting symbol), and $\sigma\to XY$, $X\to a$, $Y\to b$, $\sigma\to ZY$, and $Z\to X\sigma$ as productions. $G$ is clearly contextfree.
The word $a^{2}b^{2}=aabb$ can be generated by $G$ by the following three derivations:
1. $\sigma\to ZY\to X\sigma Y\to XXYY\to XaYY\to XaYb\to Xabb\to aabb$,
2. $\sigma\to ZY\to X\sigma Y\to a\sigma Y\to aXYY\to aaYY\to aabY\to aabb$,
3. $\sigma\to ZY\to Zb\to X\sigma b\to XXYb\to XXbb\to Xabb\to aabb$.
The second is leftmost, the third is rightmost, and the first is neither.
Note that in every derivation, the first and last derivation steps are always leftmost and rightmost.
Remarks.

One of the main properties of a contextfree grammar $G$ is that every word generated by $G$ is derivable by a leftmost (correspondingly rightmost) derivation, which can be used to show that for every contextfree language $L$, there is a pushdown automaton accepting every word in $L$, and conversely that the set of words accepted by a pushdown automaton is contextfree.

Leftmost derivations may be defined for any arbitrary formal grammar $G$ satisfying the condition
(*) no terminal symbols occur on the left side of any production.
Given two words $u,v$, we define $u\Rightarrow_{L}v$ if there is a production $A\to B$ such that $u=xAy$ and $v=xBy$ such that $x$ is a terminal word. By taking the reflexive transitive closure of $\Rightarrow_{L}$, we have the leftmost derivation $\Rightarrow_{L}^{*}$. It can be shown that for any grammar $G$ satisfying condition (*), the language $L_{L}(G)$ consisting of terminal words generated by $G$ via leftmost derivations is always contextfree.
References
 1 S. Ginsburg The Mathematical Theory of ContextFree Languages, McGrawHill, New York (1966).
 2 D. C. Kozen Automata and Computability, Springer, New York (1997).
Mathematics Subject Classification
68Q45 no label found68Q42 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections