2022 Developer Survey is open! Take survey.

# Tag Info

Accepted

### What is the state complexity of the copy language?

The technique described by Yuval: Do there exists polynomial size CFG that describe this finite language? ( you may also read: Lower bounds on the size of CFGs for specific finite languages ) ...
• 1,085
Accepted

### Known and described subclasses of Context-Free Grammars class

Density might be interesting concept for you. The density function is defined as $$\delta_L(n) := |L\cap \Sigma^n|,$$ where $\Sigma^n$ denotes the set of all strings of length $n$ over $\Sigma$. ...
Of course $k \geq 2$ here. There once was a manuscript by Horváth that claimed to solve the problem, but it was unclear in several places and to my knowledge was never published. As far as I know, ...