LeftmostDerivation 2009-05-06 08:39:02 2009-08-24 05:35:39 Definition context-free language rightmost derivation \usepackage{amssymb,amscd} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{mathrsfs} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions \usepackage{amsthm} % making logically defined graphics \usepackage{xypic} \usepackage{pst-plot} % define commands here \newcommand*{\abs}[1]{\left\lvert #1\right\rvert} \newtheorem{prop}{Proposition} \newtheorem{thm}{Theorem} \newtheorem{ex}{Example} \newcommand{\real}{\mathbb{R}} \newcommand{\pdiff}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\mpdiff}[3]{\frac{\partial^#1 #2}{\partial #3^#1}} Let $G=(\Sigma, N, P, \sigma)$ be a context-free grammar. Recall that a word $v$ is generated by $G$ if it is \begin{itemize} \item a word over the set $T:=\Sigma - N$ of terminals, and \item derivable from the starting symbol $\sigma$. \end{itemize} 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 \begin{eqnarray*} v_i &=& aXb, \\ v_{i+1} &=& awb. \end{eqnarray*} Note that $X$ is a non-terminal (an element of $N$), and $a,b,w$ are words over $\Sigma$. \textbf{Definition}. Using the notations above, if $X$ is the leftmost non-terminal occurring in $v_i$, then we say the derivation step $v_i\to v_{i+1}$ is \emph{leftmost}. Dually, $v_i\to v_{i+1}$ is \emph{rightmost} if $X$ is the rightmost non-terminal 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 \emph{leftmost} (or \emph{rightmost}) if each of its derivation steps is leftmost (or rightmost). \textbf{Example}. Let $G$ be the grammar consisting of $a,b$ as terminals, $\sigma,X,Y,Z$ as non-terminals (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 context-free. The word $a^2b^2=aabb$ can be generated by $G$ by the following three derivations: \begin{enumerate} \item $\sigma \to ZY \to X\sigma Y \to XXYY \to XaYY \to XaYb \to Xabb \to aabb$, \item $\sigma \to ZY \to X\sigma Y \to a \sigma Y \to a XYY \to aaYY \to aabY \to aabb$, \item $\sigma \to ZY \to Zb \to X\sigma b \to XXY b\to XXbb \to Xabb \to aabb$. \end{enumerate} 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. \textbf{Remarks}. \begin{itemize} \item One of the main properties of a context-free 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 context-free 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 context-free. \item Leftmost derivations may be defined for any arbitrary formal grammar $G$ satisfying the condition \begin{quote} (*) no terminal symbols occur on the left side of any production. \end{quote} 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 context-free. \end{itemize} \begin{thebibliography}{9} \bibitem{sg} S. Ginsburg {\em The Mathematical Theory of Context-Free Languages}, McGraw-Hill, New York (1966). \bibitem{dk} D. C. Kozen {\em Automata and Computability}, Springer, New York (1997). \end{thebibliography}