27
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 exists a $c>1$, so that $w_n\ge c^n$ for infinitely many $n$.
This has been shown for instance in:
Roberto Incitti:
"The growth function of context-free ...
19
About Q1:
Both the ambiguity problem (given a CFG, whether it is ambiguous) and the inherent ambiguity problem (given a CFG, whether its language is inherently ambiguous, i.e. whether any equivalent CFG is ambiguous) are undecidable. Here are the original references:
The undecidability of ambiguity was proved by Cantor (1962), Floyd (1962), and Chomsky and ...
18
Perhaps I found some relevant information in:
Jean-Michel Autebert, Jean Berstel, Luc Boasson; Context-Free Languages and Pushdown Automata; Handbook of Formal Languages; 1997, pp 111-174
DPDAs without $\epsilon$-transitions are known as realtime deterministic pushdown automata.
They are less powerful than DPDAs, for example
$L = \{ a^n b^p c a^n \mid ...
15
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 that the complement of the set $T$ of prefixes of the Thue-Morse word is context-free (and actually something more general than that). But the corresponding ...
12
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 true, then $L_{TP}$ is not context-free; otherwise, it's finite.
Edit: Let me give a quick proof sketch that the twin primes conjecture implies that $L_{TP}$ is ...
11
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 of an accepting nondeterministic TM, is the complement of a context-free language. So $|\overline{L}_n|$ can basically be any computable function less than ...
11
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 words of length not $0$ mod $3$ removed.
Let $L' = \{uv : |u| \equiv_3 |v| \equiv_3 0 \land u_{2|u|/3} \neq v_{|v|/3}\}$. Clearly, $L'$ is CFL, since you can ...
10
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
)
allows to show very easily an exponential lower bound for CFGs.
Let $G$ a grammar in Chomsky Normal Form for $L_n$.
For every word $w\in \{0,1\}^n$ there exists at ...
10
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$.
Your first language seems to have density values of only 0 and 1 while the second goes up to 3. So the first is 1-slender, the second is not following the ...
10
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 to check, or (ii) there is some input symbol $a$ that differs from the corresponding symbol $b$ that occurs $|w|$ positions later.
We use the usual trick of ...
9
Regularity is decidable for DCFL, but it is undecidable for general Context-Free Languages.
Regarding DCFL, I have two references (from Hopcroft+Ullman 79):
A regularity test for pushdown machines, R.E. Stearns, Information and Control, 1967 (full text by clicking on the page)
Regularity and Related Problems for Deterministic Pushdown Automata, Leslie G. ...
9
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 definition of pointed monoids (see, e.g., his MFCS'75 paper). Around the 80's, the algebraic object of choice to study CFL's shifted to the Hotz group—Sakarovitch ...
9
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 classical arguments for undecidability of the CFL universality problem make use of inherently ambiguous languages, and thus one needs new ideas to show ...
8
An identical homomorphism characterization of DCFL does not seem to be possible. The following is extracted from Greibach's original paper.
We show that every context-free language can be expressed as $h^{-1}(L_0)$ or $h^{-1}(L_0-\{e\})$ for a homomorphism $h$. The algebraic statement is: the family of context-free languages is a principal AFDL; ... By ...
8
There actually is a hardest DCFL, which is a deterministic version of Greibach's; it was introduced by Sudborough in 78 in On
deterministic
context-free
languages,
multihead
automata,
and
the
power
of
an
auxiliary
pushdown
store—it is however hardest w.r.t log-space reduction. The language $L_0^{(2)}$ referred therein is the set of words over $...
8
The paper
J.-M. Autebert, Une note sur le cylindre des langages déterministes,
Theoretical Computer Science 8 (1979), 395-399
gives a short proof of the following result (credited to Greibach) which seems to answer your question:
there is no deterministic context-free language $L$ such that, for
every deterministic context-free language $C$, there ...
8
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 there is a well-known tradeoff between states and stack symbols. For example, a classic construction turns a grammar like
$S \rightarrow X_1 X_1$
$X_1 \...
7
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 language is inherently ambiguous is a separate one. The undecidability of inherent ambiguity of a CFL was proved by Ginsburg and Ullian (JACM, January 1966). https://dl.acm.org/doi/10.1145/321312.321318
7
This is a great question and it really lies within my interests. I'm glad that you asked it Max.
Let $n$ DFA's with at most $O(n)$ states each be given. It would be nice if there existed a PDA with sub-exponentially many states that accepts the intersection of the DFA's languages. However, I suggest that such a PDA might not always exist.
Consider the ...
7
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,1,+,-,\land,\lor\})$ used to represent CNF formulas is: $S = \{ d^+ (\lor d^+)^*(\land (d^+ (\lor d^+)^*))^* \}$; just note that $S$ grabs all valid CNF ...
7
(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 alphabet of size $k$, we can construct an automaton that accepts a word of length $O(n^{k+c})$.
The basic idea is to just make the stack as large as possible, ...
7
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/LIPIcs.STACS.2020.16
6
Let me second Michael's judgment, this is indeed an interesting
question. Michael's main idea can be combined with a result from the literature, thus providing a similar lower bound with a rigorous proof.
I will refer to bounds on CFG size in terms of the total number of alphabetic symbols in the $n$ regular expressions. Let this number be denoted by $k$. ...
6
I don't think that there can be any non-trivial lower or upper bounds.
For lower bounds, consider the language $L_1 = \{ a^{2^k} \}$ for a fixed $k$. The size of the smallest context-free grammar is logarithmic in the size of $L_1$'s regular expression, whereas the size of the smallest automaton for $L_1$ is linear in the size of $L_1$'s regex. This ...
6
Here is an $AC_0$ reduction from $\rm Majority$ to $Dyck(1)$.
(This implies that $\rm Majority$ is $AC_0$ reducible to $Dyck(k)$ for all $k \geq 1$.)
In order to do it, we construct a poly-size
constant depth circuit whose gates are $AND$, $OR$, $NOT$ and $Dyck(1)$.
Given an instance $x \in \{0,1\}^n$ of $\rm Majority$ do
Compute $y \in \{0,1\}^{2n}$ by ...
6
About the last question, the usual undecidability proof for universality could be adapted.
Recall that in this proof, one considers an instance $\langle \Sigma,\Delta,u,v\rangle$ of Post's correspondence problem, where $\Sigma$ and $\Delta$ are two disjoint alphabets, and $u$ and $v$ are two homomorphisms from $\Sigma^\ast$ to $\Delta^\ast$. Then $$L_u=\{...
6
It's well-known you can present computation history of a Turing machine as an intersection of two CFLs. Take a deterministic Turing machine $M$ and force it to reject everything except possibly the empty word. The set of computation histories is either empty (if $M$ rejects the empty word), or a singleton (if there's an accepting computation for the empty ...
6
A proof that uses closure properties:
DCF languages are not closed under union, so take, $L_1, L_2 \in DCF$ s.t. $L = L_1 \cup L_2 \notin DCF$
Add three new symbols $\{\alpha, \beta, \#\}$ to the original alphabet $\Sigma$ and build the languages:
$L'_1 = \{ \alpha \# w \mid w \in L_1\}$
$L'_2 = \{ \beta \# w \mid w \in L_1\}$
We have $L'_1, L'_2$, but ...
6
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 the language of D.)
It might be worth looking at your example in terms of the Chomsky-Schützenberger theorem. The theorem's statement for the two grammars in ...
6
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 linear set is a set of the form $\vec{v} + P^*$ where $\vec{v} \in \mathbb{N}^k$ and $P$ is a finite set of such vectors ($P^*$ denotes all linear combinations of ...
Only top voted, non community-wiki answers of a minimum length are eligible
