10
votes
Accepted
What is the state complexity of the copy language?
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
)
...
- 1,085
10
votes
Accepted
Known and described subclasses of Context-Free Grammars class
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$.
...
- 452
10
votes
Base-k representations of the co-domain of a polynomial - is it context-free?
Of course $k \geq 2$ here.
There once was a manuscript by Horváth that claimed to solve the problem, but it was unclear in several places and to my knowledge was never published.
As far as I know, ...
- 6,947
9
votes
Accepted
Is equivalence of unambiguous context-free languages decidable?
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 ...
- 108
9
votes
Accepted
Mistake in Wikipedia CSG example?
If I am not mistaken, a simpler CS grammar is possible. Here it is:
$S \rightarrow ABSc$
$S \rightarrow Abc$
$BA \rightarrow XA$
$XA \rightarrow XY$
$XY \rightarrow AY$
$AY \rightarrow AB$
$A \...
- 6,947
9
votes
Accepted
Chomsky Schützenberger enumeration theorem
There is a proof in the book of Kuich & Salomaa, Semirings, Automata, Languages and another one in the paper of Panholzer, "Gröbner Bases and the Defining Polynomial of a Context-free Grammar ...
- 6,947
6
votes
Which kind of grammar is the following?
The simple answer would be that, having an infinite set of rules, this is not a grammar in the usual sense. Languages over infinite alphabets have been investigated, but usually using register ...
- 2,490
6
votes
Known and described subclasses of Context-Free Grammars class
Your two grammars seem very similar. They are both linear grammars in two non-terminals. (Morally one, really -- in both examples the language of S is contained in the language semiring generated by ...
- 406
6
votes
Accepted
What are graph grammars?
Graph grammars have uses from software engineering to layout verification. Tinkerpop is a fairly popular system for graph traversal.
So recall a regular grammar where you have rewrite rules as follows:...
- 1,631
6
votes
What are graph grammars?
This paper opens with an introductory survey on graph grammars and then advances two new applications. It’s dated (1992) but explains the concepts well enough that it seems like the kind of thing you’...
- 1,046
6
votes
Accepted
How to start learning formal language theory
Theory of computation by M. Sipser is interesting per se. For introduction you have to practice and go in following sequence.
Regular language and automata
Context free grammar and expressions
...
6
votes
Accepted
Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?
I've written the following to talk about the connections between quantum computation and the (extended) Church-Turing thesis. Your question appears to have several other questions, which I don't ...
- 778
6
votes
Accepted
Alternative to LBA for recognising context-sensitive languages
Here is an alternative model:
Benedek Nagy: Left-most derivation and shadow-pushdown automata for context-sensitive languages, ICCOMP'06: Proceedings of the 10th WSEAS international conference on ...
- 5,649
5
votes
What are graph grammars?
You may also want to look at the Book by Courcelle a,d J. Engelfriet https://hal.inria.fr/hal-00646514/document where links between graph grammars and MSOL-definable graph classes are discussed. You ...
- 1,036
5
votes
Accepted
Complexity of a graph-rewriting problem
I don't know if it has been studied before, but after a quick look I think it should be PSPACE complete.
We can build a reduction using the Nondeterministic Constraint Logic model of computation (NCL)...
- 22.5k
5
votes
Accepted
Has anyone mixed linear algebra with formal language theory in this way?
How you choose your vector $\nu$ for every terminal symbol you must have a row with exactly one $\epsilon$ in your matrix so that it is a fixed point. So we could disregard terminal symbols, and what ...
- 1,987
5
votes
Notion of "quotient" or "inverse" for recognizable tree languages?
The Myhill-Nerode theorem characterizes regular/recognizable languages as those that have finitely many "quotients", and it works for trees — more precisely, a tree language is regular iff ...
5
votes
Ordered Grammar in THEORY OF COMPUTATION
Ordered grammars are a special case of context-free grammars with regulated rewriting. Another name for context free grammar with regulated rewriting is controlled grammar.
But, what is regulated ...
- 5,649
5
votes
Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?
I'll address just the first part of your question.
Neither the Church–Turing Thesis nor the Extended Church–Turing Thesis is a purely mathematical or formal statement. You phrased the C–T Thesis as, &...
- 7,103
4
votes
Accepted
Emptiness of PDA without constructing the corresponding CFG
Quick Answer: Yes, there is a really lovely algorithm that solves non-emptiness for pushdown automata that does not involve constructing the equivalent CFG.
Possible Drawback: Correct me if I am ...
- 5,045
4
votes
What is the grammar of network protocols and file formats?
There is an international agreed notation for describing protocols and format specifications
(well actually there are several), which is ASN.1. It is a form of Context_free grammar notation.
I used ...
4
votes
Accepted
Is $LL(k)$ for large $k$ considered harmful? If so, why?
The parsing table of a $LL(k)$ grammar grows exponentially in $k$.
This is however the worst-case scenario, which is not typical, as Niel pointed out:
For an $LL(k)$ grammar $G$, $k$ is the size of ...
- 560
4
votes
Determine if a structure is a model of an inductively defined predicate
What do you mean by the equality in your first formula? In first-order logic (FOL) with equality, one can only apply the equality operator to a couple of terms, not to formulae. Also, your use of ...
3
votes
Accepted
Looking for a particular normal form for Context-sensitive grammar
A set of grammars in Kuroda form $\mathcal{K}$ is a strict subset of grammars in the described form $\mathcal{L}$:$\mathcal{K}\subset\mathcal{L}$. This follows from the fact that the first form covers ...
3
votes
Which factors make the problem of inferring the grammar difficult?
Regarding the difficulty of learning grammars, let's stick to regular ones for concreteness. These are precisely the grammars/languages recognized by Deterministic Finite-state Automata (DFAs). The ...
- 10.2k
3
votes
Proof of the pumping lemma for context-free languages using pushdown automata
When discussing this problem with Géraud Sénizergues, he pointed me this paper by Sakarovitch that already proves this result. The proof seems to date back to this paper by Ogden.
References:
...
- 1,141
3
votes
Accepted
Is there higher-dimensional generative grammar?
Yes, there are n-dimensional grammars and in some cases specifically applied to music, see for example Grammar-based music composition by Jon McCormack, which talks about parametric extensions to L-...
- 146
3
votes
Finding smallest context free grammar that generates a set of sets
Define a language $L$ to be nicely-ordered if $L \subseteq a^*b^*c^*d^*\cdots$, i.e., in every word of $L$, the letters appear solely in lexicographic order.
Conjecture: the optimum is always ...
- 11.3k
3
votes
Mistake in Wikipedia CSG example?
Actually as several viewers agreed original grammar was incorrect. As @EmilJeřábek noticed, there was already discussion of this problem here: https://en.wikipedia.org/wiki/Talk:Context-...
- 635
3
votes
Base-k representations of the co-domain of a polynomial - is it context-free?
This is a sketch of the proof for $k=2$ and $L = \{[n^2]_2 \mid n \geq 1\}$; where $[n^2]_2$ is the binary representation of $n^2$. For better clarity we place the least significant bit of the binary ...
- 22.5k
Only top scored, non community-wiki answers of a minimum length are eligible