2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.