New answers tagged nondeterminism
0
This may not be computationally fast, but the most straightforward algorithm that I know for converting REs to NFAs is to use Brzozowski derivatives. This is so simple that it can be done by hand, and results in NFAs with a number of states that is linear (for the usual RE operators; more on this in a moment) in the number of terminal symbols.
To understand ...
2
The automaton accepts all non-empty strings in which the last symbol $\sigma$ appears at least twice, and all symbols appearing between its penultimate appearance and its last appearance are smaller than $\sigma$.
4
The number $504$ has $4\cdot3\cdot2=24$ divisors:
$$1,
2,
3,
4,
6,
7,
8,
9,
12,
14,
18,
21,
24,
28,
36,
42,
56,
63,
72,
84,
126,
168,
252,
504$$
Out of these, $20$ are at least $6$:
$$
6,
7,
8,
9,
12,
14,
18,
21,
24,
28,
36,
42,
56,
63,
72,
84,
126,
168,
252,
504$$
For an integer $n$, $\operatorname{gcd}(n,504) \geq ...
1
Your solution is nearly correct, however you need to remove the $c$-transition of $S_0$ and the $a$-transition from $S_0$ to $S_2$ and add a new state, say $S_3$, which is reached from $S_0$ via an $\varepsilon$-transition, has a $c$-transition to itself and an $a$-transition to $S_2$ (so that the word $cab$ is not recognized anymore, see benrg's comment ...
1
Is there a general way to do it? The answer is yes: one way to do it is to find a DFA that accepts $L$ (for example with the powerset construction), make it complete (by adding a sink state), and swap final states and non-final states. The automaton is deterministic, but it is a special case of non deterministic.
Is there a polynomial time way to do it? I ...
1
Your answers to (a), (b), and (c) seem correct to me. Here's something to think about for (d).
Hint for (d): Let's say $s = s_1s_2...s_k \in L$, and on input $s$ the original transition function follows the path $P = q_0, q_1... q_f$. Let $q_{s_i}$ denote the state $q_i$ closest to $q_f$ in $P$ after only reading up to $s_i$ in the original NFA. What are the ...
Top 50 recent answers are included
