We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [word-combinatorics]

Questions about combinatorics on languages of words, that is how many sequences of symbols with certain properties there are.

36 questions
Filter by
Sorted by
Tagged with
51 views

117 views

### Proving that $xy=yx$ iff $x^2y^2=z^2$

I was given the following problem as homework: Let $x$, $y$ be words over an alphabet $Σ$. Prove that $xy = yx$ iff there exists a word $z$ such that $x^2y^2 = z^2$. I was hinted that I am ...
327 views

### Ordered Cartesian Product

Say I have three sets: A = [banana, apple, grape] B = [1, 2, 3, 4] C = [Alice, Bob, Carol] I need to design an algorithm that gives me the Cartesian Product A ...
105 views

### Expressing the language of squares as a concatenation of two languages

Can the language $L = \{ vv : v \in \Sigma^* \}$ be expressed as the concatenation of two nontrivial languages? (A language is nontrivial if it differs from $\{\epsilon\}$.)
195 views

### Given the alphabet $\{a, b, c\}$, how many words can we form with 4 letters?

Question: Given the alphabet $\{a, b, c\}$, how many words can we form with 4 letters? And how many words can we form with up to 4 letters? I was thinking about the logic behind this and came up with ...
90 views

### Given a permutation of n integers, how fast can a corresponding Standard Young's Tableau be created?

The Schensted insertion algorithm has an $O(n^2)$ running time, for constructing such a standard Young's Tableaux. But, since every permutation has a unique Young's tableau, there seems no reason as ...
60 views

70 views

### How should i guide a program to perform correct things? [closed]

I want to make a small model of A.I. which can learn itself. I am inspired by 1000+ monkey theorem which states that if 1000+ monkey bangs a keyboard for enough long, then they will eventually produce ...
80 views

193 views

### Is the set of all strings over a finite alphabet finite? [closed]

Suppose $Σ=\{0,1\}$; then $Σ^*$ is the set of all strings over $Σ$. Is $Σ^*$ over $Σ$ finte?
Let us fix an alphabet $\Sigma$ of size $c$, then we have the finite language $\Sigma^n$ which is the set of all $n$ length words. For each $N,M$ how many words are there in $\Sigma^n$ such that no ...