2022 Developer Survey is open! Take survey.
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 ) ...
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$. ...
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, ...
user avatar
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 \...
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 ...
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 ...
user avatar
  • 108
9 votes
Accepted

What is the importance of linear languages?

The first obvious reason why linear languages were introduced is that mathematicians can hardly resist, facing a lateralized notion, to consider the symmetrical version as well. For instance, in ...
user avatar
  • 4,721
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 ...
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 ...
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’...
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:...
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 ...
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 ...
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 ...
user avatar
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)...
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 ...
user avatar
  • 1,947
5 votes

What characterizations exist for the grammars that can express subsets of the context-free languages?

Every context free language over a one letter alphabet (or equivalently every langauge recognized by unary PDAs, unary DPDAs or 1 counter machines) is regular. See: S. Ginsburg, H. Rice: "Two ...
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 ...
user avatar
  • 1,026
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 ...
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, &...
user avatar
  • 7,073
4 votes
Accepted

Asymptotic density of ambiguous context-free grammars (CFGs)

The question depends on the exact encoding. However, it seems that in many reasonable encodings, as the length tends to infinity, the number of production rules $S\to a$ (for an appropriate ...
user avatar
  • 14.1k
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 ...
user avatar
  • 550
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 ...
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 ...
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 ...
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 ...
user avatar
  • 10.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-...
user avatar
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-...
user avatar
  • 146
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 ...
user avatar
  • 10k
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 ...
user avatar

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