You have to show that you can always construct a finite automaton that accepts strings in $L^R$ given a finite automaton that accepts strings in $L$. Here is a procedure to do that. Reverse all the ...

Pathological data is data that will make the algorithm perform bad. For hash tables, pathological data is data that causes collisions. That of course depends on the hash function being used. For ...

The $^*$ is an operator that takes a language (not only regular languages) $L$ and produces a new language $L^*$ called the Kleene closure of $L$. A language is a set of strings over a finite alphabet ...

The indexing time is always O(1) for an array whether you reallocate or not! Reallocating is not a bad idea if the table size doubles each time the array overflows, insertion takes constant time ...

The only way a finite system (grammar) can generate an infinite set of words is by repeating stuff: you start at $S$ and keep expanding until you hit a non-terminal that you've already expanded. So ...

Tail-recursion is a form of recursion in which the recursive calls are the last instructions in the function (that's where the tail part comes from). Moreover, the recursive call must not be composed ...

The merge subroutine takes two sorted arrays and creates one sorted array out of these two arrays. It does so in linear time. Say the sorted arrays are A = [1 2 3] and B = [2 3 4]. Since these two ...

The computation of a non-deterministic automaton can be modeled by a tree. The input is accepted if there is a root-to-leaf path that eats the input and terminates in an accepting state. When the ...

Hint: find a PDA for the language $\{a^kb^k:k\ge 0\}$ and apply it twice. The other approach is to find a grammar for the language and convert it to an equivalent PDA. Here is the grammar version: $... View answer 5 votes In terms of power, they are equivalent as you said and there is an algorithm (subset construction) for converting an NFA to an equivalent DFA. As you might tell from the algorithm's name, it ... View answer 5 votes If the grammar is ambiguous (at least one sentence has more than one parse tree), then the grammar is not in LL(1). In general, you compute the LL(1) parse table and use it to answer the question. ... View answer 4 votes Such a list can yield more than one graph. Consider 4: 1 2 3, 3: 2 1, 2: 1. One graph is$1\to 2, 2\to3, 3\to4$. A second graph is$1\to 2, 2\to3, 3\to4 , 2\to4$. View answer 4 votes I'll assume that you are computing the average of the elements of an array of fixed size and that you can change the value at some position at any moment. You want a data structure that supports the ... View answer 4 votes A graph is defined abstractly as a set of vertices together with a set of edges connecting those vertices. You have to give the vertices/edges meaning to make sense of the problem. For Sudoku, a ... View answer 4 votes That's fairly easy. Just take a non-terminal X and add the rule$X\to aY$where$a$is the label on the arrow from$X$to$Y$if$X$is not final; if it's final add a rule like:$X\to \epsilon$as ... View answer 4 votes Based on the comments: $$S \to 1S00 \mid 100$$ View answer 4 votes A string of length$2$cannot be equal to a string of length$3$. But a string constructed by concatenation of$2$strings may be equal to a string constructed by concatenating$3$strings. The empty ... View answer 4 votes Think about it this way: every function that does "no worse than n" and "no better than n" is also a function that does "no worse than n". The "no better than n" part is just an additional constraint. ... View answer 3 votes If all edge costs are equal, then any spanning tree is also a minimum spanning tree. In this case, any algorithm that solves REACHABILITY solves MST as well. Let S = {v0} be a set of nodes initially ... View answer 3 votes In theory, an algorithm is said to be efficient if its worst-case running time is bounded by a polynomial in it's input length. The reasoning being that polynomials have nice closure properties. ... View answer 3 votes There are several valid definition of a Turing machine but they (the TM's) are all equivalent in power (they all compute the same functions). You could use the original definition (coined by Alan ... View answer Accepted answer 3 votes Theorem. Let$G = (V, T, P, S)$be a Context-free Grammar. Then$\forall A \in V, A \rightarrow^* \alpha \Leftrightarrow \exists$a parse-tree$T'$rooted at node$A$with yield$\alpha \in (V \cup T)^...
The first loop runs $\log_2N$ times but in nested loops we are interested in the running time of the inner loop (thanks to Tsuyoshi Ito for the clarification). The second loop depends on the value of $... View answer 3 votes You can apply any rule in the set of productions P. The result is called a sentential form. A sentential form belongs to the language recognized by the grammar if it consists of terminal symbols only. ... View answer 2 votes Hint: what is the answer for$n^2-9n+7$? View answer 2 votes In a tree, there is exactly one path between any pair of vertices. When you add edge e1 you close that unique path to form a unique cycle. View answer 2 votes You can use two linked lists. The first one holds the matrix entries and the second one points to the entries that are endpoints of rows. To add a new dimension, scan the second list and insert the ... View answer 2 votes Boils down to knowing the difference between maximal and maximum. maximal is relative whereas maximum is absolute. I guess, maximal flow means maximum flow in a sub-network but I'm not sure. View answer 2 votes Method 1 This is one kind of problem you can write a program to solve instantly. We are counting the number pairs satisfying the conditions you state. First generate the vertices (I'm using Python). ... View answer 2 votes A graph is dense if the number of edges is closer to the maximum number of edges there could be. Formally, a graph is dense if$e=\cal \Omega(v^2)$where$v,e\$ are the number of vertices and edges. A ...