Skip to main content
27 votes
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 ...
Gamow's user avatar
  • 5,782
15 votes

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 ...
Jeffrey Shallit's user avatar
13 votes

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 ...
Michael Burke's user avatar
13 votes

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 ...
Aryeh's user avatar
  • 10.6k
11 votes
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 ...
Michaël Cadilhac's user avatar
11 votes
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 ...
Lance Fortnow's user avatar
11 votes

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 (...
Marzio De Biasi's user avatar
10 votes
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$. ...
Peter Leupold's user avatar
10 votes
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 ...
Lorenzo's user avatar
  • 118
10 votes

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 ...
Jeffrey Shallit's user avatar
9 votes
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 ...
Michaël Cadilhac's user avatar
9 votes

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 ...
Jeffrey Shallit's user avatar
8 votes
Accepted

Is SAT a context-free language?

Just an alternative proof using a mix of well known results. Suppose that: variables are expressed with the regular expression $d = (+|-)1(0|1)^*$ and that the (regular) language (over $\Sigma = \{0,...
Marzio De Biasi's user avatar
8 votes
Accepted

Are endmarkers necessary for Deterministic Pushdown Automata?

Short answer: it depends on how you set the acceptance condition of the DPDA model: final state or empty stack. The endmarkers are not necessary for DPDAs in which the accept condition is final state ...
Marzio De Biasi's user avatar
7 votes

Maximum shortest word accepted by pushdown automata

(Answer inspired by Lamine's comment) We assume the automaton is only allowed to push one symbol per state (otherwise, you could make the stack arbitrarily large with only two states). With a stack ...
Antimony's user avatar
  • 917
7 votes

Lengths of "all-accepted" words in Context Free languages

The shortest word in $A_L$ is not bounded by a recursive function in the size of a given context-free grammar describing $L$. See here for more results in that direction: https://doi.org/10.4230/...
Hermann Gruber's user avatar
6 votes

Known and described subclasses of Context-Free Grammars class

Your two grammars seem very similar. They are both linear grammars in two non-terminals. (Morally one, really -- in both examples the language of S is contained in the language semiring generated by ...
gdmclellan's user avatar
6 votes
Accepted

For which $R$ is $\{0^a10^b10^c\mid R(a,b,c)\}$ context-free?

What you're looking for is an old result of Ginsburg and Spanier actually related to one of the oldest open questions of the field. See Ginsburg's book The Mathematical Theory of CFLs. Defs. A ...
Michaël Cadilhac's user avatar
6 votes

Continuous mathematics and formal language theory

Lamine commented on the connection to the Chomsky-Schützenberger enumeration theorem. Recently, a few research problems in formal language theory were solved using continuous mathematics via this ...
Hermann Gruber's user avatar
6 votes

List of nice non-context-free languages

Two simple examples of non-context-free languages are PRIMES $= \{ a^p \mid p \text{ prime} \}$ and POWERS $= \{ a^{2^n} \mid n\ge 0 \}$. One can prove that they are not context-free by the pumping ...
Noam Zeilberger's user avatar
5 votes

Is SAT a context-free language?

If the number of variables is finite then so is the number of satisfiable conjunctions, so your SAT language is finite (and hence regular). [Edit: this claim assumes the CNFSAT form.] Otherwise, let'...
Aryeh's user avatar
  • 10.6k
5 votes

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

In addition to the references given by Michaël Cadilhac, let me add this paper Berstel, J.; Boasson, L. Towards an algebraic theory of context-free languages. Fund. Inform. 25 (1996), no. 3-4, 217--...
J.-E. Pin's user avatar
  • 4,841
5 votes

Finding a minimal context free grammar that recognizes a finite set of strings of bounded length

The following inapproximability result is known (Theorem 17 in Gruber/Holzer/Wolfsteiner, DLT 2018): Given a context-free grammar of size $s$ generating a finite language $L$, it is impossible to ...
Hermann Gruber's user avatar
5 votes

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

Just a different ("grammar oriented") perspective to prove that the complement of $\{ w^k \}$ is CF for any fixed $k$ using closure properties. First note that in the complement of $\{ w^k \}$ there ...
Marzio De Biasi's user avatar
5 votes

Continuous mathematics and formal language theory

One of the first connections is via generating functions. The Chomsky-Schützenberger theorem states that the generating function of the number of words of a unambiguous CFL is algebraic. In his paper, ...
Lamine's user avatar
  • 1,137
5 votes
Accepted

Maximum shortest word accepted by pushdown automata

Counter Automata I was a co-author for a paper where we investigated this problem for counter automata. We were able to show that the length of a shortest string accepted by an $n$-state (non-empty) ...
Michael Wehar's user avatar
5 votes
Accepted

Generalizations of Dyck languages?

I believe that a type of automata that your are looking for could be "visibly counter automata". It is easy to imagine what they should be - they are just standard automata but equipped with ...
Bartosz Bednarczyk's user avatar
5 votes
Accepted

Does a finite, polynomially-bounded CFG translate into a polynomially-bounded DFA?

The sizes $|Q_n|$ can grow exponentially even in the context of question 1 (and thus questions 2 and 3 as well). For $n = 2 k$ even, define the grammar $G_n$ of size $O(n)$ by $$ \begin{align*} S \to {...
Ilkka Törmä's user avatar
5 votes
Accepted

Words of the form $(a^n b)^n$ in a context-free language

There exists a context-free language $M$, such that $N(M)$ is not semilinear. The construction is a modification of the construction I shared in the comments. Indeed, consider the language $K := \{ a^{...
Kaban-5's user avatar
  • 245
4 votes

Eilenberg's rational hierarchy of nonrational automata & languages -- where is it now?

An accepted answer to this question was given by J.-E. Pin at Mathematics Stack Exchange.

Only top scored, non community-wiki answers of a minimum length are eligible