0

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

Chris
  • 521

1 Answers1

2

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.

vonbrand
  • 27,812
  • 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. – Chris Mar 05 '14 at 06:28
  • A DFA is just a NFA with sets of size one throughout. And you can't do with less states. – vonbrand Mar 05 '14 at 07:57
  • 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$ – Chris Mar 05 '14 at 09:23
  • should not $\delta(a\sigma,b)$ be $\delta(\sigma a,b)$ ? – Chris Mar 05 '14 at 09:29
  • @Chris, the idea is that for $n = 4$ you have for example $\delta(0100, 1) = 1001$ (shift the 0 out, shift the 1 in). – vonbrand Mar 05 '14 at 10:23
  • Ok. So with the example of $n=4$ and the word $1101001$ the transitions would look like this: $(\epsilon,1101001) \vdash (1,101001) \vdash (11,01001) \vdash (110,1001) \vdash (1101,001) \vdash (1010,01) \vdash (0100,1) \vdash (1001,\epsilon)$ ? So for this I would need 8 different states – Chris Mar 05 '14 at 11:44
  • sorry I edited my question and added an automata with $n=4$ – Chris Mar 05 '14 at 11:53