Finding maximum size of a finite language accepted by DFA

273 Views Asked by At

Let $k$ be the size of $Σ$ where $Σ$ is a finite alphabet, and $M$ be a $n$-state Deterministic Finite Automaton over $Σ$. When $L$ is a finite language accepted by $M$, how can the maximum value of $|L|$ be expressed with $n$ and $k$ ?

1

There are 1 best solutions below

0
On

Hint for a lower bound. How many states are needed to accept $\Sigma^r$?

Hint for an upper bound. What is the maximal length of a word of a finite language accepted by an $n$-state DFA?