chap2_CFG1.tex

\input{header}

\AtBeginSubsection[]
{
	\begin{frame}<beamer>
		\frametitle{Outline}
		\tableofcontents[current,currentsubsection]
	\end{frame}
}

\begin{document}

 \begin{frame}[allowframebreaks] \frametitle{Context-free languages}
  \begin{itemize}
\item In Chapter 1 we consider two ways to describe languages

\item [] automata \& regular expressions
\item Context-free grammars (CFG)

\item [] More powerful than automata
\item CFG is used in compilers and interpreters
for parsers to read programs

\end{itemize}\end{frame}

\begin{frame}[allowframebreaks] \frametitle{Context-free grammars}
  \begin{itemize}
  \item
    A grammar $G_1$:
\begin{eqnarray*}
  && A \rightarrow 0A1\\
&& A \rightarrow B\\
&& B \rightarrow \#
\end{eqnarray*}
Each one is called a substitution rule
\item Variables: $A,B$ (capital letters)
\item Terminals: 0, 1, \# (lowercase letters,
number, special symbols)
\item Start variable: $A$
\item A grammar: a collection of substitution rules
\item Derivation: $G_1$ generates 
000\#111
\begin{equation*}
  \begin{split}
&  A
\Rightarrow 0A1 \Rightarrow
00A11 
\Rightarrow 000A111\\
& 
\Rightarrow 000B111
\Rightarrow 000\#111
\end{split}
\end{equation*}
\item Parse tree

\item [] Fig 2.1

\framebreak  

\scalebox{0.85}{
  \begin{forest}
for tree={
    parent anchor=south,
    child anchor=north,
    if n children=0{
      font=\itshape,
      tier=terminal,
    }{},
  }    
  [A
   [ 
    [0
    ]
   ]
   [A
    [
    [0
    ]
    ]
    [A
     [[0
     ]]
     [A
      [B
       [\#
       ]
      ]
     ]
     [[1
     ]]
    ]
    [[1
    ]]
   ] 
   [[1
   ]]
  ]
\end{forest}
}
\item $L(G)$: language of grammar
\item For the CFG example we just discussed, 
  \begin{equation*}
L(G_1) = 
\{0^n \#  1^n\mid n \geq 0\}
\end{equation*}

\item CFG is more powerful than regular expressions because we showed earlier
that this language is not regular

\item Representation of rules:
  \begin{center}
  $A \rightarrow 0A1$
and $A \rightarrow B$
\end{center}
is often simplified to
\begin{center}
$A \rightarrow 0A1\mid B$
\end{center}
\item Example
  \begin{eqnarray*}
    \langle  \text{S} \rangle & \Rightarrow & \langle  \text{Noun-Phrase}\rangle \langle  \text{Verb-Phrase} \rangle\\
& \Rightarrow & \langle  \text{Complex-Noun} \rangle\langle  \text{Verb-Phrase}\rangle\\
& \Rightarrow & \langle  \text{Article} \rangle\langle  \text{Noun}\rangle\langle  \text{Verb-Phrase}\rangle\\
& \Rightarrow & {\sf a} \langle  \text{Noun} \rangle \langle  \text{Verb-Phrase} \rangle\\
& \Rightarrow & {\sf a \; boy} \langle  \text{Verb-Phrase}\rangle\\
& \Rightarrow & {\sf a \; boy} \langle  \text{Complex-Verb}\rangle\\
& \Rightarrow & {\sf a \; boy} \langle  \text{Verb}\rangle\\
& \Rightarrow & {\sf a \; boy \; sees}
  \end{eqnarray*}

\item Why called ``context-free'' ?

\item [] Rules independent of context
  
\end{itemize}\end{frame}

\begin{frame}[allowframebreaks]
  \frametitle{Formal definition of a context-free
    grammar}
    \begin{itemize}
\item $(V,\Sigma, R, S)$

\item [] $V$: variables, finite set

\item [] $\Sigma$: terminals, finite set

\item [] $R$: rules
\begin{center}
  variable
$\rightarrow$ strings of variables and
terminals (including $\epsilon$)
\end{center}

\item $S\in V$, start variable

\item For the example $G_1$:
\begin{eqnarray*}
  && A \rightarrow 0A1\\
&& A \rightarrow B\\
&& B \rightarrow \#
\end{eqnarray*}

$V=\{A,B\}, \Sigma=\{0,1,\#\}, S = A, R:$
the above three rules
\end{itemize}
\end{frame}

\begin{frame}[allowframebreaks]
  \frametitle{Derivation of strings}
    \begin{itemize}
\item If $u,v,w$ are strings and a rule  $A \rightarrow
w$ is applied, then we say
\begin{center}
$uAv$ yields $uwv$
\end{center}
and this is denoted as
\begin{equation*}
uAv \Rightarrow uwv
\end{equation*}
\item if 
  \begin{center}
$u=v$ or 
$u \Rightarrow u_1 \Rightarrow \cdots \Rightarrow
u_k \Rightarrow v$
\end{center}
then we say
\begin{equation*}
u \mydef{*}{\Rightarrow} v 
\end{equation*}
\item Language of a CFG
  \begin{equation*}
\{ w \in \Sigma^*\mid 
S \mydef{*}{\Rightarrow} w\}
\end{equation*}
\end{itemize}\end{frame} 

\begin{frame}[allowframebreaks] \frametitle{Example 2.3}
  \begin{itemize}

\item $G_3
=(\{S\}, \{a,b\}, R, S)$

\item[]  R:
\begin{equation*}
  S \rightarrow aSb\mid SS \mid \epsilon
\end{equation*}
\item What is the language?
\item If we treat $a, b$ respectively as ( and ), then
  we have
  \begin{center}
all valid nested parentheses
\end{center}
\end{itemize}\end{frame}


\end{document}