\documentclass[11pt]{article}

\newcommand{\wshop}{
    4
}
\newcommand{\subtitle}{
    Grammars
}

% Page Setup
\usepackage{geometry}
\geometry{
    a4paper,
    margin={2.5cm}
}

% Basic Packages
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{mathpartir}
\usepackage{enumitem}
\usepackage{mathabx}

% Font
\usepackage{charter}

% Bibliography and index
\usepackage[backend=biber, style=numeric]{biblatex}
\addbibresource{refs.bib}
\usepackage{makeidx}
\makeindex

% Colors and Graphics
\usepackage[dvipsnames, x11names]{xcolor}
\usepackage{tikz}
\usetikzlibrary{
    cd,
    fit,
    calc,
    positioning,
    arrows,
    automata,
    shapes
}
\tikzset{
    baseline = (current bounding box.center),
    every state/.append style = {
        rectangle,
        rounded corners=5pt,
		inner sep = 3pt,
		minimum size = 18pt,
		initial text = {},
        fill=Azure1
	},
	every edge/.append style = {
		->,
		>=stealth,
		bend angle=10,
		thick
	}
}
\usepackage{musicography}
\usepackage{graphicx}
\usepackage{svg}
\graphicspath{../imgs/}

% Hyperlinks
\usepackage{hyperref}
\hypersetup{
    colorlinks,
    linkcolor   = black,
    filecolor   = RubineRed,
    urlcolor    = RubineRed,
    citecolor   = RubineRed,
    pdftitle    = {Notes on Behavioural PDEs}
}
\usepackage[capitalize]{cleveref}

% Environments
\newtheorem{theorem}                    {{\color{Purple}Theorem}}[section]
\newtheorem{lemma}          [theorem]   {{\color{Magenta}Lemma}}
\newtheorem{proposition}    [theorem]   {Proposition}
\newtheorem{corollary}      [theorem]   {Corollary}
\newtheorem{question}                   {{\color{red}Question}}

\theoremstyle{definition} % Not in italics
\newtheorem{definition}     [theorem]   {{\color{NavyBlue}Definition}}
\newtheorem{example}        [theorem]   {{\color{ForestGreen}Example}}
\newtheorem{problem}                    {{\color{BurntOrange}Problem}}

\theoremstyle{remark} % Subdued label
\newtheorem{remark}[theorem]        {{\color{Gray}Remark}}

% (1), (2), ...
\renewcommand\labelenumi{(\theenumi)}

% Go nuts with line breaks 
\allowdisplaybreaks

%%%%%%%%%%
% MACROS %
%%%%%%%%%%

\newcommand{\op}{\mathrm{op}}               % Opposite
\newcommand{\inv}{{-1}}                     % Inverse
\newcommand{\id}{\mathsf{id}}               % Identity f(x) = x
\newcommand{\Det}{\mathrm{Det}}             % determinize
\newcommand{\Lang}{\mathcal{L}}             % Language

\newcommand{\incl}{\mathsf{incl}}           % Inclusion
\newcommand{\proj}{\mathsf{proj}}           % Projection

% Numbers and Standard notation
\newcommand{\NN}{\mathbb{N}}                % 0, 1, 2, 3, 4, ...
\newcommand{\ZZ}{\mathbb{Z}}                % ..., -2, -1, 0, 1, 2, ...
\newcommand{\QQ}{\mathbb{Q}}                % n/m for n and m in \NN and m > 0
\newcommand{\RR}{\mathbb{R}}                % real numbers
\newcommand{\pRR}{\mathbb{R}_{+}}           % positive real numbers

\newcommand{\dom}{\mathrm{dom}}             % Domain
\newcommand{\cod}{\mathrm{cod}}             % Codomain

\newcommand{\Grph}{\operatorname{Grph}}     % Graph of a function

% Transitions
\newcommand{\tr}[1]{
    \mathrel{
        \raisebox{-1pt}{
            \(\xrightarrow{#1}\)
        }
    }
}
\newcommand{\bisim}{\mathrel{\raisebox{1pt}{\(\underline{\leftrightarrow}\)}}}

% Text
\newcommand{\code}[1]{\texttt{#1}}
\newcommand{\codeblock}[1]{
    \begin{center}
        \parbox{0.8\textwidth}{
            \ttfamily
            #1
        }
    \end{center}
}

% Boolean statements
\newcommand{\OR}{~\mathrm{or}~}
\newcommand{\AND}{~\mathrm{and}~}
\newcommand{\NOT}{\mathrm{not}~}
\newcommand{\IMPLIES}{~\mathrm{implies}~}
\newcommand{\FORALL}{\mathrm{for\ all}~}
\newcommand{\EXISTS}{\mathrm{there\ exists}~}
\newcommand{\SUCHTHAT}{~\mathrm{such\ that}~}



% Title
\title{CSCI 341 Workshop \wshop}
\author{\subtitle}
% \date{
    % \today
% }

\pagestyle{empty}

\begin{document}


\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% START OF WORK SHOP.                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Some Pumping and Grammar Warmup}

\begin{problem}[Balanced Parentheses]
    A string of parentheses, i.e., \(\mathtt{)}\) and \(\mathtt{(}\), is called \emph{balanced} if every left-parenthese \(\mathtt{(}\) is eventually followed by a unique \emph{matching} right-parenthese \(\mathtt{)}\). 
    For example, the following strings of parentheses are not balanced:
    \begin{align*}
        \mathtt{(},
        \qquad \mathtt{))()},
        \qquad \mathtt{((())()}
        \tag{*}
    \end{align*}
    but the following strings of parentheses are:
    \begin{align*}
        \varepsilon,
        \qquad \mathtt{()},
        \qquad \mathtt{(())()},
        \qquad \mathtt{((())())()}
        \tag{**}
    \end{align*}
    Let \(A = \{\mathtt{(}, \mathtt{)}\}\) and 
    \[
        L = \{w \in A^* \mid \text{\(w\) is balanced}\}
    \]   
    \begin{enumerate}
        \item Show that \(L\) is not regular.
        \item Design a context-free grammar \(\mathcal G\) with a variable \(x\) that derives \(L\).
        \item In your grammar, derive or draw parse trees for the words in (**)
        \item Explain why the words in (*) are not derivable.
    \end{enumerate}
\end{problem}

\pagebreak

\begin{problem}[Palindromes]
    Let \(A = \{a, c, e, r\}\) and recall that for any word \(w = a_1 a_2 \cdots a_n\), we define \(w^{\op} = a_n a_{n-1} \cdots a_2 a_1\).
    Consider the language below:
    \[
        L_{pal} = \{w \in A^* \mid w = w^{\op}\}
    \]
    The words in \(L_{pal}\) are precisely the \emph{palindromes}.
    \begin{enumerate}
        \item Show that \(L_{pal}\) is not regular.
        \item Design a grammar with a variable that derives \(L_{pal}\).
        \item Draw a parse tree for \(racecar\).
    \end{enumerate}
\end{problem}

\pagebreak 

\section{Some Normal Form Problems}

\begin{definition}[Unit Production]
    Let \(\mathcal G = (X, A, R)\) be a grammar.
    A \emph{unit production} is a rewrite rule of the form \(x \to y\), where both \(x,y \in X\).
\end{definition}

\begin{problem}[Killing \(\varepsilon\)s with a dagger?]
    Consider the grammar (taken from \emph{Sipser}'s book) \(\mathcal G\) below.
    \[\begin{aligned}
        x &\to a \mid b \mid xa \mid xb \mid x0 \mid x1 \\
        y &\to x \mid (u) \\
        z &\to y \mid z * y \\
        u &\to z \mid u + z 
    \end{aligned}\]
    Observe that the rewrite rules \(y \to x\), \(z \to y\), and \(u \to z\) are all unit productions.
    \begin{enumerate}
        \item Find a derivation and parse tree that yields \(a*b0+b*a\).
        \item Find a grammar \(\mathcal G'\) with a variable \(x'\) such that \(\mathcal G'\) \textbf{has no unit productions at all} and yet \(\mathcal L(\mathcal G', x') = \mathcal L(\mathcal G, x)\). In other words, \emph{eliminate the unit productions in \(\mathcal G\).}
    \end{enumerate}
\end{problem}

\pagebreak

\begin{definition}[Usefulness]
    Let \(\mathcal G\) be a grammar with variables \(x,y\).
    We say that \(y\) is \emph{reachable from \(x\)} if there is a sequence of reqrites \(x \Rightarrow \mu_1 \Rightarrow \cdots \Rightarrow \mu_n\) such that \(y\) is a variable that appears in \(\mu_n\).
    We say that \(y\) is \emph{useful for \(x\)} if \(y\) is reachable from \(x\) and \(\mathcal L(\mathcal G, y)\) is not empty (there is at least one derivation possible starting from \(y\)).
\end{definition}

\begin{problem}[Cutting the fat]
    Consider the grammar \(\mathcal G\) below.
    \[\begin{aligned}
        x &\to yz \mid ux \\
        y &\to 0  \\
        z &\to zu \mid xy  \\
        u &\to 0z \mid 1  \\
    \end{aligned}\]
    We are going to find a grammar without useless symbols with a state that is equivalent to \(x\).
    \begin{enumerate}
        \item Which variables are reachable from \(x\)?
        \item Does every variable derive a nonempty language?
        \item Which variables are useless for \(x\)?
        \item Find a grammar \(\mathcal G'\) with a variable \(x'\) such that 
        \begin{enumerate}
            \item \(\mathcal G'\) has no useless symbols for \(x'\),
            \item \(\mathcal G'\) has no unit productions, and 
            \item \(\mathcal L(\mathcal G', x') = \mathcal L(\mathcal G, x)\).
        \end{enumerate}
    \end{enumerate}
\end{problem}

\pagebreak 

\begin{definition}[Chomsky Normal Form]
    Let \(\mathcal G = (X, A, R)\) be a grammar with a variable \(x \in X\). 
    We say that \(x\) is \emph{in Chomsky Normal Form} if 
    \begin{enumerate}
        \item Every variable in \(\mathcal G\) is useful for \(x\).
        \item If \(y \in X\) has a rewrite rule \(y \to \varepsilon\), then \(y = x\) (although this rewrite rule is not required to exist at all).
        \item All other rewrite rules (i.e., not \(x \to \varepsilon\)) in \(\mathcal G\) are of one of the following two forms:
        \begin{enumerate}
            \item \(y \to zu\) where \(y,z,u \in X\)
            \item \(y \to a\) where \(y \in X\) and \(a \in A\)
        \end{enumerate}
    \end{enumerate}
\end{definition}

\begin{problem}[Manufacturing Chomsky Normal Forms]
    Consider the grammar \(\mathcal G\) below: 
    \[\begin{aligned}
        x &\to yxz \mid \varepsilon \\
        y &\to 0yx \mid 1  \\
        z &\to x1x \mid y \mid 11
    \end{aligned}\]
    Find a grammar \(\mathcal G'\) with a variable \(x'\) such that \(x'\) is in Chomsky Normal Form and \(\mathcal L(\mathcal G', x') = \mathcal L(\mathcal G, x)\).
\end{problem}

\pagebreak

\begin{definition}[Greibach Normal Form]
    Let \(\mathcal G = (X, A, R)\) be a grammar with a variable \(x\).
    We say that \(x\) is in \emph{Greibach normal form} if no more than the variable \(x\) has a rewrite rule \(x \to \varepsilon\), and if every other rewrite rule is of the form 
    \[
        y \to azu
    \]
    for some \(a \in A\) and some \(y,z,u \in X\).
\end{definition}

It is not an easy theorem, but it is known that every context-free grammar can be turned into one in Greibach Normal Form!
This has significant consequences, which we might talk about next week.

\begin{problem}[Challenging!!]
    Consider the grammar \(\mathcal G\) below: 
    \[\begin{aligned}
        x &\to yxz \mid \varepsilon \\
        y &\to 0yx \mid 1  \\
        z &\to x1x \mid y \mid 11
    \end{aligned}\]
    Find a grammar \(\mathcal G'\) with a variable \(x'\) such that \(x'\) is in Greibach Normal Form and \(\mathcal L(\mathcal G', x') = \mathcal L(\mathcal G, x)\).
\end{problem}


\end{document}