Questions tagged [word-combinatorics]

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

Filter by
Sorted by
Tagged with
15
votes
2answers
2k views

Number of words of a given length in a regular language

Is there an algebraic characterization of the number of words of a given length in a regular language? Wikipedia states a result somewhat imprecisely: For any regular language $L$ there exist ...
21
votes
1answer
490 views

Does every large enough string have repeats?

Let $\Sigma$ be some finite set of characters of fixed size. Let $\alpha$ be some string over $\Sigma$. We say that a nonempty substring $\beta$ of $\alpha$ is a repeat if $\beta = \gamma \gamma$ for ...
17
votes
3answers
845 views

Number of words in the regular language $(00)^*$

According to Wikipedia, for any regular language $L$ there exist constants $\lambda_1,\ldots,\lambda_k$ and polynomials $p_1(x),\ldots,p_k(x)$ such that for every $n$ the number $s_L(n)$ of words of ...
7
votes
2answers
599 views

How many strings are close to a given set of strings?

This question has been prompted by Efficient data structures for building a fast spell checker. Given two strings $u,v$, we say they are $k$-close if their Damerau–Levenshtein distance¹ is small, i.e. ...
7
votes
3answers
126 views

What is language density used for?

If we have a langage $L$ over an alphabet $\Sigma$, then we can defined the density function of $L$ as : $$ p_L(n) = | L \cap \Sigma^n | $$ I am wondering why it’s useful to study this function ...
-1
votes
0answers
246 views

Prove $y'w'v'u'x' = xuvwy$ [duplicate]

This question repeats one that was closed. Let $x, u, v, w, y, x', u', v', w', y'$ be words satisfying $y'x' = xy$. $y'u'x' = xuy$. $y'v'x' = xvy$. $y'w'x' = xwy$. $y'v'u'x' = xuvy$. $y'w'v'x' = ...
-3
votes
1answer
325 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?