\begin{frame}{Formal Languages} \begin{goal}{} A \emph{formal language} is a \emph{set of words}. \end{goal} \pause\bigskip \begin{block}{} A \emph{(formal) language} $L$ is a subset of $\Sigma^*$, that is, $L \subseteq \Sigma^*$. \end{block} Here $\Sigma^*$ is the set of all words over $\Sigma$. \pause\bigskip \begin{exampleblock}{} The set of all parseable C programs form a language. \end{exampleblock} \pause \begin{exampleblock}{} $\{\,ab,\; aab,\; bbaaabb\,\}$ is a finite language over $\Sigma = \{a,b\}$ \end{exampleblock} \pause \begin{exampleblock}{} $\{\,ab^n a \mid n \geq 1\,\}$ is an infinite language over $\Sigma = \{a,b\}$: \begin{talign} \{\,aba,\; abba,\; abbba,\; abbbba,\; \ldots\,\} \end{talign} \end{exampleblock} \pause \begin{exampleblock}{} $\{\, a^nb^n \mid n \geq 0 \,\}$ is an infinite language over $\Sigma = \{a,b\}$: \begin{talign} \{\,\lambda,\; ab,\; aabb,\; aaabbb,\; aaaabbbb,\; \ldots \,\} \end{talign} \end{exampleblock} \end{frame}