\documentclass[11pt]{article}

\newcommand{\wshop}{
    2
}
\newcommand{\subtitle}{
    Automata and Regular Expressions
}

% 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
\theoremstyle{theorem} % In Italics
\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.                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In the following two workshop problems, you can use as many of the tools we have learned so far in the class as you want.
Just about everything applies!
But you could also do them totally without them, but where's the fun in that?
If you use your Antimirov derivatives, product and flip constructions, and Kleene's Algorithm applications wisely, you will have a great time.

\begin{problem}[Complement of \(a^*\)]
    Let \(A = \{a, b, c\}\).
    By the Finite Recognizability, Closure under Complement, and Kleene Theorems, the complement of the language \(\mathcal L(a^*)\), 
    \[
        L = A^* \setminus \mathcal L(a^*)
    \]
    is also regular. 
    Find a regular expression \(r\) such that \(\mathcal L(r) = L\).
    (Note that this is a proof of the equation \(r + a^* =_{\mathcal L} (a + b)^*\)!)
\end{problem}

\pagebreak

\begin{problem}[Complement of \(a^* + b^*\)]
    Let \(A = \{a, b, c\}\).
    By the Finite Recognizability, Closure under Complement, and Kleene Theorems, the complement of the language \(\mathcal L(a^* + b^*)\), 
    \[
        L = A^* \setminus \mathcal L(a^* + b^*)
    \]
    is also regular. 
    Find a regular expression \(r\) such that \(\mathcal L(r) = L\).
    (Note that this is a proof of the equation \(r + a^* + b^* =_{\mathcal L} (a + b)^*\)!)
\end{problem}

\pagebreak

\begin{problem}[Multiple of 3]
    Let \(A = \{1, 2\}\) and recall the language 
    \[
    L_1 = \{w \in A^* \mid \mathrm{sum}(w) \text{ is a multiple of \(3\)}\}
    \]
    Find a regular expression \(r\) such that \(\mathcal L(r) = L_1\).
\end{problem}

\pagebreak

\begin{problem}[Intersecting Monsters (Challenging!!)]
    Now let \(A = \{1, 2\}\). 
    Consider the languages below:
    \[
        L_1 = \{w \in A^* \mid \mathrm{sum}(w) \text{ is a multiple of \(3\)}\}
        \qquad
        L_2 = \{w \in A^* \mid w \text{ contains } 122\}
    \]
    We have already seen that these are finitely recognizable languages, which by Kleene's theorem tells us they are regular.
    From the Finite Recognizability, Closure under Intersections, and Kleene Theorems, the intersection of these languages is also regular.
    Find a regular expression \(r\) such that 
    \(
        \mathcal L(r) = L_1 \cap L_2
    \).
\end{problem}


\end{document}