Questions tagged [grammars]
The grammars tag has no usage guidance.
109
questions
31
votes
4
answers
7k
views
What is the most powerful kind of parser?
As a side-project, I'm writing a language using Python. I started by using a flex/bison clone called Ply, but am coming up against the edges in the power of what I can express with that style of ...
- 420
31
votes
2
answers
2k
views
Is {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} non-context-free?
Is the language {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} context-free or not?
I realized that I have encountered almost all variants of this question with different conditions about the ...
- 823
23
votes
4
answers
6k
views
Proof of the pumping lemma for context-free languages using pushdown automata
The pumping lemma for regular languages can be proved by considering a finite state automaton which recognizes the language studied, picking a string with a length greater than its number of states, ...
- 9,269
19
votes
6
answers
1k
views
Which models of computation can be expressed through grammars?
This is a reformulation of Are grammars programs? previous asked by Vag and with many suggestions from the commenters.
In what way can a grammar be seen as specifying a model of computation?
If, for ...
- 677
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
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
14
votes
4
answers
631
views
Base-k representations of the co-domain of a polynomial - is it context-free?
In chapter 4 of Jeffrey Shallit's A Second Course in Automata Theory the following problem is listed as open:
Let $p(n)$ be a polynomial with rational coefficients such that $p(n) \in \mathbb{N}$ for ...
- 411
14
votes
1
answer
2k
views
Is CFL strictly contained in NL?
We know that $\mathsf{REG}=\mathsf{NSPACE}(O(1))$ and $\mathsf{CSL}=\mathsf{NSPACE}(O(n))$.
What is the relation of $\mathsf{CFL}$ and $\mathsf{NSPACE}(O(\log n))=\mathsf{NL}$?
Is $\mathsf{CFL}$ a ...
- 241
13
votes
3
answers
4k
views
What are graph grammars?
I have found information on graph grammars and graph rewriting, but the papers that I find on it are a bit thick. Can someone give a quick overview of what graph grammars are, as well as an overview ...
- 309
10
votes
1
answer
806
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.4k
10
votes
1
answer
545
views
Chomsky Schützenberger enumeration theorem
In many textbooks the Chomsky-Schützenberger enumeration theorem is stated as that the characteristic formal power series of a language is $\mathbb N$-algebraic, if the grammar is unambigious. In some ...
10
votes
1
answer
343
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,127
10
votes
0
answers
250
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,946
10
votes
0
answers
266
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
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
9
votes
2
answers
221
views
Is there higher-dimensional generative grammar?
I'm interested in computer music, where there are approaches to treat pieces of music as sentences in generative grammars or L-systems. Instead of composing, one could then specify a grammar and let ...
- 616
9
votes
1
answer
233
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
8
votes
3
answers
865
views
1-way Quantum Finite Automata Example Question
I'm attempting to clarify my understanding in the example presented in Section 2.2 of 1-way Quantum Finite Automata: Strengths Weaknesses and Generalizations (this alternative link may also be useful)....
- 935
8
votes
2
answers
384
views
Mistake in Wikipedia CSG example?
I'm confused about the example given in Wikipedia article about Context-sensitive grammar:
https://en.wikipedia.org/wiki/Context-sensitive_grammar
Disclamer: I've already changed discussed section ...
- 635
8
votes
1
answer
471
views
Tool for translating PDAs to CFGs
We know that all push down automata are representable using context-free grammars. Furthermore, there is an algorithm to construct a CFG from any PDA (e.g. Sipser's proof in intro to theory of ...
- 385
8
votes
1
answer
200
views
Is $LL(k)$ for large $k$ considered harmful? If so, why?
I took a course touching on lexer and parser theory this semester (a sizeable chunk was devoted to regexes and other FSA, but context-free grammars were covered as well).
Over the course of the ...
- 249
8
votes
0
answers
1k
views
Names for the left- and right-hand sides of a grammar production?
Problem
I'm writing a document where I have to describe some of the properties of a type system as they relate to a particular formal grammar.
I was trying to refer to the right-hand-sides of the ...
- 181
7
votes
2
answers
3k
views
Is there an example of a non context-sensitive language?
I know $CSL\subset UL$ can be demonstrated by reduction to the absurd, but I've been trying to find a language that is in Type 0 ($UL$) and not in Context-Sensitive Languages ($CSL$).
Is there any ...
- 443
7
votes
1
answer
257
views
Complexity of a graph-rewriting problem
I recently came across the following problem which seems to fall in the context of graph rewriting problems:
Input: A graph $G=(V,E)$ with maximum degree 3, an edge $e_0 \in E$ and pairs of graphs $(...
- 607
7
votes
0
answers
812
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
7
votes
0
answers
344
views
The semantics of Parsing Expression Grammars
Is there a simple and intuitive explanation for the fact that the following parsing expression (where S is the starting symbol, $...
- 81
6
votes
2
answers
289
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
6
votes
2
answers
854
views
Has anyone mixed linear algebra with formal language theory in this way?
Let $G$ be the grammar:
$$
S \rightarrow aAb \\
A \rightarrow aA + a + \epsilon
$$
where $\epsilon$ is the empty string, $a,b$ are terminals and $S,A$ non-terminals with $S$ the start symbol. ...
- 213
6
votes
3
answers
444
views
Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?
As an undergraduate with limited understanding of QC and even the C-T thesis, I have problems figuring out why in questions such as Extended Church-Turing Thesis real-life quantum stuff is even given ...
- 183
6
votes
3
answers
481
views
Chomsky hierarchy for tree structures
I know of the Chomsky hierarchy, which concerns the expressive power of grammars to recognize languages $L \subseteq \Sigma^*$ made of words on an alphabet $\Sigma$.
Is there a similar hierarchy for ...
- 283
6
votes
2
answers
385
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
455
views
Which factors make the problem of inferring the grammar difficult?
Scott Aaronson said in the paper entitled "Why Philosophers Should Care About Computational Complexity" (Please see ECCC Report: TR11-108, section 7, pp 25-31):
Following the work of Kearns and ...
- 159
6
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,127
6
votes
1
answer
471
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, ...
- 555
6
votes
1
answer
167
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
6
votes
0
answers
104
views
Reference request: transforming a grammar to Greibach normal form preserves the number of parse trees
I believe that most "natural" ways of transforming a grammar to the GNF should preserve the number
of parse trees for each string. For example, Urbanek's construction from the paper
"On Greibach ...
- 245
5
votes
1
answer
938
views
What is the importance of linear languages?
What is the point of linear languages? They appear to be an intermediate set of languages in between regular and context-free languages, but do they have any useful or nice properties that either have ...
- 441
5
votes
2
answers
285
views
Why may the right hand sides in Chomsky Hierachy type 1 be larger?
I'm shaking my head because of this question, my Prof. didn't explain it. We have linear space limited automata and they have to satisfy for rules a -> b that |a| <= |b|.
Why?
I would have said, ...
leto
5
votes
1
answer
172
views
Alternative to LBA for recognising context-sensitive languages
I've always felt that there's no "canonical" automata for recognising context-sensitive languages. Much like there's DFA for regular, PDA for context-free and Turing machines for RE.
I'm ...
5
votes
1
answer
108
views
Is there any inherently ambiguous indexed language?
Indexed languages are defined as being produced by an indexed grammar.
My question is: Is there an indexed language such that there is no indexed grammar that can produce every word of the language in ...
- 101
5
votes
1
answer
2k
views
Emptiness of PDA without constructing the corresponding CFG
The emptiness problem for Context free Grammars(CFG) is well studied. The same holds for the equivalence problem between Pushdown Automata (PDA) and CFGs.
Therefore, given a PDA, the straightforward ...
- 198
5
votes
2
answers
306
views
Partially Ordered CFG
I'm looking for work about partially ordered context-free grammars. I've found one paper, which seems to simplify the problem too much (in addition to some technical mistakes, as far as I can tell). ...
- 293
5
votes
1
answer
145
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
5
votes
1
answer
567
views
Parse structure of a range concatenation grammar (RCG)
I know that with a context-free grammar, one can represent the results of a parse as a parse-tree. Specifically, each node represents one application of a production rule, is usually named for the LHS ...
- 615
5
votes
1
answer
4k
views
What are the relationship and difference between ambiguous grammars and non-deterministic ones?
Intuitively, I had assumed that ambiguous grammars were roughly the same as non-deterministic grammars. According to Wikipedia however, this is false:
there are non-deterministic unambiguous CFGs
...
- 151
5
votes
1
answer
149
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
5
votes
0
answers
98
views
Useful notion of ambiguous growing context-sensitive language
As far as I understand there is no useful notion of ambiguous context-sensitive language.
For example for any inherently ambiguous context-free language there is a context-sensitive grammar generating ...
- 61
5
votes
0
answers
163
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
5
votes
0
answers
114
views
Word grammars with free variables
I am trying to find any described formalism which introduces free variables into word grammars (I emphasize here word in order not to be confused with very similar thing in tree grammars).
What I ...
- 635
4
votes
1
answer
977
views
How to start learning formal language theory
I sincerely apologize if this is not appropriate in this stack Q&A, though it seemed the most fitting.
I want to learn formal language theory, as well as generating grammars etc. The purpose is ...
- 53