Create a general NFA for $M_n$

Question

I need to create a general NFA $M_n$ where $n \in \mathbb{N_0}$ with the following language defined: $$L(M_n) = \left\{ w \in \{0,1\}^* \big | x1y \textit{ for } x \in \{0,1\}^* \textit{ and } y \in \{0,1\}^{n-1}\right\}$$

As an example for $L(M_N) = \{0100,0101,00110,...\}$

My idea for $M_2 = (\{q_0,q_1,q_2,q_3\},\delta_n,q_0,\{q_3\})$ would look like this (i wish I could show you the graph but it does not let me draw with tikz):

$\delta_n(q_0,0)=\{q_0\}\\ \delta_n(q_0,1)=\{q_0,q_1\}\\ \delta_n(q_1,0)=\{q_2\}\\ \delta_n(q_1,1)=\{q_2\}\\ \delta_n(q_2,0)=\{q_3\}\\ \delta_n(q_2,1)=\{q_3\}\\ $

It needs the first 2 states $q_0$ and $q_1$ plus n-amount states. The final state is the accepting one. Every state starting from $q_1$ will redirect $0,1$ to the next higher state

I am not quite sure how I should define this globally so it fits for all $M_n$. I came up with the following solution but it looks quite complicated to me..

$M_n = (Q_n, \{0,1\},\delta _n,q_0,F), n \in \mathbb{N}_0\\ Q_n = \{q_0,q_1,...,q_n,q_{n+1}\}, |Q_n|=2+n\\ L(M_n) = \left\{ w \in \{0,1\}^* \big | x1y \textit{ for } x \in \{0,1\}^* \textit{ and } y \in \{0,1\}^{n-1}\right\}\\ F=\{q_{n+1}\}\\\\ \delta _n(q,a) = \begin{cases} \{q_0\} & q=q_0 \land a = 0,1\\ \{q_1\} & q=q_0 \land a = 1\\ \{q_k\} & q=q_{k-1} \land a = 0,1 \textit{ for } q_k \in Q_n\\ \{q_{n+1}\} & q=q_n \land a = 0,1 \end{cases}$

Possible automata for $n=4$

Answer 1

Better use a diagram when designing automata, writing out the tables soon gets too hairy.

In this case, what your NFA has to "remember" is what the last (up to) $n$ symbols where, and accepting states will be those where the "memory" is $n$ symbols long and starts with 1. The "up to" above is to start filling the pipe (read symbols up to the $n$-th). Tables are hairy, but manageable...

States are strings of up to $n$ symbols (a finite set, so OK). Call them $\sigma$ for conciseness. Start state is $\epsilon$ (nothing seen yet).

Transitions are:

• If $\lvert \sigma \rvert < n$, $\delta(\sigma, a) = \sigma a$ for all $\sigma \in \{0,1\}^*$ and $a \in \{0, 1\}$
• If $\lvert \sigma \rvert = n - 1$, $\delta(a \sigma, b) = \sigma b$ for all $a, b \in \{0, 1\}$ and for all $\sigma \in \{0,1\}^*$

Final states are $1 \sigma$ with $\sigma \in \{0,1\}^*$ and $\lvert \sigma \rvert = n - 1$

The $\delta$ defined is a function. As a result, you have a DFA.