Deterministic Finite Automata with finite strings

Question

How could I prove that every language with a finite number of strings is the language of some DFA?

Answer 1

Let $L$ be the the finite set of strings. Then define a NFA for $L$ by making one independent branch from the start state for every word in $L$, that has an accepting state at the end. So this NFA accepts $L$ and a formal language is accepted by a NFA iff there is a DFA that accepts $L$.

Answer 2

Let $n$ be the maximum length of any word of the finite language $L$ over the alphabet $\Sigma$. Let $W=\{w\in\Sigma^*:|w|\le n\}$; $W$ is a finite set. For each $w\in W$ let $q_w$ be a distinct state, and let $Q_0=\{q_w:w\in W\}$. Let $q_\epsilon$ be the initial state, where $\epsilon$ is the empty word. The set of acceptor states is $A=\{q_w:w\in L\}$. Let $W_0=\{w\in W:|w|<n\}$. For each $w\in W_0$ and $a\in\Sigma$ let $\delta(q_w,a)=q_{wa}$; i.e., there is a transition $$q_w\overset{a}\longrightarrow q_{wa}\;.$$

Can you see how to finish defining $Q$ and $\delta$ so that $\langle Q,\Sigma,q_\epsilon,\delta,A\rangle$ is a DFA that accepts $L$? I’ve left the remaining details in the spoiler-protected block below.

Let $q^*$ be a state not in $Q_0$, and let $Q=Q_0\cup\{q^*\}$. For each $w\in W\setminus W_0$ and $a\in\Sigma$ let $\delta(q_w,a)=q^*$, and let $\delta(q^*,a)=q^*$ for all $a\in\Sigma$. (In other words, $q^*$ is a non-accepting trap state.) Check that $\langle Q,\Sigma,q_\epsilon,\delta,A\rangle$ is a DFA that accepts $L$.