Notes - Models of Computation MT23, Myhill-Nerode theorem
Flashcards
Let $x, y \in \Sigma^\star$ be strings and let $L \subseteq \Sigma^\star$. What does it mean for $x$ and $y$ to be $L$-indistinguishable, written $x \equiv _ L y$?
$\forall z \in \Sigma^\star$, we have
\[xz \in L \iff yz \in L\]Can you define the index of a language $L$?
The number of equivalence classes of $\equiv _ L$, i.e. sets of $L$-indistinguishable strings.
Can you state the Myhill-Nerode theorem?
A language $L$ is regular if and only if $\equiv _ L$ has finite index, and moreover, the index is the size of the smallest DFA recognising $L$.
How can you work out the minimum number of states required for a DFA recognising some language $L$?
It’s the index of $L$, i.e. the number of equivalence classes of $\equiv _ L$.
When proving the Myhill-Nerode theorem, i.e.
A language $L$ is regular if and only if $\equiv _ L$ has finite index, and moreover, the index is the size of the smallest DFA recognising $L$.
how do you break down the proof?
A language $L$ is regular if and only if $\equiv _ L$ has finite index, and moreover, the index is the size of the smallest DFA recognising $L$.
- If $L$ is recognised by a DFA with $k$ states, then $L$ has index at most $k$.
- If $L$ has a finite index $k$, then it is recognised by a DFA with $k$ states.
Suppose $L$ is recognised by a DFA with $k$ states. What can you say about the index of $L$?
It is at most $k$.
What useful notation $\hat \delta$ is used when proving the Myhill-Nerode theorem?
where
\[q \to^{\star x} q'\]Quickly prove that if a language $L \subseteq \Sigma^\star$ is recognised by a DFA with $k$ states, then $L$ has index at most $k$.
Using the notation $\hat\delta(q, x) = q’$ for the state the DFA ends up in after “running” on input $x$, it is clear that
\[\hat\delta(q_0, x_i) = \hat\delta(q_0, x_j) \implies x_i \equiv_L x_j\]Then consider any collection of $k+1$ strings, $x _ 1, \cdots, x _ {k+1}$. By the pigeonhole principle, there must be $1 \le i < j \le k+1$ such that $\hat\delta(q _ 0, x _ i) = \hat\delta(q _ 0, x _ j) \implies x _ i \equiv _ L x _ j$, and so it follows that $\equiv _ L$ has at most $k$ equivalence classes.
Quickly prove that if a language $L \subseteq \Sigma^\star$ has finite index $k$, then it is recognised by a DFA with $k$ states.
Let $M = (Q, \Sigma, \delta, q _ 0, F)$ where
- $Q = \{[x] \mid x \in \Sigma^\star\}$
- $q _ 0 = [\epsilon]$
- $\delta([x], a) = [xa]$
- $F = \{[w] \mid w \in L\}$
Where $[ \cdot ]$ represents equivalence classes. $Q$ has a finite number of states, and $\delta$ is well defined since it doesn’t depend on the choice of representative (since $x \equiv _ L y \implies xa \equiv _ L ya$). This DFA recognises $L$, since
- $w \in L(M)$ iff
- $[\epsilon] \to^{\star, w} [w] \in F$ iff
- $w \in L$