34
Yes, there is. Define a context-free expression to be a term generated
by the following grammar:
$$
\begin{array}{lcll}
g & ::= & \epsilon & \mbox{Empty string}\\
& | & c & \mbox{Character $c$ in alphabet $\Sigma$} \\
& | & g \cdot g & \mbox{Concatenation} \\
& | & \bot & \mbox{...
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 ...
25
I'm not quite sure which flavour of "why" you are looking for. One reason for the increase in power when allowing nondeterminism can be seen in the following example:
Let $L$ be the set of palindromes $w\bar{w}$ over some alphabet (of at least two symbols), where $\bar{w}$ is the reverse of $w$. An NPDA for this language can just keep pushing symbols onto ...
23
Unambiguous context-free parsing is in $O(n^2)$ using Earley's algorithm. Whether there exists a parsing algorithm working in linear-time on all the unambiguous context-free grammars is an open problem. One of the most advanced statements of this kind is due to Leo [1991], who showed that a variant of Earley parsing works in linear time for all LRR ...
20
Parsing perl is un-decidable.
http://www.jeffreykegler.com/Home/perl-and-undecidability/perl-and-undecidability-files/TPR3.pdf?attredirects=0
http://www.perlmonks.org/?node_id=663393
20
Two times no.
First, most HPLs are not context free. While they usually have syntax based on a CFG, they also have what people call static semantics (which is also often included in the term syntax). This can include names and types which have to check out for a correct program. For instance,
class A {
String a = "a";
int b = a + d;
}
is a ...
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
I don't believe that Python's grammar is context free. The requirement that lines in the same block of code have the same amount of indentation is not the sort of thing that context free grammars handle well.
More precisely, there appears to be a homomorphism from the language of Python blocks of the form
if condition:
line1
line2
line3
else:...
15
Every unary context-free language is regular.
(e.g. a direct consequence of Parikh's theorem)
If every iterative/pumping pair of a context-free language L is
degenerated, then L is regular, i.e. L is regular if, for all words x,u,y,v,z it satisfies:
$$xu^nyv^nz \in L, \text{for all } n \geq 0 \implies xu^iyv^jz \in L, \text{ for all }i,j \geq 0.$$This was ...
14
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 ...
13
Bodo Manthey and Martin Böhme show that every
C++ Compiler is necessarily Turing complete, that is, it can compute any
partial recursive function at compile time. So it is much worse than
just context-sensitive.
http://wwwhome.math.utwente.nl/~mantheyb/journals/BotEATCS_BoehmeManthey_CompilingCPP.pdf
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
This is essentially the problem of "addition chains", discussed in great detail in many papers and in Knuth's The Art of Computer Programming. In brief: the problem as you have stated it is not known to be NP-hard, but nobody knows an efficient algorithm to find the absolutely minimum. However, there are good algorithms that come reasonably close to the ...
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 ...
7
The language of valid Bencoded values is not context-free—and nor is just the language of Bencoded strings. Let $L$ be the set of valid Bencoded values, and let $L'$ be the intersection of $L$ with the regular language [0-9]*:a*, i.e. the Bencoded strings with just the symbol a. If $L$ were context-free, so would $L'$, but $L'$ does not ...
7
I think that declaration before use of variables and the function polymorphism of the OOP languages are other examples of programming languages specifications that cannot be handled by context free grammars:
int myfun(int a) { ... }
int myfun(int a, int b) { ... }
int myfun(int a, int b, int c, ...) { ... }
...
int I_m_I_cfg = myfun(1,2);
...
I made a ...
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 ...
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=\{...
Only top voted, non community-wiki answers of a minimum length are eligible
