## Language Families

Id Name Formula Description Parameter U $|\Sigma|$
4 Universe $\Sigma^\star$  0 
5 Number of a's are m-1 mod m $\{w\in\{a,b\}^\star\mid\#_a(w)= m-1\mod m\}$

$L_m$ is accepted by a $m$-state minimal DFA

$m$ 0 $2$
6 

$L_n=L(A)$ where $A=([0,n-1],\{a,b\},\delta,0,\{n-1\})$ with

$\delta(0,a)=0$, $\delta(0,b)=1$, $\delta(i,a)=i+1$, for $i\in[1, n-2]$,

$\delta(n-1,a)=1$, and $\delta(i,b)=i$, for $i\in[0,n-1]$.

$n$ 0 $2$
7 

$A=([0,m-1],\{a,b,c\},\delta,0,\{m-1\})$, and for all $i\in[0,m-1]$,

$\delta(i,X) = \left \{ \begin{array} {ll} (i+1)\mod m, & \text{if X=a} \\ 0, & \text{if X=b} \\ i, & \text{if X=c} \end{array} \right.$

$m$ 0 $3$
8 

$L_m=L(A)$ with

$A=([0,m-1],\{a,b,c\},\delta,0,\{m-1\})$, and for all $i\in[0,m-1]$,

$\delta(i,X) = \left \{ \begin{array} {ll} i, & \text{if X=a} \\ (i+1)\mod m, & \text{if X=b} \\ 1, & \text{if X=c} \end{array} \right.$

$m$ 0 $3$
9 $a^{n-1}(a^n)^\star$

$L_n$ is accepted by an $n$-state DFA.

$n$ 0 $1$
10 Odd number of a's on words over $\{a,b\}$ 

$L=\{w\in \{a,b\}^\star\mid \#_a(w) \text{ is odd }\}$

 0 $2$
11 

$A_1=([0,m-1],\{a,b\},\delta_1,0,\{m-1\})$. For any $i\in [1,m-1]$,

$\delta_1(i,a)=(i+1)\mod m$, $\delta_1(0,b)=0$, and $\delta_1(i,b)=(i+1)\mod m$, if $i>0$.

$m$ 0 $2$
13 Iteration of word $aa$ $(aa)^\star$

The language is accept by a 2-state DFA $A=(\{0,1\},\{a\},0,\delta,\{0\})$ where $\delta(0,a)=1$ and $\delta(1,a)=0$.

$m$ 0 $1$
14 $(a^m)^{\star}a^{m-1}$

$A_1=([0,m-1],\{a\},\delta,0,[m-1])$

$\delta(i,a)=i+1\mod m$ for $i\in [0,m-1]$

$m$ 0 $1$
15 

$A_1=([0,m-1],\{a,b,c\},\delta_1,0,\{0\})$, where

$\delta_1(0,a)=m-1$, $\delta_1(0,b)=1$, $\delta_1(0,c)=1$, $\delta_1(1,c)=0$, and

for any $i\in[1,m-1]$, $\delta_1(i,a)=i-1$, $\delta_1(i,b)=i$, and  $\delta_1(i,c)=i$ if $i>1$.

$m$ 0 $3$
16 $\{x\in\{a,b\}^\star \mid \#_a(x)=0\mod m\}$

It is represented by a $m$-state DFA.

$m$ 0 $2$
17 $\{x\in\{a,b\}^\star \mid \#_b(x)=0\mod m\}$ $m$ 0 $2$
18 $\{a,b\}^* -\{x\in\{a,b\} \mid \#_b(x)=0\mod m\}$ $m$ 0 $2$
19 $\{a,b\}^*-\{x\in\{a,b\} \mid \#_a(x)=0\mod m\}$ $m$ 0 $2$
20 $(a^m)^*$

$\Sigma=\{a,b\}$

$m$ 0 $2$
21 $(b^m)^*$

$\Sigma=\{a,b\}$

$m$ 0 $2$
22 

$A =([0,m-1],\{a,b\},\delta,0,\{m-1\})$, where

$\delta(i,X)= \left \{ \begin{array}{lr}\{i + 1\}&\text{if } i< m-1 \text{ and } X=b,\\ \emptyset & \text{if } i = m-1 \text{ and } X=b,\\\{0, i + 1\}&\text{if } i< m-1 \text{ and } X=a,\\\{1,\ldots, m-1\} &\text{if } i = m-1 \text{ and } X=a.\end{array}\right.$

$m$ 0 $2$
23 $(a^m)^\star$ $m$ 0 $1$
24 $a^{m-1}$

$m>0$

$m$ 0 $1$
25 

$A=([0,m-1],\{a,b,c,d,f\},\delta,0,\{0\})$ incomplete DFA, where

$\begin{array}{lclr} \delta(i,a)&=&i+1\mod m, & \text{for } i \in [0,m-1] \\ \delta(i,c)&=&i+1, & \text{for } i \in [0,m-1[ \\ \delta(i,d)&=&i, & \text{for }i \in [0,m-1]\\ \delta(i,f)&=&i, & \text{for }i \in [1,m-1]\\ \end{array}$

Used for an lower bound of state complexity of shuffle operations.

 0 $5$
26 
$A=([0,m-1],\{a,b,c,d,f\},\delta,0,\{0\})$ incomplete DFA

$\begin{array}{lclr} \delta(i,b)&=&i+1\mod m, & \text{for }i \in [0,m-1]\\ \delta(i,c)&=&i, & \text{for }i \in [0,m-1] \\ \delta(i,d)&=&i+1, & \text{for }i \in [0,m-1[ \\ \delta(i,f)&=&i, & \text{for }i \in [1,m-1] \\ \end{array}$

 0 $5$
27 $\{x\in \{a\}^* \mid \#_a(x)= 0 \mod m\}$ $m$ 0 $1$
28 $L_t=\{a, b\}^\star\{a, b\}^tb\{a, b\}^\star$

$nsc(L_t)=m= t+3$

$m$ 0 $2$
29 

$L_m=L(A)$ where the NFA $A=([1,m],\{a,b\},\delta,1,[1,m])$ with

$\delta(i,X)=\left \{ \begin{array}{lr} \{i+1\}&\text{ if } i<n \text{ and } X=a \\ \{1\} &\text{ if } i=n \text{ and } X=b \\ \emptyset & \text{ otherwise} \end{array}\right .$

$m$ 0 $2$
30 

The NFA for this language family has states $[0, 1, \dots, n-1]$, and alphabet $\{a,b\}$.

Input $a$ takes state $i$ to state $(i+1) \mod n$. Input $b$ takes $i$ to itself and $0$ for $i \neq 0$.

State $0$ is both start and final state.

$n$ 0 $2$
31 $ab^\star a$  0 $2$
32 $(b^\star a) ^{m-1}(a+b)^\star$
$m$ 0 $2$
33 $(a^\star b)^{n-1}(a+b)^\star$
$n$ 0 $2$
34 $((b+c)^\star a)^{m-1}(a+b+c)^\star$ $m$ 0 $3$
35  The DFA has state set $Q=\{0,1, ..., n-1\}$, $\Sigma=\{a,b,c\}$, $q_0=0$, $F=\{n-1\}$, $a$ performs the identity transformation, $b$ maps state $i$ to $i+1$ if $i<n-1$ and $n-1$ to itself, and $c$ maps all states to $0$.  0 
36  The DFA has state set $Q=\{0,1,\ldots,n-1\}$, $\Sigma=\{a,b,c,d\}$, $q_0=0$, $F=\{n-1\}$, $a$ maps state $i$ to $i+1$ for $i<n-1$ and $n-1$ to itself, $b$ and $c$ perform the identity transformation, and $d$ maps all states to $0$.  0 
37  The DFA has state set $Q=\{0,1,\ldots,n-1\}$, $\Sigma=\{a,b,c,d\}$, $q_0=0$, $F=\{n-1\}$, $a$ and $d$ perform the identity transformation, $b$ maps state $i$ to $i+1$ for $i<n-1$ and $n-1$ to itself,   and $c$ maps all states to $0$.  0 
38 $a^{m-1}a^\star$ $m$ 0 $1$
39 $a^{n-1}a^\star$ $n$ 0 $1$
40 $(a+b)^{m-1}(a+b)^\star$ $m$ 0 $2$
43 $(b+a(a+b)^{n-3}a)^\star a(a+b)^{n-3}b (a+b)^\star$ $n$ 0 $2$
44 $b^\star a(a+b)^\star$  0 $2$
45  $A=(Q,\Sigma,\delta,q_0,F)$, where $Q=\{0,1,\ldots,m-1\}$, $\Sigma=\{a_1,\ldots,a_{m-2},b_1,\ldots,b_{m-2}\}$, $q_0=0$, $F=\{m-1\}$, $a_i$ maps $0$ to $i$ and all the other states to $m-1$, and $b_i$ maps $i$ to $m-1$ and every other state to itself. $m$ 0 $2m-4$
47 $aa^\star$  0 $1$
48  For $m\ge 5$, $A=(Q,\Sigma,\delta,q_0,F)$, where $Q=\{0,1,\ldots,m-1\}$, $\Sigma=\{a,b,c\}$, $q_0=0$, $F=\{m-1\}$, $a$ performs the cycles $(1,2,3)(4,\ldots,m-1)$, $b$ maps $2$ to $1$ and transposes $3$ and $4$ , and $c$ maps all the states to $0$.
For $m=4$, $a$ performs the cycle $(1,2,3)$, and $b$ maps $2$ to $1$.
For $m=3$, $a$ performs the cycle $(1,2)$, and $b$ maps $2$ to $1$.
$m$ 0 $3$
49 $(a+b)^\star a$  0 $2$
50  $A=(Q,\Sigma,\delta,q_0,F)$, where $Q=\{0,1,\ldots,m-1\}$, $\Sigma=\{a,b,c\}$, $q_0=0$, $F=\{m-1\}$, $a$ maps $i$ to $i+1$ for $i \not \in \{0,m-1\}$, $b$ performs the cycle $(1,\ldots,m-2)$, and $c$ maps all states other than $m-1$ to $1$. $m$ 0 $3$
51 $(b+ab)^\star a (ab^\star)^{m-3}a(a+b)^\star$ $m$ 0 $2$
52  For $m\ge 4$, $A=(Q,\Sigma,\delta,q_0,F)$, where $Q=\{0,1,\ldots,m-1\}$, $\Sigma=\{a,b,c\}$, $q_0=0$, $F=\{m-1\}$, $a$ maps $i$ to $i+1$ for $i\le m-3$, $b$ maps $1$ to $0$, and $c$ maps $i$ to $0$ if $i<m-2$ and maps $m-2$ to $m-1$. $m$ 0 $3$
53 $aaa^\star$  0 $1$
54 $a^\star$  0 $1$
55 $(b+a(a+b)^{m-1})^\star a (a+b)^{m-2}$ $m$ 0 $2$
57 $(a+b)^\star$  0 $2$
58 $(b+a(a+b)^{m-3}a)^\star a (a+b)^{m-3}b (a+b)^\star$ $m$ 0 $2$
59 $\sum_{i=1}^{m-2} a_i \Sigma^\star a_i \Sigma^\star$ $m$ 0 $m-2$
60 $a(a+b)^{m-3}$ $m$ 0 $2$
61 $a(a+b)^{m-4}a$ $m$ 0 $2$
64 $a$  0 $1$
65 $\sum_{i=1}^{m-3} a_i a_i$ $m$ 0 $m-3$
66 $a^{n-3} \{a^{n-2}\}^\star ( \{b\}^\star \cup \{c\}^\star)$
$n$ 0 $3$
67 
Let $A=([0,m-1],\{a,b\},\delta,0,\{0\})$, where $\delta$ is defined as follows:

$\begin{array}{lclr} \delta(i,a)&=&i+1, & \text{for }i \in [0,m-2]\\ \delta(i,b)&=&i+1, & \text{for }i \in [0,m-2] \\ \delta(m-1,a)&=&0, & \\ \delta(m-1,b)&=&1 & \\ \end{array}$
$m$ 0 $2$
68  Let $A=([0,n-1],\{a,b\},\delta,0,\{0\})$, where $\delta$ is defined as follows:

$\begin{array}{lclr} \delta(i,a)&=&i, & \text{for }i \in [1,n-1]\\ \delta(i,b)&=&i+1 \mod n, & \text{for }i \in [0,n-1] \\ \delta(0,a)&=&1 & \\ \end{array}$

$n$ 0 $2$
69  Let $A=([0,m-1],\{a,b,c,d,e,f\},\delta,0,\{m-1\})$, where $\delta$ is defined as follows:

$\begin{array}{lclr} \delta(i,a)&=&i+1 \mod m, & \text{for }i \in [0,m-1]\\ \delta(i,b)&=&i, & \text{for }i \in [0,m-1] \\ \delta(i,c)&=&i+1 & \text{for }i \in [1,m-2]\\ \delta(i,d)&=&i & \text{for }i \in [0,m-1]\\ \delta(i,e)&=&i & \text{for }i \in [2,m-1]\\ \delta(i,f)&=&i & \text{for }i \in [0,m-1]\\ \end{array}$

and, $\delta(0,c) = 0$, $\delta(m-1,c) = 1$, $\delta(0,e) = 0$, $\delta(1,e) = 0$

$m$ 0 $6$
70  Let $A=([0,n-1],\{a,b,c,d,e,f\},\delta,0,\{n-1\})$, where $\delta$ is defined as follows:

$\begin{array}{lclr} \delta(i,a)&=&i+1 \mod n, & \text{for }i \in [0,n-1]\\ \delta(i,b)&=&i+1 \mod n, & \text{for }i \in [0,n-1] \\ \delta(i,c)&=&i & \text{for }i \in [0,n-1]\\ \delta(i,d)&=&i+1 & \text{for }i \in [1,n-2]\\ \delta(i,e)&=&i & \text{for }i \in [0,n-1]\\ \delta(i,f)&=&i & \text{for }i \in [2,n-1]\\ \end{array}$

and, $\delta(0,d) = 0$, $\delta(n-1,d) = 1$, $\delta(0,f) = 0$, $\delta(1,f) = 0$

$n$ 0 $6$
71  Let $A=([0,m-1],\{a,b,c,d\},\delta,0,\{m-1\})$, where $\delta$ is defined as follows:

$\begin{array}{lclr} \delta(i,a)&=&i+1 \mod m, & \text{for }i \in [0,m-1]\\ \delta(i,b)&=&i, & \text{for }i \in [0,m-1] \\ \delta(i,c)&=&i+1 \mod m & \text{for }i \in [1,m-1]\\ \delta(i,d)&=&i & \text{for }i \in [0,m-1]\\ \end{array}$

and, $\delta(0,c) = 0$

$m$ 0 $4$
72  Let $A=([0,n-1],\{a,b,c,d\},\delta,0,\{n-1\})$, where $\delta$ is defined as follows:

$\begin{array}{lclr} \delta(i,a)&=&i, & \text{for }i \in [0,n-1]\\ \delta(i,b)&=&i+1 \mod n, & \text{for }i \in [0,n-1] \\ \delta(i,c)&=&i& \text{for }i \in [0,n-1]\\ \delta(i,d)&=&i+1 \mod n & \text{for }i \in [1,n-1]\\ \end{array}$

and, $\delta(0,d) = 0$
$n$ 0 $4$
73 

$A=([0,m-1],\{a,b,c\},\delta,0,\{m-1\})$, where

$\delta(0,a)=m-1$, $\delta(0,b)=1$, $\delta(0,c)=1$, $\delta(1,c)=0$, $\delta(1,a)=0$,and

for any $i\in[1,m-1]$, $\delta(i,a)=i-1$, $\delta(i,b)=i$, and  $\delta(i,c)=i$ if $i>1$.

$m$ 0 $3$
74 

$A=([0,n-1],\{a,b,c\},\delta,0,\{n-1\})$, where

$\delta(0,c)=n-1$, $\delta(0,b)=1$, $\delta(0,a)=1$, $\delta(1,a)=0$, $\delta(1,c)=0$,and

for any $i\in[1,n-1]$, $\delta(i,c)=i-1$, $\delta(i,b)=i$, and  $\delta(i,a)=i$ if $i>1$.

$n$ 0 $3$
75 
Let $A=([0,m-1],\{a,b\},\delta,0,\{m-1\})$, where $\delta$ is defined as follows:

$\begin{array}{lclr} \delta(i,a)&=&i+1, & \text{for }i \in [0,m-2]\\ \delta(i,b)&=&i+1, & \text{for } i \in [1,m-2] \\ \delta(m-1,a)&=&0, & \\ \delta(m-1,a)&=&1, & \\ \delta(0,b)&=&0 & \\ \end{array}$

$m$ 0 $2$
76 
$A=([0,m-1],\{a,b,c\},\delta,\{0\},\{0\})$ NFA

$\begin{array}{lclr} \delta(0,a)&=& 1\\ \delta(0,b)&=& 1\\ \delta(1,b)&=& 0\\ \delta(1,c)&=& 0\\ \delta(1,c)&=& 1\\ \delta(1,a)&=& 2\\ \delta(m-1,a)&=& 0\\ \delta(m-1,b)&=& m-1\\ \delta(m-1,c)&=& m-1\\ \delta(i,a)&=&i+1, & \text{for }i \in [2,m-2] \\ \delta(i,b)&=&i, & \text{for }i \in [2,m-2] \\ \delta(i,c)&=&i, & \text{for }i \in [2,m-2] \\ \end{array}$
$m$ 0 $3$
77 
$A_m=([0,m-1],\{a,b,c\},\delta,0,\{0\})$ DFA

$\begin{array}{lclr} \delta(0,b)&=& 1\\ \delta(1,b)&=& 0\\ \delta(0,c)&=& m-1\\ \delta(i,a)&=&(i+1)\mod{m}, & \text{for }i \in [0,m-1] \\ \delta(i,b)&=&i & \text{for }i \in [2,m-1] \\ \delta(i,c)&=&i, & \text{for }i \in [1,m-1] \\ \end{array}$

 0 $3$