Given a language $L$ how can I determine the number of states of the minimal automate which recognizes $L$. I want some examples and to understand the methods that we can use to find a lower bound for the number of states ,for example:
Let $Σ=\{0,1\}$ and $L=\{1^n0^n /n\leq N\}$
What is the minimal number of states of deterministic finite automaton which recognizes $L$?
I use the following definition of an automate:
A deterministic finite automaton is represented formally by a $5$-tuple $(Q,Σ,δ,q_0,F)$, where:
$Q$ is a finite set of states.
$Σ$ is a finite set of symbols, called the alphabet of the automaton.
$δ$ is the transition function, that is, $δ: Q × Σ → Q$.
$q_0$ is the start state, that is, the state of the automaton before any input has been processed, where $q_0∈ Q$.
$F$ is a set of states of $Q$ (i.e. $F⊆Q$) called accept states.
Thanks for your help
There are standard algorithms for minimizing a DFA, producing another DFA that recognizes the the same language as the input DFA and has the smallest number of states among all DFAs that recognize this language. Any halfway adequate text in automata theory ought to explain them in excruciating detail.
Thus, if you have a regular language and want to know a strict lower bound for a the size of a DFA that recognizes it:
Construct some DFA for the language, usually (depending on which kind of description of the language you have already) by applying standard algorithms.
Minimize the DFA.
Count the number of states in the minimal DFA.