The context-free tag has no wiki summary.
10
votes
2answers
271 views
Does there exist an extension of regular expressions that captures the context free languages?
In many papers involving context-free grammars (CFGs), the examples of such grammars presented there often admit easy characterizations of the language they generate. For example:
$S \to a a S b$
...
1
vote
0answers
78 views
Non-uniform CFG ambiguity decidability
The uniform version (the version which we normally see) of deciding whether a CFG (Context Free Grammar) is ambiguous is undecidable. But here I'd like to know something about the non-uniform version ...
1
vote
0answers
92 views
Structural equivalence of two context-free grammars
I understand that determining if two context-free grammars are structurally equivalent is decidable (according to the 1968 paper by Paull, M.C. and Unger, S.H., "Structural equivalence of context-free ...
5
votes
0answers
167 views
Eliminate ambiguity from CFG
CFG here stands for context-free grammar. I understand that:
Deciding whether a CFG $G$ is ambiguous is undecidable.
Deciding whether a CFL $L$ is inherently ambiguous is undecidable.
My question ...
5
votes
1answer
152 views
Minimal Number of Symbols in Context-Free Grammar for a Special One-Letter Language
Given is the language
$$L_n = \{a^n\},$$
where $n$ is a natural number and $a$ is a letter. What are the productions/rules of a minimal context-free grammar according to the number of symbols of the ...
13
votes
1answer
850 views
Sufficient conditions for the regularity of a context-free language
It would be nice to collect a list of conditions that imply that a context-free language L
is regular, i.e. conditions of the form:
"if a given CFG/PDA has property P, then its languages is regular"
...
3
votes
0answers
254 views
Minimal context-free Grammar for a special one-letter Language
For natural numbers $n \geq 5$, $m \geq 2^{n-2} + 1$ the following context-free language is given:
$$
L_{n,m} = \{ a^i | 2 \leq i \leq m \} \setminus \{a^{2^i}|2 \leq i \leq n-2\}
$$
Find and ...
7
votes
0answers
340 views
Is there an ambiguity test for CFGs faster than trying all strings?
It is well known that testing whether a grammar is ambiguous is undecidable. It is however trivially decidable for any $G$ whether $L_n(G) := \{ w | w \in L(G) \wedge |w| \leq n \}$ for any $n \in ...
0
votes
1answer
148 views
Decide if a given sequence is regular or context-free
Given a sequence s (or a finite set of sequences) I would like to know if this was generated by a regular or by a context-free (supposes these are the only options) grammar.
Of course, this is an ...
20
votes
1answer
1k views
Can all unambiguous grammars be parsed in linear time?
When tinkering with noncanonical LR parsing, I thought up a parsing method (with infinitely sized tables, which makes it somewhat unpractical) capable of parsing exactly the unambiguous grammars in ...
-1
votes
1answer
2k views
When converting a Context-Free Grammar to Chomsky Normal Form why is a new start state added? [closed]
I'm taking a theoretical computer science class and we just went over the steps to rewrite a context-free grammar in Chomsky Normal Form. The steps we were told to complete are:
Add a new start ...
4
votes
1answer
327 views
Permutation phrases with LR parsing
A permutation phrase is an extension to the standard (E)BNF context free grammar definitions: a permutation phrase $\{ A_1, \dots, A_n \}$ contains $n$ productions (or equivalently, nonterminals) ...
3
votes
1answer
1k views
Why is non-determinism (Push-down automata) necessary?
I would like to know why for the recognition of context-free languages only non-deterministic push-down automata (DPA=NPDA) work. Why do deterministic push-down automata (DPDA) not recognize such ...
3
votes
1answer
178 views
Can Bencodes Be Described With a Context-Free Grammar?
Bencoding is the encoding scheme used by Bittorrent applications. You’re probably most familiar with bencoding via the .torrent file format used by Bittorrent ...
18
votes
10answers
1k views
For a language to be programmable, is it mandatory that it be based on a context free grammar
Practically, for a language that can eventually be compiled/transformed into system level instructions, is it necessary that it be a context free grammar?
ex: Are all programming/scripting languages ...
16
votes
3answers
491 views
CFG parsing using $o(n^2)$ space
There are a multitude of algorithms that can parse a context-free grammar in $O(n^3)$ time. Using matrix multiplication, one can even go asymptotically faster than that.
However, all algorithms for ...
-6
votes
1answer
1k views
How do you convert the following ambiguous grammar to unambiguous? [closed]
I understand how the difference between the two, how ambiguity means that there is at least one string with 2 distinct parse trees while there is only one in an unambiguous tree. But I can't seem to ...
0
votes
0answers
173 views
Testing the emptiness of DPDA [closed]
How to test the emptiness of a DPDA without converting it to a CFG?
11
votes
1answer
206 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 ...
7
votes
1answer
330 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 ...
5
votes
1answer
620 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 ...
2
votes
1answer
344 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 ...
3
votes
1answer
171 views
Classes containing boolean closure of CFLs
So I asked a similar question on MathOverflow, but I now realize I asked the wrong question and asked it in the wrong place.
Anyway, I'm searching for a class of languages containing the boolean ...
