Tag Info

Accepted

Number of words of length n in a context-free language

Every context-free language has either polynomial growth or exponential growth. In the notation of the question poser: Either there is a polynomial $p$ so that $w_n\le p(n)$ for all $n$ Or there ...
• 5,782

Languages that we cannot (dis)prove to be Context-Free

Another good one is the complement of the set $S$ of contiguous subwords (aka "factors") of the Thue-Morse sequence ${\bf t} = 0110100110010110 \cdots$. To give some context, Jean Berstel proved ...
• 6,985

How is proving a context free language to be ambiguous undecidable?

The answer by apolge presents the proof that it is undecidable whether an arbitrary context free grammar is ambiguous. The question of whether a context free grammar defines an inherently ambiguous ...

Languages that we cannot (dis)prove to be Context-Free

How about the language $L_{TP}$ of twin primes? I.e., all pairs of natural numbers $(p,p')$ (represented, say, in unary), such that $p,p'$ are both prime and $p'=p+2$? If twin primes conjecture is ...
• 10.6k
Accepted

Is the complement of { www | … } context-free?

Still CFL I believe, with an adaptation of the classical proof. Here's a sketch. Consider $L = \{xyz : |x|=|y|=|z| \land (x \neq y \lor y \neq z)\}$, which is the complement of $\{www\}$, with the ...
• 3,956
Accepted

Size of complement of context-free language

From the proof that determining if a CFL ${L}$ = $\Sigma^*$ is undecidable, the set of strings $ID_0\#ID_1^R\#ID_2\#ID_3^R\#\ldots\#ID_t$ where $ID_0,ID_1,\ldots,ID_t$ is a list of the configurations ...
• 8,711

List of nice non-context-free languages

If I had to summarize the capabilities/limitations of CF languages I would say: they can pair "things" but two distinct pairings cannot overlap they can "count" but only linearly (...
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$. ...
Accepted

Is equivalence of unambiguous context-free languages decidable?

This is currently an open problem. As correctly pointed out, if it is decidable, then one expects the proof to be hard since it generalises the famous DPDA equivalence problem. On the other hand, the ...
• 118

Is the complement of { www | … } context-free?

Here is the way I think about solving this problem, with a PDA. In my opinion, it's intuitively clearer. A word $x$ is not of the form $www$ iff either (i) $|x| \not\equiv 0$ (mod 3), which is easy ...
• 6,985
Accepted

A reference for a "more algebraic" approach to pushdown automata and CFLs?

Sakarovitch's PhD thesis from 1976, titled Monoïdes syntactiques et languages algébriques (syntactic monoids and algebraic languages), revolves around this topic. At the time, this led to the ...
• 3,956

Maximum shortest word accepted by pushdown automata

The precise answer depends on your model of PDA (models differ among different authors; compare Sipser to Hopcroft &Ullman). And number of states alone is not a good measure for PDA's, because ...
• 6,985