Let be a context-free grammar. Recall that a word is generated by if it is
The second condition simply says that there is a finite sequence of derivation steps, starting from , and ending at :
For each derivation step , there is a production in such that
Note that is a non-terminal (an element of ), and are words over .
Definition. Using the notations above, if is the leftmost non-terminal occurring in , then we say the derivation step is leftmost. Dually, is rightmost if is the rightmost non-terminal occurring in .
Equivalently, is leftmost (or rightmost) if (or ) is a word over .
A derivation is said to be leftmost (or rightmost) if each of its derivation steps is leftmost (or rightmost).
Example. Let be the grammar consisting of as terminals, as non-terminals (with as the starting symbol), and , , , , and as productions. is clearly context-free.
The word can be generated by by the following three derivations:
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.
One of the main properties of a context-free grammar is that every word generated by is derivable by a leftmost (correspondingly rightmost) derivation, which can be used to show that for every context-free language , there is a pushdown automaton accepting every word in , and conversely that the set of words accepted by a pushdown automaton is context-free.
Leftmost derivations may be defined for any arbitrary formal grammar satisfying the condition
(*) no terminal symbols occur on the left side of any production.
Given two words , we define if there is a production such that and such that is a terminal word. By taking the reflexive transitive closure of , we have the leftmost derivation . It can be shown that for any grammar satisfying condition (*), the language consisting of terminal words generated by via leftmost derivations is always context-free.
- 1 S. Ginsburg The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York (1966).
- 2 D. C. Kozen Automata and Computability, Springer, New York (1997).
|Date of creation||2013-03-22 18:54:50|
|Last modified on||2013-03-22 18:54:50|
|Last modified by||CWoo (3771)|