Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now
15

No, unfortunately not. There are even infinite square-free words if your alphabet has at least three symbols. This apparently natural border (two-element alphabets have only finitely many square-free words) is observed in many places, for instance: $\{xyyz \mid x,y,z\in \Sigma^+\}$ is co-finite for $|\Sigma|\leq 2$ but not context-free for $\Sigma>2$. ...


14

For your language, can you take $p_0(x) = 1/2$, $\lambda_0 = 1$, $p_1(x) = 1/2$, $\lambda_1 = -1$, and $p_i(x) = \lambda_i = 0$ for $i > 1$? The Wikipedia article doesn't say anything about the coefficients being either positive or integral. The sum for my choices is $\qquad \displaystyle 1/2 + 1/2(-1)^n = 1/2 (1 + (-1)^n)$ which seems to be 1 for ...


11

@Patrick87 gives a great answer for your specific case, I thought I would give a tip of how to find $s_L(n)$ in the more general case of any language $L$ that can be represented by an irreducible DFA (i.e. if it is possible to get to any state from any state). Note that your language is of this type. Proof of theorem for irreducible DFAs Let $D$ be the ...


10

Given a regular language $L$, consider some DFA accepting $L$, let $A$ be its transfer matrix ($A_{ij}$ is the number of edges leading from state $i$ to state $j$), let $x$ be the characteristic vector of the initial state, and let $y$ be the characteristic vector of the accepting states. Then $$ s_L(n) = x^T A^n y. $$ Jordan's theorem states that over the ...


8

Let $L \subseteq \Sigma^*$ a regular language and $\qquad \displaystyle L(z) = \sum\limits_{n \geq 0} |L_n|z^n$ its generating function, where $L_n = L \cap \Sigma^n$ and so $|L_n|=s_L(n)$. It is known that $L(z)$ is rational, i.e. $\qquad \displaystyle \frac{P(z)}{Q(z)}$ with $P,Q$ polynomials; this is easiest seen by translating a right-linear grammar ...


6

Continuing Artem's answer, here is a proof of the general representation. As Artem shows, there is an integer matrix $A$ and two vectors $x,y$ such that $$ s_L(n) = x^T A^n y. $$ (The vector $x$ is the characteristic vector of the start state, the vector $y$ is the characteristic vector of all accepting state, and $A_{ij}$ is equal to the number of ...


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

The total number of (different) permutations of strings with $n_i$ characters of type $i$ is given by $$\frac{(\sum_i n_i)!}{\prod_i n_i!}.$$ In other words, if the length of the string is $n=n_1 + n_2 +...$, you have $\frac{n!}{n_1!n_2!n_3!\ldots}$ different permutations. Note that the formula fits your simple case. Why is this formula correct? Because $n!...


5

Okay. I think I may have figured it out myself. I invite everyone to check my answer to see if it makes sense. So the first bracket must be a left bracket and there must be some right bracket later on that corresponds to this first bracket. Inside these two brackets there is a valid bracket expression $A$ with depth at most $l-1$ and outside these two ...


5

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


4

The borderless words are also known as unbordered or bifix-free ("A note on bifix-free sequences", PT Nielsen, in a paper as early as 1973). The language of unbordered words is not even context-free, see the paper "Inverse star, borders, and palstars" by Ramparsad etal, in TCS with a preprint on ArXiv. The technique to obtain this result is Ogden's Lemma, ...


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


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


3

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

$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(n)$ ...


2

Turns out this is not an easy problem, but it has been solved. A similar case is treated in Bounded discrete walks by Banderier and Nicodème (2010) and they refer to the exact result you need in Combinatoire analytique des chemins et des cartes¹ by Banderier (2001). This is a preliminary version. You can obtain a copy of the final version by contacting the ...


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

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

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

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

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

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


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

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


Only top voted, non community-wiki answers of a minimum length are eligible