Memorylessness Lemma

A key property of finite state automata is that they are memoryless. This is formalised by the memorylessness lemma.

Definition §

Memorylessness Lemma ^definition

Let $x,y,z$ be formulae. Then, for any FSA $A$:

$$q(x)=q(y)⟹q(x\circ z)=q(y\circ z)$$

That is, $A$ either accepts both $xz$ and $yz$ or it rejects both. It cannot accept one and reject the other.

• $\circ$ is the concatenation operation
• $q(x)$ is the state arrived by $A$ from $q_0$ after applying the extended transition function

The way to interpret the memorylessness lemma is that, in a FSA, once we get to some state, it does not matter how we got there. We could have taken a 1-state computation path, or a 1999-state computation path. To the FSA, all that matters is the remaining path we take.

Derivation §

Prefix-Suffix Decomposition §

Given a word, $w$, we can split it into a prefix and suffix. $w=p\circ s$, where $p$ and $s$ are sub-strings of $w$.

The prefix or suffix can be the empty word $ϵ$

For example, the set of all prefix-suffix decompositions for the word ‘dog’ are given below:

$$\text{dog}=\{ϵ\circ \text{dog},\text{d ∘ og},\text{do ∘ g},\text{dog}\circ ϵ\}$$

That is, we can partition a string using a line, making the left side the prefix and the right side the suffix. %%🖋 Edit in Excalidraw, and the dark exported image%%

In the context of feeding this string to an FSA, $A$, we can use our newly-defined extended transition function ${\delta }^{\ast }$ to concisely state that:

$$q_0\stackrel{p}{\to }q(p)\stackrel{s}{\to }q(ps)=q(w)$$

For an example string Babel, decomposed into $p=\text{Bab}$ and $s=\text{el}$ we have:

$$q(\text{Babel})=q_0\stackrel{\text{Bab}}{\to }q(\text{Bab})\stackrel{\text{el}}{\to }q(\text{Babel})$$

In the context of state diagrams, this takes the computation path starting from $q_0$ and ending at $q(\text{Babel})$, and splits that path into two sub-paths, corresponding to the prefix and suffix.

Final Lemma §

Finally, we can combine all these tools to form the memorylessness lemma:

For some FSA, $A$ having extended transition function ${\delta }^{\ast }$. For every prefix string, $x$ and $y$, such that $q(x)=q(y)$ (that is, ${\delta }^{\ast }(q_0,x)={\delta }^{\ast }(q_0,y)$) then for every suffix string $z$, we have:

$$q(xz)=q(yz)$$

And $A$ either accepts both strings or rejects both strings.

Thus, we get: