\documentclass[11pt]{article}

\usepackage{hevea,xspace,graphicx,paralist}

\oddsidemargin 0cm
\textwidth 17cm

\newcommand{\question}[1]{#1}
\newcommand{\answer}[1] { {\sf #1}  {\vspace{6ex}}  }
\newcommand{\ignore}[1] {}
\newcommand{\ie}{{\em i.e.},\xspace}
\begin{document}

\thispagestyle{empty}

\begin{center}
\begin{Large}
{\bf CS 3100 -- Models of Computation -- Fall 2010}\\
{\bf Notes for Lecture 11 on Context-Free Grammars}
\end{Large}
\end{center}



\section{What is a CFG?}

A CFG is a compact description of a context-free language CFL.

Let's get some terminology straight:
Grammar versus Language.

We have already seen it: Regular expressions (the ``grammar'') versus
regular languages (potentially infinite set of strings).

All regular languages are context-free (but not vice versa).

A CFL is not regular, but still has a simple enough structure
that it can be recognized using a single-stack automaton.

They arise in programming languages and all kinds of other situations.

The syntax of regular expressions is a CFL! 

The key pattern in a CFG is ``(((())))''  or ``(())()(())((())(()))''

In fact, all CFL strings are ``grown inside out''

OK let's illustrate these facts now.

\begin{compactitem}
\item $(\{0,1\},\{S\},S,\emptyset)$ is a CFG

\item $(\{0,1\},\{S,T\},S,P)$ is a CFG where $P$ is this set of rules:
  {\small\begin{verbatim}
  S -> 0T | 0
  T -> 1T | 1
  \end{verbatim}}

Notice that this CFG is the same as the one below:
  {\small\begin{verbatim}
  S -> 0T  
  S -> 0
  T -> 1T 
  T -> 1
  \end{verbatim}}

\item $(\{0,1\},\{S,T,U\},S,P)$ is a CFG where $P$ is this set of rules:
  {\small\begin{verbatim}
  S -> TU
  T -> 0T | 0
  U -> 1U | e  -- epsilon
  \end{verbatim}}

\item Strictly this is a CFG although no one would want to use it:
   $(\{0,1\},\{S\},S,P)$ is a CFG where $P$ is this set of rules:
  {\small\begin{verbatim}
  S -> S
  \end{verbatim}}

\item Strictly this is a CFG although no one would want to use it:
   $(\{0,1\},\{S\},S,P)$ is a CFG where $P$ is this set of rules:
  {\small\begin{verbatim}
  S -> e
  \end{verbatim}}

\item Strictly this is a CFG although no one would want to use it:
   $(\{0,1\},\{S,T\},S,P)$ is a CFG where $P$ is this set of rules:
  {\small\begin{verbatim}
  S -> e
  T -> 1
  \end{verbatim}}

\item $G = (\{0,1\},\{S,T,U\},S,P)$ is a CFG where $P$ is this set of rules:
  {\small\begin{verbatim}
  S -> TU
  T -> 0T | 0
  U -> 1U | 1  
  \end{verbatim}}
  {\bf although you should use a regular-expression whenever
  possible}, \ie, $0^+ 1^+$.

\item In $G$ above, see how you lose control of the ``balance'' between
  $0$s and $1$s. This is what regular languages do: ``forget counts''

\item CFGs also don't strictly count, but can {\em match up counts!}

 $G_{bal} = (\{0,1\},\{S\},S,P)$ is a CFG where $P$ is this set of rules:
  {\small\begin{verbatim}
  S -> 0S1 | e
  \end{verbatim}}
  grows inside out. It matches 0 with a 1, but then once the match is
  seen it ``forgets'' the exact numbers of 0s and 1s.

\end{compactitem}

\section{Tricks to Evolve a CFG ``Inside-Out''}

\noindent Let's understand the ``inside out'' trick well, because
this is how you will be designing most CFGs. Here on, I'll merely
show you the rules:

\begin{compactitem}
\item  What does this CFG generate?
 {\small\begin{verbatim}
 S -> 0 S 1 S | 1 S 0 S | e
 \end{verbatim}}  

\item Do things change if I add one more rule?
 {\small\begin{verbatim}
 S -> 0 S 1 S | 1 S 0 S | S S | e
 \end{verbatim}}  

\item When asked to do ``obtain a CFG for all strings where the number
 of zeros are twice as many as the number of 1s'', let us
 consider these attempts:

 \begin{compactitem}
 \item How about:
  {\small\begin{verbatim}
  S -> 0 0 1 S | 0 1 0 S | 1 0 0 S
  \end{verbatim}}

 \item How about:
  {\small\begin{verbatim}
  S -> 0 S 0 S 1 | 0 S 1 S 0 | 1 S 0 S 0
  \end{verbatim}}

 \item Do we need this:
  {\small\begin{verbatim}
  S -> S 0 S 0 S 1 S | S 0 S 1 S 0 S | S 1 S 0 S 0 S
  \end{verbatim}}
 \end{compactitem}

\item When asked to design a grammar for $\{0^n 1^{m} \;\mid\; n,m \ge 0\}$
  go tell them ``use a regular expression!''

\item When asked to design a grammar for 
    $G_{001}=\{0^{2n} 1^{n} \;\mid\; n \ge 0\}$,
  can you tell them ``use a regular expression?''
  Build sufficient intuitions. If sure it is not a reg language,
  then use the Pumping Lemma.

\item A CFG for     $G_{001}$ : wrong attempt (why)?
  {\small\begin{verbatim}
  S -> T U
  T -> 00 T | e
  U -> 1 U  | e
  \end{verbatim}}

\item The way to think of a CFG for $G_{001}$: you need to grow
  inside out! You can grow ``00.1'' inside out:
  {\small\begin{verbatim}
  S -> 00S1 | e
  \end{verbatim}}

\item Cool fact: Any CFG over a singleton alphabet is regular.
  What does this CFG generate?
  {\small\begin{verbatim}
  S -> ( S ) | S S | e
  \end{verbatim}}

  What does this CFG generate?
  {\small\begin{verbatim}
  S -> ( S ( | S S | e
  \end{verbatim}}

  What does this CFG generate?
  {\small\begin{verbatim}
  S -> 0 S 0 | S S | e
  \end{verbatim}}

\item Consider $L=\{a^i b^j c^k \;\mid\;i,j,k \ge 0\;\wedge\; 
    if(i=0)then\; j=k \}$.

\item Regular? (Naah!)

\item How to pump?  Not beginning with $a$!  Once you increase or decrease
  $a$ you don't fall out of the language!

\item Reverse and pump? Yes! IF original regular, reversal preserves
  regularity. But then can mangle reversal by pumping it out of shape.
  Hence original can't be regular.

\item  USING and ABUSING closure arguments:
  \begin{compactitem}
  \item USE:
    Show $\{w\;\mid\;w\;has\;equal\;number\;of\;0s\;and\;1s\}$ is non-regular.

    Hint: intersect with {\tt 0* 1*}. The language then becomes what?

    Can you show that language non-regular?
    
    Then original language is regular!

  \item ABUSE:
    Show $L_{eq}=\{w\;\mid\;w\;has\;equal\;number\;of\;0s\;and\;1s\}$ is non-regular.

    BAD Hint: intersect with {\tt 2 2*} (some junk).
    Resulting language is EMPTY.

    Empty is REGULAR.

    Hence original language is regular! (Naah!)
    

  \end{compactitem}
\end{compactitem}


\section{Consistency and Completeness}

Consistency: all the generated strings are correct according to the language.
Example: Is this palindromic? (Nahh!)
{\small\begin{verbatim}
S -> T U
T -> 0 T 1 | 1 T 0 | e
U -> 0 U 1 | 1 U 0 | e
\end{verbatim}}

Consistency: 
 Is this palindromic? (Yes, but not all are captured!)
{\small\begin{verbatim}
S -> 0 S 0 | 1 S 1 | e
\end{verbatim}}

Completeness:
Fill in the missing palindromes (for instance). What are they?

Do we need to add the {\tt S S} part to make this language complete
with respect to $L_{eq}$?
 {\small\begin{verbatim}
 S -> 0 S 1 S | 1 S 0 S | S S | e
 \end{verbatim}}  

\section{When is Something not a CFL?}

$L_{ww}=\{ w w \;\mid\;w\in\{0,1\}^*\}$ is not a CFL.  A proof has to wait.

\section{Closure under  Kleene Ops. (Groan, not under Compl.!)}

CFLs are closed under all Kleene operators (union, concatenation, star).

CFLs are not closed under complementation.
$L_{ww}$ is not a CFL (believe me). But its complement is (will write a CFG).

{\small\begin{verbatim}
S -> T U | U T | Oddlen
T -> P 0 P
U -> Q 1 Q
P -> 0 | 1
Q -> 0 | 1
Oddlen -> P | P P Oddlen
\end{verbatim}}

\section{Ambiguity and Inherent Ambiguity}
Have multiple parses. 
{\small\begin{verbatim}
S -> E + E | E * E | num
\end{verbatim}}
Inherent is when every CFG is ambiguous (for some string).
$\{0^i 1^j 2^k\;\mid\;i,j,k\ge 0\;\wedge\; (i=j\;\vee\;j=k)\}$
\end{document}

