# Languages recognized by finite state automata of polynomially growing size

In the course of my research (condensed matter physics stuff), I stumbled over the following concept:

The class of regular languages can be defined via finite state machines (FSM): A language $L$ is regular iff there is an FSM which accepts $L$. Clearly every finite language is regular.

I am interested in the following (larger) class of languages (call it $\mathcal{L}^?$) over some finite alphabet $\Sigma$ with relaxed conditions:

A language $L$ is in $\mathcal{L}^?$ $:\Leftrightarrow$

There is a sequence of FSMs $(M_n)_{n\in\mathbb{N}}$ such that

1. $w\in L\,\Leftrightarrow\,$ $M_{|w|}(w)$ accepts
2. $|M_n|\leq \operatorname{Poly}(n)$

Here $|w|$ denotes the length of word $w$ and $|M|$ is the size of the FSM $M$, i.e., its number of states.

Obviously all languages $L\subseteq \Sigma^\ast$ are included if one drops the second requirement, as the sublanguages $L_n\subseteq L$ of words with fixed length $n$ are finite. But for a generic language $L_n$ with fixed length words, the minimal accepting FSA has a size exponentially growing in $n$ (is this correct? I sketched just a naive counting argument...).

As I'm no computer scientist, I was wondering whether this concept is already known in automata theory / computability theory (and if so, how it is called). Due to my lack of expertise, I just do not know where to start.

I would be very happy if you could ...

• either provide a pointer to the relevant topic of automata theory (terms I have to look for, relevant publications)
• or give an alternative characterization of this class (maybe it's just equivalent to one of the well-known language classes?)

• @NcLang : $\:$ Are FSMs allowed to go backwards over the input? $\;\;\;\;$ – user12859 Sep 26 '14 at 21:17