If L is a finite-size language then L is a regular language, meaning that it can be accepted by a finite state machine. Prove this by defining how to build—for any finite-size language L—a finite state machine M that accepts L and prove that L(M) = L. (Hint: a finite-size language has the notion of the “longest” word and a finite state machine can have a lot of states as long as its a finite number.)
(A language is a set of strings. A language is written using an alphabet. Σ = alphabet and Σ* = all words. L ⊆ Σ* is a language)
I have tried this question and haven't figured out how to define this. Any help would be greatly appreciated.
Let $L$ be a finite language in alphabet $\Sigma$ and let $n\in\Bbb N$ be the length of the longest word in $L$.
First let's build a very "large" machine that accepts the language $L_0=\Sigma^{\,\leq n}$ consisting of all the strings in alphabet $\Sigma$ with less than or equal to $n$ symbols. The machine I will build is by no means the simplest machine that recognises $L_0$, but it will serve as a template for building a machine for $L$.
It looks like a big tree, each state has an arrow for each symbol in the alphabet, and each arrow goes to a unique new state until we have read an input of length $n$. After that all states will send every longer input to a reject state. Every state is an accept state, except for the last state.
For example, if $\Sigma = \{0,1,2\}$ and $n=3$ the finite state machine looks like this:
Any of the accept states corresponds to a single string. For example, the bottom-most state can only be the final state if the input is the empty string, and the state in the top layer, fourth from the left only can be the final state if the input is $010$. Any string of length $4$ or longer will end up in the top most state, and will not be accepted.
Now, to create the machine for $L$, we simply "switch off" all the accept states that correspond to strings that are not in $L$. So if $010\notin L$, the state in the top layer, fourth from the left will become a reject state.
Of course, you can merge a lot of states to get a more compact machine later, but the thing we were interested in was that there exists a machine. For that purpose this is good enough.