3

It depends on the definition. Some definitions of a deterministic finite automaton (DFA) are a quadruplet $(Q, \delta, q_0, F)$ where $Q$ is the set of states and $q_0 \in Q$ is the initial state. Therefore, it must be defined. However, the definition of non-deterministic finite automaton (NFA) is sometimes seen as a quadruplet $(Q, \Delta, I, F)$ where $Q$ ...


2

The transition function can be represented as a two dimensional array. For your automaton, you just need to complete the following: $\begin{array}{|c|c|c|} \hline & a & b\\ \hline q_1& &\\ \hline q_2& &\\ \hline q_3& &\\ \hline q_4& &\\ \hline \end{array}$ It can also be defined as a set of triplets $(q, a, \delta(q, a)...


2

Aside from trivial cases, transforming lexicographic order indices from one ordering to another ordering can can rarely be done more efficiently than unranking the index using the original alphabet ordering, and then ranking the resulting sequence using the new alphabet ordering. That works fine in this case, because after precomputation of a table of size $...


2

Any word accepted by this regular expression has to be either in length 3 or to end with $aba$ or $baa$. Try to prove this fact, and use it to show that $aabaabba$ must be rejected.


1

If $n$ is odd, no comparison involving elements of $S$ is performed outside of the for loop. Moreover, each loop iteration performs exactly $3$ comparisons involving some element in $S$. The number of iterations is the minimum integer value of $k$ such that $2+2k > n$, i.e., $k=\left\lceil \frac{n-2}{2} \right\rceil = \frac{n-1}{2}$. Therefore, the total ...


1

$\log n! \le \log n^n = n \log n = o(n^n)$.


1

It is well known that $\ln(n)=o(n^{\epsilon'})$ for any $\epsilon'>0$. Now, fix some $k$, and define $\epsilon':=\frac{\epsilon}{k}$. From the multiplicative rule of the small-o (or equivalently, the multiplicative rule of limits), since $k\in \mathbb{N}$, we get: $\ln^k(n)={o(n^{\epsilon'})}^k=o({(n^{\epsilon'})}^k)=o(n^{k\epsilon'})=o(n^\epsilon)$. Thus ...


1

The notation $\log^k n$ most likely stands for $(\ln n)^k$ (this is a common abuse of notation). In this case the claim is trivially when $\varepsilon=0$ true since $n^\varepsilon=1$ and $\ln^k n = \Omega(1)$. For constant $\varepsilon>0$ and $k \ge 1$ you have: $$ \lim_{n \to +\infty} \frac{\ln^k n}{n^\varepsilon} = \lim_{n \to +\infty} \left( \frac{\ln ...


1

A little abstraction would help both reasoning about and solving the problem efficiently, I think. For every point $x$ on the circle, there is some set $S_x$ of pairwise overlapping arcs that intersect this point. Now, if there is some other point $y$ such that $S_x \subseteq S_y$, you can always use $y$ instead of $x$ in a solution to your problem. We can ...


1

I think there is a mistake in your post: the first equation should be $\ddot{x}(t) = F(t, \dot{x}(t), x(t))$ (and not $\ddot{x}(t + dt)$). Also, in the computation of $kv_i$ and $kx_i$, it should be $kv_i = v(t) + ka_{i-1}\Delta t$ and $kx_i = x(t) + kv_i\Delta t$ (where $\Delta t = dt$ or $\frac{dt}{2}$). $kv_i$ does not use $kv_{i-1}$ (except in the ...


1

For direct result let's use direct summation assuming $n=2^k$: $$T(n) = 2T\left(\frac{n}{2}\right) + n\log(n)=2\left[ 2T\left(\frac{n}{2^2}\right) +\frac{n}{2}\log \frac{n}{2}\right]+ n\log(n) = \\ =2^2T\left(\frac{n}{2^2}\right)+n\log \frac{n}{2}+ n\log(n) =\\ =\cdots=\\ =2^kT\left(1\right)+n\log \frac{n}{2^{k-1}}+ \cdots +n\log \frac{n}{2}+n\log(n)=\\ =2^...


Only top voted, non community-wiki answers of a minimum length are eligible