# Tag Info

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