patternMinor
Are number of states in a NFA same as Pumping length?
Viewed 0 times
samenumbernfaarelengthstatespumping
Problem
So i was reading a post on Minimum pumping length of regular language where Yuval Filmus has proved that a pumping lemma might have lesser number of states than a minimal DFA. But What about NFA's? Are NFA's able to give us minimum pumping length?
For example say we have a language L= $(10)^∗$, though for this minimal DFA will have $3$ states but NFA will have only $2$ states, which in fact is the pumping length of the language. So are NFA's able to give us exact pumping length of a language?
For example say we have a language L= $(10)^∗$, though for this minimal DFA will have $3$ states but NFA will have only $2$ states, which in fact is the pumping length of the language. So are NFA's able to give us exact pumping length of a language?
Solution
Here is a counterexample. Consider the language $L = 1^ + 0^1^n$. The minimal NFA for $L$ has $n+C$ states for some constant $C$, but every word can be pumped, so the pumping length is 1.
Context
StackExchange Computer Science Q#116229, answer score: 3
Revisions (0)
No revisions yet.