All Questions
Tagged with context-free grammars
32 questions
0
votes
0
answers
39
views
Are there approaches to deriving a Grammar(production rules) from given set of strings?
Apologies for unambiguous question. So far I have a lot of difficulties of discerning on how to design formal production rules for some formal language aside from classic examples such as equal pairs ...
- 9
5
votes
2
answers
159
views
Modify DCFG to enforce length limit
Given a deterministic context-free grammar $G$ that generates the language $L$, is there an efficient algorithm that can be used to construct another DCFG $G_N$ that generates the language $\{ s \in L ...
- 163
0
votes
0
answers
91
views
Are there data structures that cannot be serialized / deserialized using a context free grammar?
I understand that deserializing data from a string or binary stream into a data structure is effectively the same parsing. When you deserialize the input string, you use a grammar to create a parse ...
10
votes
0
answers
254
views
Smallest context-free grammar for powers of two summing to $2^k$
Let $k > 0$ and define an alphabet $\Sigma_k = \{ 2^0, 2^1, \ldots, 2^k \}$. Define:
$$P_k = \{ a_1a_2\cdots a_t \in \Sigma_k^* \mid \sum_i a_i = 2^k \}.$$
This is a finite language.
Question: Is ...
- 3,976
5
votes
1
answer
150
views
Different definitions of grammar complexity
It's known that there are different "kinds" of grammar complexity of language $L$ --- nonterminal complexity (minimal possible $|N|$ for grammar $(N, \Sigma, P, S)$ generating $L$), covering ...
- 411
3
votes
0
answers
164
views
Deciding whether an arbitrary context-free grammar generates a deterministic push-down automata?
I know that it's undecidable whether an arbitrary context-free grammar is ambiguous, but is it decidable whether that grammar is deterministic? I can't find the answer to this question anywhere on the ...
- 131
2
votes
0
answers
76
views
A Context-Sensitive Grammar which cannot be recognised by a Parsing Expression Grammar
It is (currently) an open question of whether every context-free grammar can be recognised by some parsing expression grammar. [1]
However, has it been proven that there exists an example of a ...
- 121
3
votes
1
answer
168
views
Compressing grammars by introducing ambiguity and left-recursion
This is a reference request. What is known about the following questions?
Problem: Given a grammar $G$ (for example context-free) with language $L$ we can introduce a
new grammar $G'$ which also ...
- 11.6k
4
votes
2
answers
190
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
6
votes
1
answer
171
views
Example of context-free tree language which can not be generated by monadic CFTG
Assuming that a context-free tree language (CFTL) is that which is generated by a context-free tree grammar (CFTG), I am looking for an example of CFTL which can not be generated by a monadic CFTG (...
- 635
1
vote
0
answers
68
views
What is the interpretation of an infinite formal context-free grammar?
Let $L$ be a language as follows:
$$
\begin{align*}
L &::= a\ |\ L^{*}\\
\end{align*}
$$
Now, suppose I apply some sort of transformation $T : N \rightarrow N$ where $N$ is the set of non-...
- 309
7
votes
1
answer
2k
views
What is the complexity of counting parse trees?
A Counting Problem
Given a CFG $G$ and a string $s$, how many distinct parse trees are there for the string $s$?
An Example Instance
Let's consider an example instance consisting of a CFG $G$ with ...
- 5,167
5
votes
0
answers
164
views
"Context" understanding in tree grammars
The Context-Free tree grammar has rules of the form:
$A\rightarrow t$ or $A(x_1,\dots,x_n)\rightarrow t_x$,
where $A\in N$, $t\in T(N\cup T)$, $t_x\in T(N\cup T\cup \{x_1,\dots,x_n\})$, $T(Z)$ ...
- 635
19
votes
1
answer
1k
views
Is equivalence of unambiguous context-free languages decidable?
It is well known that the equivalence problem is undecidable for general context-free languages. However, all proofs of this fact that I am aware of seem to involve some ambiguous context-free ...
- 464
5
votes
1
answer
152
views
Regarding proper form of production rules of Context-free tree grammars
Is it possible to describe Context-free Tree Grammar $G_t$ such that set of yields of its trees will coincide with Context-sensitive word language $a^nb^nc^n$?
$\{a^nb^nc^n | n>0\}=\{Yield(t)|t\...
- 635
3
votes
0
answers
178
views
Context-Sensitive Grammar characteristic properties
This question can look like some kind of puzzle, but it is actually part of more complex applied problem.
Let's consider subspace of Context-Sensitive Grammars, which contains grammars which can not ...
- 635
6
votes
2
answers
396
views
Finding smallest context free grammar that generates a set of sets
Are there any results known about the size of smallest context free grammar that generates a set of sets?
That is, I am given an alphabet $\Sigma$ as well as a set $S \subseteq \mathbb{P}(\Sigma)$ ...
- 338
6
votes
2
answers
296
views
Known and described subclasses of Context-Free Grammars class
I'm looking for various researches which consider specific subclasses of Context-Free Grammar class, i.e. some specific described cases, which differ from well-known:
deterministic/non-deterministic
...
- 635
7
votes
0
answers
845
views
Does PEG contain CFG?
Despite their considerable expressive power, all PEGs can be parsed in linear time using a tabular or memoizing parser (8). These properties strongly suggest that CFGs and PEGs define incomparable ...
- 420
10
votes
0
answers
274
views
Complexity of a problem over acyclic context-free grammars
Let $G$ be an acyclic, context-free grammar over a fixed alphabet $\Sigma=\{a_1,\dots,a_k\}$ with the restriction (without loss of generality) that $|w|=2$ for each rule $A\to w$ in the grammar. ...
- 500
6
votes
1
answer
508
views
Counting words of length $n$ in an inherently ambiguous CFG?
There is a polynomial-time algorithm for computing the number of words of length $n$ in an unambiguous CFG $G = (V, \Sigma, R, S)$ (via a dynamic programming approach). However, for ambiguous CFGs, ...
- 653
10
votes
1
answer
352
views
What is the state complexity of the copy language?
Let a number $n$ be given. Consider the following language $L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \}$.
In words, $L_n$ is the set of copy strings of length $2n$.
Consider the following ...
- 5,167
4
votes
1
answer
280
views
What characterizations exist for the grammars that can express subsets of the context-free languages?
It is well known that CFGs and PDAs are equivalent, and there has been extensive research about the relationship between deterministic pushdowns and $LR(1)$ grammars, as $DCFL$ is a subset of $LR(1)$.
...
- 2,962
9
votes
1
answer
236
views
Asymptotic density of ambiguous context-free grammars (CFGs)
What is the ratio of ambiguous CFGs to all CFGs?
Since both sets are countably infinite the ratio is not well-defined.
But what about the asymptotic density:
$$\lim_{n \mapsto \infty}\frac
{\# \...
- 103
2
votes
1
answer
2k
views
Difference between a cyclic and a left-recursive context-free grammar?
I am currently reading a paper indicating that a cyclic CFG and a left-recursive CFG are different things:
The original purpose of the LC transform is to allow
simulation of left-corner parsing ...
- 121
2
votes
0
answers
249
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 ...
- 63
0
votes
1
answer
259
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 ill-...
- 356
-1
votes
1
answer
5k
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 state ...
- 101
0
votes
1
answer
191
views
Describing a grammar and associated parser
In the process of writing a Turing machine simulator, I decided on a machine representation in ASCII that closely mirrors Turing's original machine tables. I am interested in the formal categorization ...
- 103
10
votes
1
answer
810
views
Closure of unambiguous context-free languages under pre- and postfix.
Let $L$ be a context-free language. Define $ppc(L)$ to be the pre- and postfix closure of $L$, in other words, $ppc(L)$ contains all of $L$'s prefixes and postfixes, and hence $L$ itself. My question: ...
- 11.6k
16
votes
1
answer
498
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
9
votes
1
answer
849
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