\begin{frame}{Languages Generated by Grammars} \begin{block}{} The \emph{language generated} by a grammar $G = (V,T,S,P)$ is \begin{talign} L(G) = \{\, w \in T^* \mid S \Rightarrow^* w \,\} \end{talign} \end{block} \bigskip The language consists of all words that \begin{itemize} \smallskip \item contain only terminal letters (no variables), and \item can be derived from the start symbol \end{itemize} \pause\bigskip \begin{exampleblock}{} $G = (\{S\}, \{a,b\}, S, P)$, where $P$ consists of \begin{talign} S &\to aSb & S &\to \lambda \end{talign} What is the language generated by $G$? \begin{talign} L(G) = \mpause[1]{\{\, a^nb^n \mid n \geq 0 \,\}} \end{talign} \end{exampleblock} \pause Recall that this language is not regular. \end{frame}