New answers tagged

12

You have mistake in $(2.1)^n \cdot n^2<2^n \cdot n^3$, because it is equivalent $\left(\frac{2.1}{2}\right)^n<n$


1

Your language is regular and can be rewritten as $$ L = {0\Sigma^*1} $$ (start with 0 end with 1)


2

Your solution depends on $n$. In this case the $n$ in the formulation of the language is not a constant, but a variable ranging over the positive integers $n\ge 1$. So we need strings of the form $0^n x 1^n$ for any $n\ge 1$, and any $x\in\Sigma^*$. In general that would not be possible with a FSA, it cannot count and compare the numbers of $0$'s and $1$'s, ...


4

Your language consists of all words starting with $0$ and ending with $1$.


1

To write the profit as a mathematical expression, you need to set up a little more notation for the buys and sells. Let $x[1], \ldots, x[n]$ be the stock prices on days $1, \ldots, n$. For each buy and sell, let $b$ denote the day on which the stock is bought, and $s$ the day on which it is sold. The problem says that we must have $1 \leq b < s \leq n$. ...


1

To compute $\exp(1)$ it does $0$ multiplications, since it enters the if and returns 2. Assume that, for all $k<n$, to compute $\exp(k)$ it does no more than $2\log_2(k)$ multiplications. To compute $\exp(n)$ we have two cases. Either $n$ is even and the number of multiplication is $1$ more than the number done for $\exp(n/2)$, or $n$ is odd and the ...


Top 50 recent answers are included