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 $