Notes - Models of Computation MT23, Kozen's axioms


Flashcards

What are Kozen’s axioms (in general)?


A set of axioms for determining the equivalence of two regular expressions.

Under Kozen’s axioms, what is

\[\epsilon E\]

equivalent to?


\[E\]

Under Kozen’s axioms, what are $\varnothing E$ or $E \varnothing$ equivalent to?


\[\varnothing\]

Under Kozen’s axioms, what are $\epsilon + E E^\star$ and $\epsilon + E^\star E$ equivalent to?


\[E^\star\]

What are the two rules for sublanguages in Kozen’s axioms?


  1. $L(F + EG) \subseteq L(G) \implies L(E^\star F) \subseteq L(G)$
  2. $L(F + GE) \subseteq L(G) \implies L(FE^\star) \subseteq L(G)$

Quickly prove one of the rules for sublanguages in Kozen’s axioms, that

\[L(F + GE) \subseteq L(G) \implies L(FE^\star) \subseteq L(G)\]

Fix some $w \in L(FE^\star)$. $w$ must be of the form $f e _ 1 \cdots e _ n$ where $n \ge 0$ and $f \in L(F)$ and each $e _ i \in L(E)$. We prove that $w \in L(G)$ by induction on $n$.

  • Base case $n = 0$: Then $w = f$, so $w \in L(F) \subseteq L(F + GE) \subseteq L(G)$.
  • Inductive case $n > 0$: Suppose $w = fe _ 1 \cdots e _ {n+1}$. Then $f e _ 1 \cdots e _ n \in L(FE^\star)$ also, so by the inductive hypothesis, $f e _ 1 \cdots e _ n \in G$, so $f e _ 1 \cdots e _ {n} e _ {n+1} \in L(GE)$, and $L(GE) \subseteq L(F + GE) \subseteq L(G)$.

What is Kozen’s theorem?


All valid equivalence between regular expressions can be derived from Kozen’s axioms and rules, using the laws of equational logic.

Can you state Arden’s theorem?


Suppose:

  • $E$, $F$, $X$ are regular expressions
  • $L(E)$ does not contain the empty string $\epsilon$
  • $X \equiv F + X E$

Then:

  • $X \equiv FE^\star$

uniquely.

Quickly prove Arden’s theorem, i.e. that if:

  • $E$, $F$, $X$ are regular expressions
  • $L(E)$ does not contain the empty string $\epsilon$
  • $X \equiv F + X E$

Then:

  • $X \equiv FE^\star$

uniquely.


Checking $F E^\star$ is an equivalence:

\[\begin{aligned} F + (FE^\star) E &\equiv F + FE^+ \\\\ &\equiv F (\epsilon + E^+) \\\\ &\equiv FE^\star \end{aligned}\]

Now we want to show that for arbitrary $X$ where $\epsilon \ne L(X)$, if $X \equiv F + XE$, then $X = FE^\star$.

If $L(X) = \emptyset$, then $L(F) = \emptyset$, so $L(FE^\star) = \emptyset$ and we are done.

So we may assume that $L(X) \ne \emptyset$. Then we can prove $L(X) = L(FE^\star)$ by set inclusion in each direction. First note that repeated substitution gives:

\[\begin{align} X &\equiv F + XE \\\\ &\equiv F + (F + XE)E \equiv F + FE + X E^2 \\\\ &\equiv F + FE + E^2 (F + XE) \equiv F + FE + FE^2 + XE^3 \\\\ &\equiv \ldots \quad \text{etc.} \end{align}\]

Hence, in general,

\[L(X) = \left(\bigcup^k_{i = 0} L(FE^i)\right) \cup L(XE^{k+1})\]

This makes one inclusion clear: $L(FE^i) \subseteq L(X)$ for all $i \ge 0$, so $L(FE^\star) \subseteq L(X)$.

For the other direction, pick $s \in X$ and let $n$ be its length. Taking $k$ to be $n$ in the recurrence, we have that

\[s \in \bigcup^n_{i = 0} L(FE^i), \text{ or } s \in L(XE^{n+1})\]

but the second case is impossible as all strings in $L(XE^{n+1})$ have length greater than $n$. Hence $s \in \bigcup^n _ {i = 0} L(FE^i)$, so $s \in L(FE^\star)$.

Proofs




Related posts