Questions tagged [context-free]
Context-free languages and grammars.
15
questions
9
votes
1
answer
831
views
Do there exists polynomial size CFG that describe this finite language?
Do there exists permutations $\pi_1,\pi_2$ and polynomial size (in $|w|=n$) context free grammar that describe the finite language $\{w \pi_1(w) \pi_2(w)\}$ over alphabet $\{0,1\}$?
UPDATE: For one ...
- 223
16
votes
1
answer
482
views
Lower bounds on the size of CFGs for specific finite languages
Consider the following natural question: Given a finite language $L$, what is the smallest context-free grammar generating $L$?
We can make the question more interesting by specifying a sequence of ...
- 14.5k
21
votes
1
answer
2k
views
Number of words of length n in a context-free language
Denote by $w_n$ the number of words of length $n$ in a (possibly ambiguous) context-free language.
What is known about $w_n$?
I'm sure this has been studied a lot, but I couldn't find anything at ...
- 14k
12
votes
3
answers
498
views
Is the complement of { www | … } context-free?
It is well-known that the complement of $\{ ww \mid w\in \Sigma^*\}$ is context-free. But what about the complement of $\{ www \mid w\in \Sigma^*\}$?
- 14k
32
votes
1
answer
893
views
Eilenberg's rational hierarchy of nonrational automata & languages -- where is it now?
In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised Volumes C and D dealing with "a hierarchy (called the rational ...
- 771
25
votes
3
answers
14k
views
How is proving a context free language to be ambiguous undecidable?
I've read somewhere that a Turing machine cannot compute this and it's therefore undecidable but why? Why is it computationally impossible for a machine to generate the parse tree's and make a ...
- 379
17
votes
1
answer
2k
views
Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?
In the formal description of Deterministic Pushdown Automata, they allow $\epsilon$ moves, where the machine can pop or push symbols onto the stack without reading a symbol from the input. If these $\...
- 1,132
13
votes
1
answer
309
views
Is { ww' | HamDist(w,w')>1 } context-free?
After reading the recent question "Is the complement of $\{ www \mid ...\}$ context-free?"; I remembered a similar problem I wasn't able to disprove:
Is $L = \{ ww' \mid w,w' \in \{0,1\}^* \land |w|...
- 23k
12
votes
3
answers
477
views
Does there exist a hardest DCFL?
Greibach famously defined a language $H$, the so-called nondeterministic version of $D_2$, such that any CFL is an inverse morphic image of $H$. Does there exist a similar statement with DCFL, ...
- 3,946
11
votes
3
answers
1k
views
Maximum shortest word accepted by pushdown automata
Given a fixed alphabet, consider all deterministic pushdown automata with $n$ states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic ...
- 917
9
votes
0
answers
371
views
Deciding if a language induced by a Presburger formula is context-free
Is the following problem decidable?
Given $n$ and a Presburger arithmetic formula $\phi(x_1,x_2,\dots,x_n)$, determine whether the language $\{a_1^{i_1} \dots a_n^{i_n}:\phi(i_1,i_2,\dots,i_n)\}$ ...
- 1,291
6
votes
1
answer
787
views
What is known about $CFL \cap coCFL$?
CFL is the class of context-free languages; co-CFL the languages whose complements are context-free. So CFL $\neq$ co-CFL.
Are there any nice characterizations or other basic facts about CFL $\cap$ ...
6
votes
1
answer
298
views
Size of complement of context-free language
Let $L$ be a context-free language, $\bar L$ be its complement and $\bar L_n$ be the length $n$ words in $\bar L_n$.
What is known about $|\bar L_n|$?
Note that it is known that $|L_n|$ is either ...
- 14k
5
votes
1
answer
1k
views
The class CFL\cap co-CFL
Is anything nontrivial known about the class $\mathrm{CFL}\cap \mathrm{coCFL}$? In particular, is it known whether $\mathrm{CFL}\cap \mathrm{coCFL} = \mathrm{DCFL}$ (certainly the reverse containment ...
- 732
4
votes
2
answers
166
views
What is the current state of the art in black-box grammar induction?
Grammar induction of Context Free Languages seems to be a very well researched field. I would like to know the current state of the art in inducing a Context Free Grammar (I am reading up Higuera's ...
- 197