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
Related Tags
nondeterminism × 313finite-automata × 108
automata × 85
complexity-theory × 70
turing-machines × 68
pushdown-automata × 34
formal-languages × 32
algorithms × 25
time-complexity × 20
context-free × 20
np × 20
regular-languages × 17
space-complexity × 17
computation-models × 15
polynomial-time × 12
terminology × 10
closure-properties × 10
computability × 8
reference-request × 8
regular-expressions × 8
satisfiability × 7
simulation × 7
np-complete × 6
formal-grammars × 6
complexity-classes × 6