$L = \{a^{2^k}, k \in \mathbb{N}\}$ is not a context-free language according to Pumping lemma for context-free languages. Suppose $L$ is context-free. The pumping lemma says there exists some integer ...

First, your $L1L2$ is wrong. $$L1L2 = \{a^ib^ic^j\ | \ i>0, j>0\}$$ Your conclusion is right, $L1L2$ is irregular(as long as $L2\neq\phi$, otherwise $L1L2=\phi$ is clearly regular). This can be ...

Trip represents a sequence of stops plus associated arrival and departure times on each stop. Group all trips by their sequence of stops, ignoring the time information, then each group of trips ...

For BIT and its variants, I recommend this article: http://coutcode.com/blog/binaryindexedtree/ The core of BIT is point update - range query, ie. for array $A[1 \dotsc n]$, BIT supports following ...

After recoloring in (b), the following rule is still violated: children of a red node are black. Recoloring while preserving black height in step (b) introduces new double red nodes 2 and 7, which ...

Hopcroft's algorithm works well on complete DFA. (ie. for $M=\{Q,\Sigma,\delta,q_0,F\}$, the transition function $\delta:Q\times\Sigma\to Q$ is a total function). For incomplete DFA with partial ...

Just replace Kleene stars with $\epsilon$ to find the basis and position, then extend to both direction. $B=\{\epsilon\}$ $\mathcal{F}=\{X\to0X|10X|X1\}$ $L_1 = \langle B \rangle_{\mathcal{F}}$

You are in the right track. But the algorithm is incomplete. You missed the case inserting element on the left sub tree and back. Here is the modified algorithm: (Changes marked in bold) Let $n$ ...

No error. in fact, if you add the binary representation of (-38) and 38 as unsigned 7-bit integer without overflowing, you'll get $10000000_2$, then due to overflow the lowest 7 bits is preserved, ...

One possible grammar is: $G = (N, \Sigma, P, S)$, where $N = \{S,U,V\}$ $\Sigma = \{a,b,c\}$ $P = \{ S \to baUV, U \to ab|bUc, V \to a|aV \}$ The key observation here is breaking $bab^nabc^... View answer 2 votes Assume the maximum matching problem is$U-V$matching, and$S\subset U$. Find maximum$S-V$matching. If the result equals$|S|$, then it is a feasible matching in original$U-V$matching problem. ... View answer 2 votes By "in linear time I can find that pair" I assume you are using two-pointer technique, that using 2 pointers to traversal the array, trying to reduce the gap to the target by advancing one of the ... View answer Accepted answer 2 votes Using Heavy path decomposition. The key idea is to partition all edges into heavy edges and light edges. Consider tree edge from parent node X to child node Y: heavy edge: size of sub tree Y is at ... View answer 1 votes You are close. Also remember the order of non-tree edges does not matter. There are actually 2 cases for node 1: $$1 \to 2 \to 4 \to \dotsb$$ Start from node 4, it's just a DFS traversal of ladder ... View answer 1 votes GPDA$\to$PDA Approach See you have got a solution from chat. But the first thing popped my mind is a Generalized_pushdown_automaton(GPDA), which can be constructed pretty straight forward. GPDA ... View answer 1 votes Hints: each bit of xor result depends on all bits on that position only. So each bit can be processed independently, while ignoring the unchanged constraint. process bits from MSB to LSB, the higher ... View answer 1 votes Maintaining one AVL tree for the whole process is enough, and more efficient. Setup another AVL tree T, initially empty. Perform DFS on original AVL tree Insert node to T on entering the node, ... View answer 0 votes It is just Left Recursion Removal. The algorithms removing recursion for direct and indirect case are presented on the wiki page. The case in your notes are direct recursion, in general form.$A\to A\...
Hint 1. try build some automaton (Turing machine, etc.) that accept strings of given pattern, then encode both states and transitions in the grammar. Hint 2. try some scanning process to generate $\{... View answer 0 votes In BIT query, the trick is removing the last 1 bit. In BIT update is adding the last 1 bit. Write out node n in binary. Set the counter to 0. Repeat the following while n <= N (the largest value ... View answer Accepted answer 0 votes Noting that every increment starts from the lowest significant bit (LSB). Consider each increment operation this way: starting from LSB, move towards MSB, flipping 1's to 0's until a 0 is encountered. ... View answer 0 votes Assume input$x \ge 1$, and$x$is an integer. Loop invariant:$j*2^i \le x < (j+1)*2^i$, or$[x/2^i]=j$Proof: Initial:$i=0, j=x, x=j*2^i$Inducing: Suppose after$k_{th}$loop, we have$j*2^i ...