Vimal Patel
  • Member for 2 years, 10 months
  • Last seen more than a week ago
  • Vadodara, Gujarat, India
Are these special (one production) Context-Free Grammars always unambiguous?
9 votes

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
Are Context-Free Grammars with only one Production Rule always Unambiguous?
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
Is there an example of when DFS will not return the min. spanning tree?
3 votes

Here is one such example of undirected weighted graph.

View answer
How to determine if a language is deterministic context-free language?
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
Which Tree traversal String is unique?
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
Is this language Recursively Enumerable or Not RE?
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
Reducing the halting problem for a language with strings that include at least one 1
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
Converting S->aTbS|epsilon T->aTb|epsilon to chomsky normal form
2 votes

Our grammar $G$ has following two production where $S$ is start symbol. $S\rightarrow aTbS \vert\epsilon$ $T\rightarrow aTb|\epsilon$ Now to convert it to chomsky normal form (CNF) we have to ...

View answer
Thomas write rula andview serializability
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
Third Normal Form and Boyce Code normal form
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
Can a Non-Deterministic Pushdown Automaton recognize $ \# a^nb^{2^n} \# $ which a TM can?
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 ...

View answer
Does DFS in an unweighted DAG find the shortest path for each vertex from a source?
1 votes

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$ ...

View answer
question about the construction of BSTs using a repeated sequence of rotations
1 votes

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 ...

View answer
Time complexity described by recurrence relation
Accepted answer
1 votes

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 + ...

View answer
Find two numbers in sorted array whose product is close to N
Accepted answer
1 votes

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 ...

View answer
What is the difference between Big(O) and small(o) notations in asymptotic analysis?
1 votes

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$: ...

View answer
Closure of CFL against right-quotient with regular languages
1 votes

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
Question about growth rates of functions involving n and logn
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} \...

View answer