(Solved): Draw the derivation tree corresponding to the derivation in Example 5.1 Examples of Context-Free Lan ...

Examples of Context-Free Languages EXAMPLE 5.1 The grammar $G=(\{S\},\{a,b\},S,P)$, with productions $\begin{array}{l}S\to aSa\\ S\to bSb\\ S\to \lambda \end{array}$ is context-free. A typical derivation in this grammar is $S\Rightarrow aSa\Rightarrow aaSaa\Rightarrow aabSbaa\Rightarrow aabbaa$ This, and similar derivations, make it clear that $L(G)=\left\{w{w}^R:w\in \{a,b{\}}^{\ast }\right\}$ The language is context-free, but as shown in Example 4.8, it is not regular.