\documentclass{article}

\usepackage[utf8]{inputenc}

\usepackage[english]{babel}

\usepackage{listings}

 \usepackage{amsthm}

 \usepackage{hyperref}

 \usepackage[margin=0.5in]{geometry}

\usepackage{pmboxdraw}

\theoremstyle{theorem}

\newtheorem{theorem}{Theorem}

\theoremstyle{lemma}

\newtheorem{lemma}{Lemma}

\newcommand{\lemmaautorefname}{Lemma}

\theoremstyle{definition}

 \newtheorem{definition}{Definition}

\begin{document}

This is a sketch proof for the correctness of the algorithm ders\_simp.

\section{Function Definitions}

\begin{definition}{Bits}

\begin{verbatim}

abstract class Bit

case object Z extends Bit

case object S extends Bit

case class C(c: Char) extends Bit

type Bits = List[Bit]

\end{verbatim}

\end{definition}

\begin{definition}{Annotated Regular Expressions}

\begin{verbatim}

abstract class ARexp 

case object AZERO extends ARexp

case class AONE(bs: Bits) extends ARexp

case class ACHAR(bs: Bits, f: Char) extends ARexp

case class AALTS(bs: Bits, rs: List[ARexp]) extends ARexp 

case class ASEQ(bs: Bits, r1: ARexp, r2: ARexp) extends ARexp 

case class ASTAR(bs: Bits, r: ARexp) extends ARexp 

\end{verbatim}

\end{definition}

\begin{definition}{bnullable}

\begin{verbatim}

  def bnullable (r: ARexp) : Boolean = r match {

    case AZERO => false

    case AONE(_) => true

    case ACHAR(_,_) => false

    case AALTS(_, rs) => rs.exists(bnullable)

    case ASEQ(_, r1, r2) => bnullable(r1) && bnullable(r2)

    case ASTAR(_, _) => true

  }

\end{verbatim}

\end{definition}

\begin{definition}{ders\_simp}

\begin{verbatim}

def ders_simp(r: ARexp, s: List[Char]): ARexp = {

 s match {

   case Nil => r 

   case c::cs => ders_simp(bsimp(bder(c, r)), cs)

 }

}\end{verbatim}

\end{definition}

\begin{definition}{bder}

\begin{verbatim}

def bder(c: Char, r: ARexp) : ARexp = r match {

 case AZERO => AZERO

 case AONE(_) => AZERO

 case ACHAR(bs, f) => if (c == f) AONE(bs:::List(C(c))) else AZERO

 case AALTS(bs, rs) => AALTS(bs, rs.map(bder(c, _)))

 case ASEQ(bs, r1, r2) => {

  if (bnullable(r1)) AALT(bs, ASEQ(Nil, bder(c, r1), r2), fuse(mkepsBC(r1), bder(c, r2)))

  else ASEQ(bs, bder(c, r1), r2)

  }

 case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder(c, r)), ASTAR(Nil, r))

}

\end{verbatim}

\end{definition}

\begin{definition}{bsimp}

\begin{verbatim}

  def bsimp(r: ARexp): ARexp = r match {

    case ASEQ(bs1, r1, r2) => (bsimp(r1), bsimp(r2)) match {

        case (AZERO, _) => AZERO

        case (_, AZERO) => AZERO

        case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s)

        case (r1s, r2s) => ASEQ(bs1, r1s, r2s)

    }

    case AALTS(bs1, rs) => {

      val rs_simp = rs.map(bsimp)

      val flat_res = flats(rs_simp)

      val dist_res = distinctBy(flat_res, erase)

      dist_res match {

        case Nil => AZERO

        case s :: Nil => fuse(bs1, s)

        case rs => AALTS(bs1, rs)  

      }

    }

    //case ASTAR(bs, r) => ASTAR(bs, bsimp(r))

    case r => r

  }

\end{verbatim}

\end{definition}

\begin{definition}{sub-parts of bsimp}

\begin{itemize}

\item{flats}\\

flattens the list.

\item{dB}\\

means distinctBy

\item{Co}\\

The last matching clause of the function bsimp, with a slight modification to suit later reasoning.

\begin{verbatim}

def Co(bs1, rs): ARexp = {

      rs match {

        case Nil => AZERO

        case s :: Nil => fuse(bs1, s)

        case rs => AALTS(bs1, rs)  

      }

\end{verbatim}

\end{itemize}

\end{definition}

\begin{definition}{fuse}

\begin{verbatim}

  def fuse(bs: Bits, r: ARexp) : ARexp = r match {

    case AZERO => AZERO

    case AONE(cs) => AONE(bs ++ cs)

    case ACHAR(cs, f) => ACHAR(bs ++ cs, f)

    case AALTS(cs, rs) => AALTS(bs ++ cs, rs)

    case ASEQ(cs, r1, r2) => ASEQ(bs ++ cs, r1, r2)

    case ASTAR(cs, r) => ASTAR(bs ++ cs, r)

  }

\end{verbatim}

\end{definition}

\begin{definition}{mkepsBC}

\begin{verbatim}

  def mkepsBC(r: ARexp) : Bits = r match {

    case AONE(bs) => bs

    case AALTS(bs, rs) => {

      val n = rs.indexWhere(bnullable)

      bs ++ mkepsBC(rs(n))

    }

    case ASEQ(bs, r1, r2) => bs ++ mkepsBC(r1) ++ mkepsBC(r2)

    case ASTAR(bs, r) => bs ++ List(Z)

  }

\end{verbatim}

\end{definition}

\begin{definition}{mkepsBC equicalence}

\\

Given 2 nullable annotated regular expressions r1, r2, if mkepsBC(r1) == mkepsBC(r2)

then r1 and r2 are mkepsBC equivalent, denoted as r1 $\sim_{m\epsilon}$ r2

\end{definition}

\begin{definition}{shorthand notation for ders}

\\For the sake of reducing verbosity, we sometimes use the shorthand notation

$d_{c}(r)$ for the function application bder(c, r) and $s(r)$(s here stands for simplification) for the function application bsimp(r) .

\\We omit the subscript when it is clear from context what that character is and write $d(r)$ instead of $d_{c}(r)$. 

\\And we omit the parentheses when no confusion can be caused. For example ders\_simp(c, r) can be written as $s(d_{c}(r))$ or even $s d r$ as we know the derivative operation is w.r.t the character c. Here the s and d are more like operators that take an annotated regular expression as an input and return an annotated regular expression as an output

\end{definition}

\begin{definition}{distinctBy operation expressed in a different way--how it transforms the list}\\

Given two lists rs1 and rs2, we define the operation $--$:\\

$rs1 -- rs2 := [r \in rs1 |  r \notin rs2]$

Note that the order each term appears in $rs_1 -- rs_2$ is preserved as in the original list.

\end{definition}

\section{Main Result}

\begin{lemma}{simplification function does not simplify an already simplified regex}\label{lma1}\\

bsimp(r) == bsimp(bsimp(r)) holds for any annotated regular expression r.

\end{lemma}

\begin{lemma}{simp and mkeps}\label{lma2}\\

When r is nullable, we have that

mkeps(bsimp(r)) == mkeps(r)

\end{lemma}

%\begin{theorem}See~\cref{lma1}.\end{theorem}

%\begin{lemma}\label{lma1}\lipsum[2]\end{lemma}

\begin{lemma}{mkeps equivalence  w.r.t some syntactically different regular expressions(1 ALTS)}\label{lma3}\\

When one of the 2 regular expressions $s(r_1)$ and $s(r_2)$ is of the form ALTS(bs1, rs1), we have that $ds(ALTS(bs, r1, r2)) \sim_{m\epsilon} d(ALTS(bs, sr_1, sr_2))$

\end{lemma}

\begin{proof}

By opening up one of the alts and show no additional changes are made.\\

Details: $ds(ALTS(bs, r1, r2)) = d Co( bs, dB(flats(sr1, sr2)) )$

\end{proof}

\begin{lemma}{mkepsBC invariant manipulation of bits and notation}\label{lma7}\\

ALTS(bs, ALTS(bs1, rs1), ALTS(bs2, rs2)) $\sim_{m\epsilon}$ ALTS(bs, rs1.map(fuse(bs1, \_)) ++ rs2.map(fuse(bs2, \_)) ). \\

We also use $bs2>>rs2 $ as a shorthand notation for rs2.map(fuse(bs2,\_)).

\end{lemma}

\begin{lemma}{mkepsBC equivalence w.r.t syntactically different regular expressions(2 ALTS)}\label{lma4}\\

$sr_1 = ALTS(bs1, rs1)$ and $sr_2 = ALTS(bs2, rs2)$ we have  $  d(sr_1 +sr_2 ) \sim_{m\epsilon} d(ALTS(bs, bs1>>rs1 ++ bs2>>rs2))$ 

\end{lemma}

\begin{proof}

We are just fusing bits inside here, there is no other structural change.

\end{proof}

\begin{lemma}{What does dB do to two already simplified ALTS}\label{lma5}\\

$d Co(ALTS(bs, dB(bs1>>rs1 ++ bs2>>rs2))) = d Co(ALTS(bs, bs1>>rs1 ++ ((bs2>>rs2)--rs1)        )) $ 

\end{lemma}

\begin{proof}

We prove that $ dB(bs1>>rs1 ++ bs2>>rs2) = bs1>>rs1 ++ ((bs2>>rs2)--rs1)$.

\end{proof}

\begin{lemma}{after opening two previously simplified alts up into terms, length must exceed 2}\label{lma6}\\

If sr1, sr2 are of the form ALTS(bs1, rs1), ALTS(bs2, rs2) respectively, then we have that 

$Co(bs, (bs1>>rs1) ++ (bs2>>rs2)--rs1) = ALTS(bs, bs1>>rs1 ++ (bs2>>rs2)--rs1)$

\end{lemma}

\begin{proof}

 $Co(bs, rs) \sim_{m\epsilon} ALTS(bs, rs)$ if $rs$ is a list of length greater than or equal to 2.

 As suggested by the title of this lemma, ALTS(bs1, rs1) is a result of simplification, which means that rs1 must be composed of at least 2 distinct regular terms. This alone says that $bs1>>rs1 ++ (bs2>>rs2)--rs1$ is a list of length greater than or equal to 2, as the second operand of the concatenation operator $(bs2>>rs2) -- rs1$ can only contribute a non-negative value to the overall length of the list 

 $bs1>>rs1 ++ (bs2>>rs2)--rs1$.

\end{proof}

\begin{lemma}{mkepsBC equivalence w.r.t syntactically different regular expressions(2 ALTS+ some deletion after derivatives)}\label{lma8}\\

$d ALTS(bs, bs1>>rs1 ++ bs2>>rs2) \sim_{m\epsilon} d ALTS(bs, bs1>>rs1 ++ ((bs2>>rs2)--rs1)        ) $ 

\end{lemma}

\begin{proof}

Let's call $bs1>>rs1$ $rs1'$ and  $bs2>>rs2$ $rs2'$. Then we need to prove $d ALTS(bs, rs1' ++rs2') \sim_{m\epsilon} d ALTS(bs, rs1'++(rs2' -- rs1') )   $.\\

We might as well omit the prime in each rs for simplicty of notation and prove $d ALTS(bs, rs1++rs2) \sim_{m\epsilon} d ALTS(bs, rs1++(rs2 -- rs1) )   $.\\

We know that the result of derivative is nullable, so there must exist an r in rs1++rs2 s.t. r is nullable.\\

If $r \in rs1$, then equivalence holds. If $r \in rs2 \wedge  r \notin rs1$, equivalence holds as well. This completes the proof.

\end{proof}

\begin{lemma}{nullability relation between a regex and its simplified version}\label{lma9}\\

$r\ nullable \iff sr\ nullable $ 

\end{lemma}

\begin{lemma}{concatenation + simp invariance of mkepsBC}\label{lma10}\\

$mkepsBC r1 \cdot sr2 = mkepsBC r1 \cdot r2$ if both r1 and r2 are nullable.

\end{lemma}

\begin{theorem}{Correctness Result}

\begin{itemize}

\item{}

When s is a string in the language L(ar), \\

ders\_simp(ar, s)  $\sim_{m\epsilon}$ ders(ar, s), \\

\item{}

when s is not a string of the language L(ar)

ders\_simp(ar, s) is not nullable

\end{itemize}

\end{theorem}

\begin{proof}{Split into 2 parts.}

\begin{itemize}

\item

When we have an annotated regular expression ar and a string s that matches ar, by the correctness of the algorithm ders, we have that ders(ar, s) is nullable, and that mkepsBC will extract the desired bits for decoding the correct value v for the matching, and v is a POSIX value. Now we prove that mkepsBC(ders\_simp(ar, s)) yields the same bitsequence.

\\

We first open up the ders\_simp function into nested alternating sequences of ders and simp.

Assume that s = $c_1...c_n$($n \geq 1$ ) where each of the $c_i$ are characters. 

Then $ders\_simp(ar, s)$ = $s(d_{c_n}(...s(d_{c_1}(r))...))$ = $sdsd......sdr$. If we can prove that

$sdr \sim_{m\epsilon} dsr$ holds for any regular expression and any character, then we are done. This is because then we can push ders operation inside and move simp operation outside and have that $sdsd...sdr \sim_{m\epsilon} ssddsdsd...sdr \sim_{m\epsilon} ... \sim_{m\epsilon} s....sd....dr$.

 Using \autoref{lma1} we have that $s...sd....dr = sd...dr$. 

By \autoref{lma2}, we have $RHS \sim_{m\epsilon} d...dr$.\\

Notice that we don't actually need \autoref{lma1} here. That is because by \autoref{lma2}, we can have that $s...sd....dr \sim_{m\epsilon} sd...dr$. The equality above can be replaced by mkepsBC

 equivalence without affecting the validity of the whole proof since all we want is mkepsBC equivalence, not equality.

Now we proceed to prove that $sdr \sim_{m\epsilon} dsr$. This can be reduced to proving $dr \sim_{m\epsilon} dsr$ as we know that $dr \sim_{m\epsilon} sdr$ by \autoref{lma2}.\\

we use an induction proof. Base cases are omitted. Here are the 3 inductive cases.

\begin{itemize}

\item{$r_1+r_2$}\\

The most difficult case is when $sr1$ and $sr2$ are both ALTS, so that they will be opened up in the flats function and some terms in sr2 might be deleted. Or otherwise we can use the argument that $d(r_1+r_2) = dr_1 + dr_2  \sim_{m\epsilon} dsr_1 + dsr_2 \sim_{m\epsilon} ds(r_1+r_2)$,

 the last equivalence being established by \autoref{lma3}.

When $s(r_1), s(r_2)$ are both ALTS, we have to be more careful for the last equivalence step, namelly, $dsr_1 + dsr_2 \sim_{m\epsilon} ds(r_1+r_2)$. \\

We have that $LHS = dsr_1 + dsr_2 = d(sr_1 +sr_2)$. Since $sr_1 = ALTS(bs1, rs1)$ and $sr_2 = ALTS(bs2, rs2)$ we have  $  d(sr_1 +sr_2 ) \sim_{m\epsilon} d(ALTS(bs, bs1>>rs1 ++ bs2>>rs2))$ by \autoref{lma4}.

On the other hand, $RHS = ds(ALTS(bs, r1, r2)) = d Co(bs, dB(flats(s(r1), s(r2)) ) ) = d Co(bs, dB(bs1>>rs1 ++ bs2>>rs2))$ by definition of bsimp and flats.\\  

$d Co(bs, dB(bs1>>rs1 ++ bs2>>rs2)) = d Co(bs, (bs1>>rs1 ++ ((bs2>>rs2)--rs1))) $ by \autoref{lma5}.\\ $d Co(bs, (bs1>>rs1 ++ ((bs2>>rs2)--rs1)        )) = d(ALTS(bs, bs1>>rs1 ++ (bs2>>rs2)--rs1))$ by \autoref{lma6}. \\

 Using \autoref{lma8}, we have  $d(ALTS(bs, bs1>>rs1 ++ (bs2>>rs2)--rs1)) \sim_{m\epsilon} d(ALTS(bs, bs1>>rs1 ++ bs2>>rs2)) \sim_{m\epsilon}  RHS$.\\

 %only the last part we don't have an equality here. We use mkeps equivalence instead because these two regexes are indeed different syntactically. However, they have even more in common than just mkeps equal. We might later augment this proof so that this equivalence relation is changed to something like regular expression equivalence.

 This completes the proof.

\item{$r*$}\\

$s(r*) = r*$. Our goal is trivially achieved.

\item{$r1 \cdot r2$}\\

When r1 is nullable, $ds r1r2 = dsr1 \cdot sr2 + dsr2  \sim_{m\epsilon}  dr1 \cdot sr2 + dr2 = dr1 \cdot r2 + dr2 $. The last step uses \autoref{lma10}. 

When r1 is not nullable, $ds r1r2 = dsr1 \cdot sr2  \sim_{m\epsilon}  dr1 \cdot sr2  \sim_{m\epsilon}  dr1 \cdot r2 $

\end{itemize}

\item

Proof of second part of the theorem: use a similar structure of argument as in the first part.

\item

This proof has a major flaw: it assumes all dr is nullable along the path of deriving r by s. But it could be the case that $s\in L(r)$ but $ \exists s' \in Pref(s) \ s.t.\ ders(s', r)$ is not nullable (or equivalently, $s'\notin L(r)$). One remedy for this is to replace the mkepsBC equivalence relation into some other transitive relation that entails mkepsBC equivalence.

\end{itemize}

\end{proof}

\begin{theorem}{

This is a very strong claim that has yet to be more carefully examined and proved. However, experiments suggest a very good hope for this.}\\

Then we have \mbox{\boldmath$pushbits(ders\_simp(ar, s) ) == simp(ders(ar,s)) \ or\ ders\_simp(ar, s) == simp(ders(ar, s))$}.\\

Unfortunately this does not hold. A counterexample is\\

\begin{verbatim}

regex after ders simp

    └-SEQ

          └-ALT

regex after ders and then a single simp

       └-ALT

          |  └-a

             └-a List(S)

\end{verbatim}

\end{theorem}

\end{document}

%The second part might still need some more development.

%When s is not in the set L(ar), we have that s = s1@s2 s.t. s1 $\in$ L(ar), and any longer string that is a prefix of s does not belong to L(ar).\\

%By first part of proof, we have ders(ar, s1) $\sim_{m\epsilon}$ ders\_simp(ar, s1)

%.....somehow show that by correctness, der(c, ders\_simp(ar, s1)) must be not nullable. But this will need that L(ders(ar, s1)) == L(ders\_simp(ar, s1)). By part 1 of proof we only have that for any string s1c s.t. s1c $\in$ L(ar) (which is equivalent to s $\in$ L(ders(ar, s1))), s is also in L(ders\_simp(ar, s1)). That is an inclusion, not an equality. c not in L(ders(ar, s1)) does not imply c not in L(ders\_simp(ar, s1))

%So this path stuck here.