<p>Let me add a concrete example to the excellent answer of Jeffrey Shallit.</p>

<p>Suppose you want to create a Scrabble (TM) dictionary. You can think of several ways to represent your dictionary, like list of words, tries (letter trees) or deterministic automata. According to [1], minimizing a trie to a dawg [= DFA] <em>produces an amazing savings in space; the number of nodes is reduced from 117,150 to 19,853. The lexicon represented as a raw word list takes about 780 Kbytes, while our dawg can be represented in 175 Kbytes.</em></p>

<p>As you can see, the state complexity really matters in this case, especially if you want to write an efficient program as the authors did. </p>

<p>[1] Appel and Jacobson <a href="http://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/lectures/scrabble.pdf">The World's Fastest Scrabble Program</a>, 
Communications of the ACM <strong>31</strong>, 572-578   (1988). </p>

CC BY-SA 3.0
2013-08-26T18:55:46.967Z
2013-08-26T20:10:00.593Z
2013-08-26T20:10:00.593Z
J.-E. Pin
<p>The proof that it is decidable whether an arbitrary deterministic context-free grammar (or equivalently a deterministic pushdown automaton) has an equivalent finite state automaton describing the same language is essentially a proof of the state complexity of finite automatons describing deterministic context-free languages: the bound on the size of these finite automatons in terms of the deterministic automatons gives bounds on the length of the decision procedure.</p>

<p>For details, see "<a href="http://reference.kfupm.edu.sa/content/r/e/regularity_and_related_problems_for_dete_81282.pdf" rel="nofollow">Regularity and related problems for deterministic pushdown
automata.</a>" by Leslie G. Valiant.</p>

CC BY-SA 3.0
2012-11-25T20:05:57.463Z
2012-11-25T20:05:57.463Z
Alex ten Brink
<p>State complexity is really about concise <em>description</em> of an object (in this case, a regular language), not about computational complexity.  The general topic is called "descriptional complexity" in the literature and draws its inspiration, in part, from the classic 1971 paper of Meyer and Fischer entitled "Economy of Expression by Automata, Grammars, and Formal Systems" (see <a href="http://people.csail.mit.edu/meyer/economy-of-description.pdf">http://people.csail.mit.edu/meyer/economy-of-description.pdf</a> ).  This is still an active area, with a yearly conference (DCFS - Descriptional Complexity of Formal Systems).</p>

<p>As for applications, any place where your program essentially relies on a finite-state machine (e.g., parsers) it will be good to have this finite-state machine as small as possible.  </p>

CC BY-SA 3.0
2012-11-27T05:53:14.520Z
Oh, okay. So basically reducing the state complexity helps in achieving a minimal representation of a given language, rather than make it easier to process?
Airmine
CC BY-SA 4.0
2019-10-09T09:06:08.713Z
Also, since most algorithms on automata directly depend on state complexity, minimizing states is often done with an ulterior motive of minimizing computational complexity.
Denis
CC BY-SA 3.0
2012-11-25T02:13:20.883Z
2012-11-25T02:13:20.883Z
Jeffrey Shallit
<p>I'm reading "<a href="http://dx.doi.org/10.1007/978-3-642-03351-3_20">Concatenation of Regular Languages and Descriptional Complexity</a>" by Galina Jiraskova, 2009 on the state complexity resulting from concatenation of two regular languages ( by Galina Jiraskova), but I can't understand what the practical implications of state complexity would be. The first trivial thought that struck me was that higher complexity would require more time and space by the machine. Is this correct? Also are there any other places where state complexity is relevant and signinficant? </p>

<p>Edit:
The state complexity of a regular language is the smallest number of states in any
deterministic finite automaton (dfa) accepting the language. The nondeterministic
state complexity of a regular language is defined as the smallest number of states in any nondeterministic finite automaton (nfa) for the language.</p>

CC BY-SA 3.0
2012-11-01T15:56:28.450Z
Sure thing. Edited the question!
Airmine
CC BY-SA 3.0
2012-11-01T18:15:07.683Z
It seems possible the paper you are reading answers the question to some degree...? Can you cite it in more detail eg the title & preferably a link to the pdf if available? FSM state complexity shows up in many applications & also has theoretical implications...
vzn
CC BY-SA 3.0
2012-11-01T18:45:29.120Z
Yes, I did look through the paper and looked through the references. Couldn't find much related to the applications of state complexity.
Airmine
CC BY-SA 3.0
2012-11-01T21:14:15.003Z
just about any FSM application (which there are many) must consider state complexity for nontrivial, "big" problems. example. FSMs are used in speech recognition where the states are phonemes & this can lead to large FSMs. FSMs are also used extensively in EE applications eg circuits etc. there a FSM with high complexity is a "big" circuit. however the paper in question is mainly looking at the theoretical complexity of the problem where upper/lower bounds on "blowup" or "efficient minimization" (compression) are key properties to study....
vzn
CC BY-SA 3.0
2012-11-04T16:25:42.803Z
Not exactly "practical", but state complexity plays a role in *Diversity-based inference of finite automata* by Rivest and Schapire: [[conference](http://people.csail.mit.edu/rivest/pubs/RS87c.pdf); [journal](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.1719&rep=rep1&type=pdf)].
Neal Young
<fl.formal-languages><automata-theory><regular-language>
The significance of state complexity in automata and regular languages?
Airmine
# The significance of state complexity in automata and regular languages?

(Asked by: username_0 on 2012-11-01)

I'm reading "[Concatenation of Regular Languages and Descriptional Complexity](http://dx.doi.org/10.1007/978-3-642-03351-3_20)" by Galina Jiraskova, 2009 on the state complexity resulting from concatenation of two regular languages ( by Galina Jiraskova), but I can't understand what the practical implications of state complexity would be. The first trivial thought that struck me was that higher complexity would require more time and space by the machine. Is this correct? Also are there any other places where state complexity is relevant and signinficant?

Edit:
The state complexity of a regular language is the smallest number of states in any
deterministic finite automaton (dfa) accepting the language. The nondeterministic
state complexity of a regular language is defined as the smallest number of states in any nondeterministic finite automaton (nfa) for the language.

**Tags:** fl.formal-languages, automata-theory, regular-language
> **Comments:**
> **username_0**: Sure thing. Edited the question!  
> **username_1**: It seems possible the paper you are reading answers the question to some degree...? Can you cite it in more detail eg the title & preferably a link to the pdf if available? FSM state complexity shows up in many applications & also has theoretical implications...  
> **username_0**: Yes, I did look through the paper and looked through the references. Couldn't find much related to the applications of state complexity.  
> **username_1**: just about any FSM application (which there are many) must consider state complexity for nontrivial, "big" problems. example. FSMs are used in speech recognition where the states are phonemes & this can lead to large FSMs. FSMs are also used extensively in EE applications eg circuits etc. there a FSM with high complexity is a "big" circuit. however the paper in question is mainly looking at the theoretical complexity of the problem where upper/lower bounds on "blowup" or "efficient minimization" (compression) are key properties to study....  
> **username_2**: Not exactly "practical", but state complexity plays a role in *Diversity-based inference of finite automata* by Rivest and Schapire: [[conference](http://people.csail.mit.edu/rivest/pubs/RS87c.pdf); [journal](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.1719&rep=rep1&type=pdf)].  

---

## 3 answers

### Answer by username_5 on 2012-11-25. Score: 18 | Accepted answer

State complexity is really about concise *description* of an object (in this case, a regular language), not about computational complexity. The general topic is called "descriptional complexity" in the literature and draws its inspiration, in part, from the classic 1971 paper of Meyer and Fischer entitled "Economy of Expression by Automata, Grammars, and Formal Systems" (see <http://people.csail.mit.edu/meyer/economy-of-description.pdf> ). This is still an active area, with a yearly conference (DCFS - Descriptional Complexity of Formal Systems).

As for applications, any place where your program essentially relies on a finite-state machine (e.g., parsers) it will be good to have this finite-state machine as small as possible.

> **Comments:**
> **username_0**: Oh, okay. So basically reducing the state complexity helps in achieving a minimal representation of a given language, rather than make it easier to process?  
> **username_6**: Also, since most algorithms on automata directly depend on state complexity, minimizing states is often done with an ulterior motive of minimizing computational complexity.  

---

### Answer by username_3 on 2013-08-26. Score: 9

Let me add a concrete example to the excellent answer of Jeffrey Shallit.

Suppose you want to create a Scrabble (TM) dictionary. You can think of several ways to represent your dictionary, like list of words, tries (letter trees) or deterministic automata. According to [1], minimizing a trie to a dawg [= DFA] *produces an amazing savings in space; the number of nodes is reduced from 117,150 to 19,853. The lexicon represented as a raw word list takes about 780 Kbytes, while our dawg can be represented in 175 Kbytes.*

As you can see, the state complexity really matters in this case, especially if you want to write an efficient program as the authors did.

[1] Appel and Jacobson [The World's Fastest Scrabble Program](http://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/lectures/scrabble.pdf),
Communications of the ACM **31**, 572-578 (1988).


---

### Answer by username_4 on 2012-11-25. Score: 4

The proof that it is decidable whether an arbitrary deterministic context-free grammar (or equivalently a deterministic pushdown automaton) has an equivalent finite state automaton describing the same language is essentially a proof of the state complexity of finite automatons describing deterministic context-free languages: the bound on the size of these finite automatons in terms of the deterministic automatons gives bounds on the length of the decision procedure.

For details, see "[Regularity and related problems for deterministic pushdown
automata.](http://reference.kfupm.edu.sa/content/r/e/regularity_and_related_problems_for_dete_81282.pdf)" by Leslie G. Valiant.


---

