# Questions tagged [word-combinatorics]

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

37 questions
Filter by
Sorted by
Tagged with
87 views

### Primitive word and cyclic rotations

Definition. A word $w \in \Sigma^*$ is primitive if $w=u^n \rightarrow n=1$. Is it true that a word is primitive if and only if its all cyclic rotations are dstinct?
66 views

133 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 ...
356 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 ...
108 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\}$.)
338 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 ...
91 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 ...
61 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

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