As of May 31, 2023, we have updated our Code of Conduct.
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 ) ...
Joseph Stack's user avatar
  • 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$. ...
Peter Leupold's user avatar
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
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 ...
Lorenzo's user avatar
  • 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 \...
Jeffrey Shallit's user avatar
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 ...
Jeffrey Shallit's user avatar
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 ...
Klaus Draeger'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

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
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

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's user avatar
  • 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 ...
Hermann Gruber's user avatar
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,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)...
Marzio De Biasi'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
  • 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 ...
Lê Thành Dũng 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,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 ...
Michael Wehar's user avatar
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 ...
Brian Tompsett - 汤莱恩's user avatar
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 ...
Boson's user avatar
  • 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 ...
Alessander Botti Benevides'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

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 ...
Aryeh's user avatar
  • 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: ...
Lamine's user avatar
  • 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-...
Pluto's user avatar
  • 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 ...
D.W.'s user avatar
  • 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-...
Andrey Lebedev's user avatar
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

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