# Tag Info

The number of words of given length in a language is a very natural parameter. Here are some examples to pique your interest: The density of $(1+01)^*$ is the Fibonacci sequence. The density of a regular unary language is eventually periodic. The density of a regular language is of the form $\Theta(n^k \lambda^n)$ for some integer $k \geq 0$ and real $\... 6 This word problem over groupoid is a nice example to show the essence of dynamic programming, the recognition of the subproblems. In other words, how can we define the table or the multi-dimensional array that we should fill? In general, the subproblems should represent the computations that will be repeated many times in a brute-force algorithm. The ... 5 Yes, this is true. The direct implication ($\Rightarrow) is the hardest to prove, and you will need the following lemma: two words commute if and only if they are powers of the same word (R.C. Lyndon and M.P. Schützenberger, The equation a M = bncp in a free group, Michigan Math. J. 9 (1962) 289-298. Or in this: H. Petersen, On the language of primitive ... 4 Count instead $$(a+b)^{n+m} - M_{m,n} = \sum_{i+j < m} a^i b (a+b)^{n+m-2-i-j} b a^j.$$ This leads to \begin{align*} |M_{m,n}| &= 2^{n+m} - \sum_{i+j<m} 2^{n+m-2-i-j} \\ &= 2^{n+m} - \sum_{k=0}^{m-1} (k+1) 2^{n+m-2-k} \\ &= 2^{n+m} - 2^{n+m-2} (4-2^{-(m-2)}-m2^{-(m-1)}) \\ &= 2^{n+m} (1 - 1 + 2^{-m} + m2^{-m-1}) \\ &= (m+2) 2^{... 4 E_L(n) describes how many bits of information you get from a string of length n, assuming it belongs to the language. For many languages the function would be a rather smooth function in n. There are of course languages where the language only contains strings of even length, for example, in which case E_L(n) isn't even defined for odd n. E_L(... 4 Density is what you get when you want a measure for the size of infinite languages. We can't quantify that by just taking their number of elements, which is the same for all infinite languages: (enumerable) infinity. Still, we have an intuition about the relative sizes of infinite languages. For instance, about the language of all even strings over a given ... 3 Well, take a moment to reflect. Is a word or a string one of the most important and most common entities in this world? What are the most basic properties of a word or string? its alphabet its length its sound its meaning its syntax or grammar its origin its usage as how to form sentences. hmm, does it repeat part of itself? Or never (square-free)? It ... 3 Under related concepts on the wiki page for square-free we find the notion of cube-free words. An example of such words is the (Prouhet-)Thue-Morse sequence. Which has a very real-life application. The sequence has been discovered independently many times, not always by professional research mathematicians; for example, Max Euwe, a chess grandmaster, who ... 3 One direction is easy: if xy = yx then x^2y^2 = xxyy = xyxy = (xy)^2. In the other direction, we split into cases. If |x|=|y| then, as you mention, x = y. If |x|<|y| then let y=y_1y_2, where |y_1|=|y|-|x| and |y_2|=|x|. We have z = x^2y_1 and z = y_2y = y_2y_1y_2. Since |x| = |y_2|, it follows that x = y_2. Substituting this, we ... 3 Assume you have the alphabet \{A,B,C\} and you want to form words of length 4. For the first letter you have 3 choices, A, B or C. For the second letter you have again 3 choices, A,B or C and so on. In total: 3 \cdot 3 \cdot 3 \cdot 3 = 3 ^ 4 = 81 possibilities. 3 This is yet another example of enumerative encoding. Suppose that x has \alpha_i symbols of type i. The size of S is then the multinomial coefficient \binom{n}{\alpha_1,\ldots,\alpha_M}. Pascal's identity reads \binom{n}{\alpha_1,\ldots,\alpha_M} = \sum_{i\colon \alpha_i \neq 0} \binom{n-1}{\alpha_1,\ldots,\alpha_i-1,\ldots,\alpha_M}. $$In the ... 3 Work an example. I worked through the Scheme version with the input 35 (and with the denominations of the coins as 1, 5, 10, 25, 50) and I'm seeing a ton of repetition in the search tree. (cc 5 1) has already come up 3 times and I'm only about half way through. Also, memoization actually does a little more than lazy evaluation. Lazy evaluation caches the ... 2 The star operator is a unary operator known as Kleene star (or Kleene closure) and the result of its application on \Sigma (an arbitrary set of strings) is another set that contains all possible finite strings constructed using only strings from \Sigma. Assuming that the set contains at least one non-empty string, the cardinality of the set produced by ... 2 For each particular c,N,M, this can be solved explicitly by constructing a DFA accepting the language. The general case may also be approached heuristically, though the dependency structure makes heuristic estimates harder to make. The case N = 1 can be solved explicitly. Suppose that the alphabet is \{0,\ldots,c-1\}. Represent each word w_1\ldots ... 2 The answer depends on |\Sigma|. If \Sigma contains a single letter then L = (\Sigma\Sigma)^*(\Sigma\Sigma)^* can be written as a concatenation of two nontrivial languages. Conversely, suppose that |\Sigma| > 1, say a,b \in \Sigma. Since \epsilon \in L, necessarily \epsilon \in L_1,L_2. This implies that all words in L_1,L_2 are squares, ... 2 Does not "with up to 4 letters" mean that we should count 1-letter, 2-letter, 3-letter, and 4-letter words? Then the answer is 3 + 3^2 + 3^3 + 3^4. 2 From xy = yx, we can say x^2y^2 = x (xy) y = x (yx) y = (xy)^2, Hence z = xy. Hence, first part is proved. Now, suppose there exists a word z such that x^2 y^2 = z^2. Moreover, suppose |x| < |y| w.l.o.g. Hence there is a w such that x^2w = w'y, ww'=y, |w| = |y|-|x|, and |w'| = |x|. As x^2w = w'y and |w'|=|x|, we can say w' = x.... 2 That's an inaccuracy. If \delta < 1/2 is constant then it is the case that \sum_{k=0}^{\delta m} \binom{m}{k} = O\left(\binom{m}{\delta m}\right), since the binomial coefficients increase very fast until they finally level out around the central binomial coefficient. The hidden constant depends on \delta. (When \delta is close to 1/2 this doesn'... 2 When there are more than one type of parentheses (say [] and ()), the problem is NP-complete. The proof is the same as the proof for the palindrome problem except that in the reduction, 0s and 1s in w are changed to [s and (s respectively, 0s in v_i are changed to ]s and 1s in r_k are changed to )s. When there are only one type of parentheses (say ()),... 2 I think the book is right. In your example, the word u=abcd satisfies the conditions: it is not a prefix of a word in a^* b^* c^*. In general, I think that proof is valid. I'll try to explain why the minimality of n proves the existence of such a word u \in L. If there did not exist such a word u \in L, then that would mean that every word u \... 2 There is a simple upper bound of$$\frac{\binom{n}{2}}{k-1},$$following from the fact that there are \binom{n}{2} ordered pairs of elements, and each ordered word contains k-1 of them. There is an almost matching lower bound of$$ \frac{\binom{n-k+1}{2}}{k-1}. $$This shows that for fixed k, the answer is asymptotically$$ \frac{n^2}{2(k-1)} \pm O(n).... 1 If there is just one symbol which can appear on the tape, then nothing about the tape can ever change. Thus, the tape is absolutely useless, and you are left with a finite bidirectional automaton. However, the blank symbol\bot$is often treated as a special case. We could thus consider the situation where each cell on the tape can carry either$0$or$\bot$... 1 Your algorithm is not correct. Here is a counterexample:$D$contains the words$aa,bb,ac,bc$;$v=aa$; and$w=bb$. A transformation is possible$(aa \to ac \to bc \to bb)$but your algorithm won't find it. 1 No, there's no faster way to calculate all the "factors" (substrings) of$w$. It takes$\Theta(|w|^2)$space even to write down the list of all factors. Any algorithm has to spend at least 1 unit of time per character of output. So, any algorithm will have to take$\Omega(|w|^2)$time; you can't do better than$O(|w|^2)$time. If you want to look for a ... 1 (1) Indeed. Every regular [=rational] language is the morphic image of a local [=2-testable] language. This is seen as follows. A finite state automaton can be "encoded" by a 2-testable language by using the transitions as letters. So we consider symbols$(p,a,q)$. The corresponding language is 2-testable: basically test whether the transitions are ... 1 If I'm not misunderstanding you, I think the minimum cost factorization can be calculated in$O(n^2)$time as follows. For each index i, we will calculate a bunch of values$(p_i^\ell, r_i^\ell)$for$\ell=1,2,\ldots$as follows. Let$p_i^1\ge 1$be the smallest integer such that there is an integer$r\ge 2$satisfying $$S[i-rp_i^1+1, i-p_i^1] = S[i-(r-1)... 1 Here are all words in L^* of length at most 9:$$ \epsilon, \\ pi, po, \\ pipi, pipo, popi, popo, \\ pipipi, pipipo, pipopi, pipopo, popipi, popipo, popopi, popopo, \\ pipipipi, pipipipo, pipipopi, pipipopo, pipopipi, pipopipo, pipopopi, pipopopo, popipipi, popipipo, popipopi, popipopo, popopipi, popopipo, popopopi, popopopo. $$In total, there are 31 ... 1 You want to enumerate first by sum, then by lexicographic order of some sort (it's impossible to tell which type exactly from your example). Replacing actual elements with indices, here is the order you're interested in for A \times B:$$ (0,0) \\ (1,0), (0,1) \\ (2,0), (1,1), (0,2) \\ \ldots$$It's a simple exercise to generate this order for$A \times B$... 1 The correct answer can be rewritten as$\frac{n(n-1)}{2} + n + 1$. Let's call the two remaining attributes$A_k$and$A_l$. You are counting each combination of$nC_{n-2}$candidate keys four times: (1) when they are alone, (2) when they are with$A_k$, (3) when they are with$A_l$, (4) when they are with both$A_k$and$A_l\$. Your formula then boils down ...