# Show that every definite language is accepted by a finite automaton

A language $L$ is definite if there is some $k> 0$ such that for any string $w$, whether $w \in L$ depends on the last $k$ symbols of $w$. How can I prove that every definite language is accepted by a finite automaton?

This is true as a consequence of the Myhill Nerode theorem. For any fixed $k\gt 0$, the number of possible combinations of the last $k$ symbols of any string $w\in L$ is $|\Sigma|^k$, where $\Sigma$ is the alphabet.

Any two strings that have the last $k$ symbols identical will always be both accepted or both rejected by $L$, for any string appended to them, i.e., no string in $\Sigma^*$ will distinguish such strings. Thus, such strings lie in the same equivalence class of $L$.

Strings with differences in their last $k$ symbols will either lie in different equivalence classes or will cause the classes demarcated in the previous step to collapse together into a single class.

Thus, the equivalence classes of $L$ are determined by the last $k$ symbols of $L$.

As the possible combinations of the last $k$ symbols is finite, the number of equivalence classes is finite. Thus, by the Myhill Nerode theorem, the language $L$ is regular. Hence, there exists a DFA that accepts $L$.

Hint 1:

$L=L_1\sqcup L_2$ where $L_1=\{u \in L : |u|<k\}$ and $L_2=\{u \in L : |u|\ge k\}$.

-

What properties would you like to have on $L_1$ and $L_2$ to prove that $L$ is regular?

Hint 2:

What property does $L_1$ have that makes it regular?

-

How many elements are there in $L_1$?

Hint 3:

If $u\in L_2$, then $u$ can be written $u=vw$ with $|w| = k$.

-

And then $\Sigma^*w\subseteq L_2$.

-

Take $L_3=L_2\cap \Sigma^k$.

-

Express $L_2$ in terms of $L_3$.

-

$L_2=\Sigma^*L_3$

Hint 4:

What property does $L_3$ have that makes it regular?

-

How many elements are there in $L_3$?