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, ...
Jeffrey Shallit's user avatar
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 ...
Jeffrey Shallit's user avatar
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$. ...
Peter Leupold's user avatar
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 ...
Lorenzo's user avatar
  • 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 \...
Jeffrey Shallit's user avatar
7 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 ...
Mark Schultz-Wu's user avatar
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 ...
sriram lamsal's user avatar
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:...
Joshua Herman's user avatar
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’...
Stella Biderman's user avatar
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 ...
gdmclellan's user avatar
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 ...
Hermann Gruber's user avatar
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 ...
StefanH's user avatar
  • 2,077
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 ...
M. kanté's user avatar
  • 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 ...
Lê Thành Dũng 'Tito' Nguyễn's user avatar
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 ...
Hermann Gruber's user avatar
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, &...
Timothy Chow's user avatar
  • 7,550
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-...
Hermann Gruber's user avatar
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 ...
Alessander Botti Benevides's user avatar
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 ...
Hermann Gruber's user avatar
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 ...
Kirill Boyarintsev's user avatar
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 ...
domotorp's user avatar
  • 14k
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 ...
Marzio De Biasi's user avatar
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-...
Andrey Lebedev's user avatar
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 ...
D.W.'s user avatar
  • 12.1k
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-...
Pluto's user avatar
  • 146
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: ...
Lamine's user avatar
  • 1,138
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 ...
Hermann Gruber's user avatar
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 ...
MRC's user avatar
  • 389
3 votes

Generating grammar from a string

You might be interested in Sequitur (given a single string, it compresses it by finding a grammar that generates just that one string) or in grammar induction (given a set of strings, it finds a ...
D.W.'s user avatar
  • 12.1k
2 votes

Counting words of length $n$ in an inherently ambiguous CFG?

It seems that this problem is NP-hard, if both the grammar and $n$ (in unary notation) are considered to be parts of the input. There is a classical construction that is used to show that universality ...
Kaban-5's user avatar
  • 245

Only top scored, non community-wiki answers of a minimum length are eligible