Vimal Patel
• Member for 2 years, 10 months
• Last seen more than a week ago

Here is a simple counter example: $S \rightarrow aSbSaSbS \space |\space \epsilon$ and string $w: abababab.$ In one case we use last $S$ and in other case we use second $S$. All other $S$ goes to $... View answer Accepted answer 5 votes Unfortunately, your conjecture is wrong. For instance$S \rightarrow aSSb | \epsilon$is ambiguous. To see that take$w: aabb$. For this string we have following two distinct derivation tree ... View answer 3 votes Here is one such example of undirected weighted graph. View answer 2 votes Here$L$is DCFL. (a)$f_1(L) = \{u\in\Sigma^*: ua\in L\text{ for some }a\in\Sigma\}$(that is,$f_1(L)$is the set of strings obtained by dropping the last symbol of strings in$L$.) Let's define ... View answer Accepted answer 2 votes Preorder traversal: This traversals always yield unique binary trees. (proof for this remains. To me it seems that it is correct due to procedure to construct tree that follows. However it might not ... View answer 2 votes$L = \{\text{<M, k>| M is a Turing Machine and } |w \in L(M) : w \in a^*b^*| \geq k \}$Now we want to find whether$L$is$RE$or not. Yes, indeed your interpretation of language$L$is ... View answer Accepted answer 2 votes Original Question:$L_1 = \{w \in \{0|1\}^* | \text{ w is a sequence of one or more 1's } \}L_2 = \{\langle M \rangle | \text{ Turing machine } M \text{ decides } L \}$prove that$L_2$is ... View answer 2 votes Our grammar$G$has following two production where$S$is start symbol.$S\rightarrow aTbS \vert\epsilonT\rightarrow aTb|\epsilon$Now to convert it to chomsky normal form (CNF) we have to ... View answer 1 votes Timestamp ordering ensures conflict serializability proof : Assume that in precedence graph of schedule, we have edge$T_i \rightarrow T_j$. Now, When$T_j$puts it's request for this conflicting ... View answer Accepted answer 1 votes$S_1:$If relation R is in 3NF and every key is simple, then R is in BCNF.$S_2:$If relation R is in 3NF and R has only one key, then R is in BCNF Both statements are correct. Your counterexample is ... View answer 1 votes Actually this language is not a CFL. And here is a proof: Let's take string$w: a^mb^{2^m}$where$m$is constant guaranteed by pumping lemma for CFLs. Then$a^{m+k_1}b^{2^m+k_2} \in L$where$1\le ...

Why don't we just use DFS to find shortest path in DAG? For this try to find shortest path from source vertex $0$ to all vertex in following graph. In particular if DFS visits $1$ first from $0$ ...

Actually any BST can be transformed into balanced BST using $\mathcal{O}(n)$ rotations. High level explanation: We convert given BST to right going chain(see fig-1 below). Then we convert that chain ...

If we draw recurrence tree for this relation than it would be something like following: T(n) -> Cost: n / | \ T(n/2) T(n/3) T(n/6) -> total cost: n/2 + n/3 + ...

This answer is compilation of above comments but this include reasoning why this algorithm works. 1. find(A, val) 2. start = 1 3. end = A.length 4. minn = (start,end) //minn ...

Bigoh notation $O$: This is anlogous to $\le$. $f(n) = O(g(n))$ means that for large enough value of $n$ value of $f(n)$ will be within some constant factor of value of $g(n).$ Smalloh notation $o$: ...
Above answers are excellently written. But one other approach would be helpful I think. We want to prove that if $L(A)$ is a $CFL$ and $L(B)$ is a regular then $L(A/B) = \{w\space|\space wx \in A,\... View answer 0 votes Ok this is not a good way to do it but here is my approach. So, here it suffices to prove$\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$. That will imply$f(n) = o(g(n))$proof of$\lim_{n\to\infty} \...