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$ enter image description here


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.

  • $\begingroup$ Hi. If I understood you correctly this will create a DFA and not an NFA while I should create an NFA with the least amount of states. $\endgroup$ – Chris Mar 5 '14 at 6:28
  • $\begingroup$ A DFA is just a NFA with sets of size one throughout. And you can't do with less states. $\endgroup$ – vonbrand Mar 5 '14 at 7:57
  • $\begingroup$ Maybe I misunderstood your solution. Can you explain me what happens on transition for $n-1$. Lets say we have an example for $n=2$. Going through your transition I would have the following sequence word $w=0100$ : $(s,0100) \vdash (0,100) \vdash $ at this point we would be at $|\sigma|=n-1$ $\endgroup$ – Chris Mar 5 '14 at 9:23
  • $\begingroup$ should not $\delta(a\sigma,b)$ be $\delta(\sigma a,b)$ ? $\endgroup$ – Chris Mar 5 '14 at 9:29
  • $\begingroup$ @Chris, the idea is that for $n = 4$ you have for example $\delta(0100, 1) = 1001$ (shift the 0 out, shift the 1 in). $\endgroup$ – vonbrand Mar 5 '14 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.