0
$\begingroup$

Question:

Prove that a finite language is a regular language.

How would I go about solving this? I tried my own approach (below) but didn't get far because I don't understand how I am supposed to approach this proof.

My Approach:

Consider a finite automata M

($\delta$* denotes $\delta$ hat(^) which means all states w travels to until empty)

$M=(Q,\Sigma,\delta,q_0,F)$

if w is a string and w $\in$L* (any finite language)

=> $\delta$*($q_0$, w)$\in$F (then i make a logic statement that says for all w this is true?)

and if w$ \in$$\epsilon$

=> $\delta$*($q_0$, $\epsilon$ )$\in$F

$\endgroup$
3
$\begingroup$

Let $n$ be the maximum length of the words in the given finite language $L$, and let $m$ be the size of the (occuring letters from the) alphabet.
Build an automata with $\sum_{k\le n}m^k$ many states, one for each possible word, and mark exactly those states as accepting which correspond to a word in $L$.

$\endgroup$
  • $\begingroup$ you mean draw new DFA?would emphasis your prove please. $\endgroup$ – Jared Feb 19 at 0:13

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.