\begin{frame}{Grammars} \begin{block}{} A \emph{grammar} $G = (V,T,S,P)$ consists of: \begin{itemize} \item finite set $V$ of \emph{non-terminals} (or \emph{variables})\\[.5ex] \item finite set $T$ of \emph{terminals}\\[.5ex] \item a \emph{start symbol} $S \in V$\\[.5ex] \item finite set $P$ of \emph{production rules} $x \to y$ where \begin{itemize} \item $x \in (V \cup T)^+$ containing at least one symbol from $V$ \item $y \in (V \cup T)^*$ \end{itemize} \end{itemize} \end{block} \begin{exampleblock}{} In the previous example: \begin{itemize} \item variables: $\langle$sentence$\rangle$, $\langle$article$\rangle$, $\langle$noun$\rangle$, $\langle$verb$\rangle$ \item terminals: the, a, farmer, cow, milks \item starting symbol: $\langle$sentence$\rangle$ \end{itemize} \end{exampleblock} \pause \begin{block}{} A grammar is \emph{context-free} if $x \in V$ for every rule $x \to y$. \end{block} \end{frame}