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 ...
- 5,712
18
votes
Accepted
Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?
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 ...
- 22.3k
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 ...
- 6,898
12
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 ...
- 10k
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 ...
- 8,546
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 ...
- 3,816
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$.
...
- 452
10
votes
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
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 ...
- 6,898
9
votes
Deciding whether a context-free language is regular
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, ...
- 1,502
9
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 language is inherently ambiguous is a ...
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 ...
- 3,816
9
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 ...
- 108
8
votes
Does there exist a hardest DCFL?
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) ...
- 4,721
8
votes
Does there exist a hardest DCFL?
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
...
- 3,816
8
votes
Does there exist a hardest DCFL?
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 ...
8
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 ...
- 6,898
7
votes
Complexity of intersection of regular languages as context-free grammars
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 ...
- 4,900
7
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,...
- 22.3k
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 ...
- 907
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/...
- 5,424
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 ...
- 406
6
votes
Accepted
Are deterministic context-free languages closed under outfix (or other erasing operations)
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 ...
- 22.3k
6
votes
Complexity of intersection of regular languages as context-free grammars
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 ...
- 5,424
6
votes
Complexity of intersection of regular languages as context-free grammars
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 ...
- 421
6
votes
Reference for Dyck languages being $\mathsf{TC}_0$-complete
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
...
- 1,887
6
votes
Accepted
is determining an unknown CFL from intersection of two CFLs decidable?
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 ...
- 1,251
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 ...
- 3,816
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 ...
- 5,424
6
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 ...
- 22.3k
Only top scored, non community-wiki answers of a minimum length are eligible