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,967
10
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,967
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$.
...
- 462
10
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 ...
- 118
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,967
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
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,641
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
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,500
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
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 ...
- 918
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,840
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.6k
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 ...
- 2,037
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,046
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,840
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,465
5
votes
Is there any inherently ambiguous indexed language?
This is an open question, which is explicitly stated in the paper
Adams, Jared; Freden, Eric; Mishna, Marni, From indexed grammars to generating functions, RAIRO, Theor. Inform. Appl. 47, No. 4, 325-...
- 5,840
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 ...
4
votes
Is there any context-free language that is inherently ambiguous as an indexed language
I just wrote this in an answer to the OP's other question on this topic, but for reasons of self-containedness, let me just reproduce the relevant part again:
This is an open question, which is ...
- 5,840
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
Base-k representations of the co-domain of a polynomial - is it context-free?
I think I have a proof. The proof follows from this lemma.
Lemma. For a context-free language $L$ if for infinitely many $n$ there are $n^6$ words of equal length whose first $n^2$ letters are the ...
- 13.9k
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.6k
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.7k
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
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
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,137
3
votes
Different definitions of grammar complexity
I think that among the most obvious measures are variable and production complexity. These are structural measures, in the sense there is for each k an infinitude of languages having measure k. And ...
- 5,840
3
votes
Accepted
Subset of regular languages
Yes, this is identical to a bigram model, a Markov model with order 2. Briefly, each state corresponds to a context of up to n-1 symbols, and each arc represents ...
- 389
Only top scored, non community-wiki answers of a minimum length are eligible