0
$\begingroup$

I am trying to construct a nfa that generalizes Example 1.33 found in the book Introduction to the Theory of Computation by Sipser, but I am quite sure that my transition function is wrong. I'd like some advice on how to fix that and how to simplify the notation such that to make it simpler.

Let $k > 0$ be a natural number and $B = \{n_{1}, n_{2}, \cdots, n_{k}\}$ a set with $k$ natural numbers. Let $\Sigma = \{0\}$ an unary alphabet and let

$$C = \{0^{i} \in \Sigma^{*} \mid i \in \bigcup_{b \in B} \{i \in \mathbb{N} \mid i = 0\ mod\ b \}\}$$

the set of all strings $0^{i}$ such that $i$ is a multiple of some natural in $B$. Construct a nondeterministic finite automaton $N$ that recognizes C.

We will construct a NFA that recognizes C.\

Let $k > 0$ be a natural number and $B = \{n_{1}, n_{2}, \cdots, n_{k}\}$ a set with $k$ natural numbers.

Let $N = (Q, \Sigma, \delta, q_{0}, F)$ where

$Q = \{q_{i,j} \mid 1 \leq i \leq k, 0 \leq j < n_{i}, n_{i} \in B\} \cup \{q_{start}\}$

$\Sigma = \{0\}$

for any $q \in Q$, any $a \in \Sigma \cup \{\epsilon \}$, $i, j \in \mathbb{N}$ and $n_{i} \in B$

$\delta(q, a) = \begin{cases} \{q_{i, 0} \in Q \mid 1 \leq i \leq k\} & q = q_{start},\ a = \epsilon \\ \emptyset & q = q_{start}, a \neq \epsilon \\ \{q_{i, l} \in Q \mid 1 \leq i \leq k, 0 \leq j < n_{i}, l = (j + 1)\ mod\ n_{i} \} & q \neq q_{start}, a = 0 \\ \{q_{i, j} \in Q \mid 1 \leq i \leq k, 0 \leq j < n_{i}\} & q \neq q_{start}, a = \epsilon \\ \end{cases}$

$q_{0} = q_{start}$

$F = \{q_{i, 0} \in Q \mid 1 \leq i \leq k\} $

After I convinced myself that the 3rd and 4th rule of the transition function above was wrong I rewrote it, as follows:

$\delta(q, a) = \begin{cases} \{q_{i, 0} \mid 1 \leq i \leq k\} & q = q_{start},\ a = \epsilon \\ \emptyset & q = q_{start},\ a \neq \epsilon \\ \{q_{i, (j+1)\ mod\ n_{i}} \} & 1 \leq i \leq k, 0 \leq j < n_{i},\ q = q_{i, j},\ a = 0 \\ \{q_{i, j}\} & 1 \leq i \leq k, 0 \leq j < n_{i},\ q = q_{i, j},\ a = \epsilon \\ %%\{q_{i, l} \in Q \mid 1 \leq i \leq k, 0 \leq j < n_{i}, l = (j + 1)\ mod\ n_{i} \} & q \neq q_{start}, a = 0 \\ %%\{q_{i, j} \in Q \mid 1 \leq i \leq k, 0 \leq j < n_{i}\} & q \neq q_{start}, a = \epsilon \\ \end{cases}$

$\endgroup$
2

Your Answer

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

Browse other questions tagged or ask your own question.