16

I thought about this problem again, and I think I have a full proof. It is a bit more tricky than what I anticipated. Comments are very welcome! Update: I submitted this proof on arXiv, in case this is useful to someone: http://arxiv.org/abs/1207.2819 $\DeclareMathOperator{\fp}{fp}$ $\DeclareMathOperator{\lp}{lp}$ $\newcommand{\fpp}[1]{\widehat{\fp{#1}}}$ $\...


10

The approach you're describing is the generating function approach. By solving systems of polynomial equations, one can calculate the number of words of given length (generated by any non-terminal), and through it the corresponding asymptotics. For regular languages one can directly use linear algebra to estimate the number of words of given length. The ...


10

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 ) allows to show very easily an exponential lower bound for CFGs. Let $G$ a grammar in Chomsky Normal Form for $L_n$. For every word $w\in \{0,1\}^n$ there exists at ...


10

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$. Your first language seems to have density values of only 0 and 1 while the second goes up to 3. So the first is 1-slender, the second is not following the ...


10

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, the problem is still open. One direction of the implication is easy, of course.


9

In a rule Aβ→γβ, β is called the context because it does not change by applying the rule. Applying a rule Aβ→γ changes the β part completely, and therefore β is not a context at all. In this case, β does not have a name. It is nothing more than one of the many substrings of the left-hand side of the rule Aβ→γ. If I have to call β as something, I would ...


9

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 \rightarrow a$ $Bb \rightarrow bb$. A derivation for the string $aaabbbccc$ is $\Rightarrow_1 ABSc\\\Rightarrow_1 AB\textbf{ABSc}c\\\Rightarrow_2 ABAB\textbf{Abc}cc\...


9

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 classical arguments for undecidability of the CFL universality problem make use of inherently ambiguous languages, and thus one needs new ideas to show ...


8

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 algebra, you deal with left or right inverses, but also with inverses. In ring theory, you consider left or right ideals, but also ideals, etc. Since left linear ...


7

$\mathrm{CSL}=\mathrm{NSPACE}(O(n))$. Thus, take your favourite PSPACE-complete problem. If it is decidable in $\mathrm{NSPACE}(O(n))$ (for example, QBF is), you are done. Otherwise, introduce a polynomial amount of padding to make it so.


7

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 Generating Function", J. of Automata, Languages and Combinatorics 10 (2005), 79–97. I wish there were a simple and clear proof of the result.


6

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 automata rather than grammars. That being said, you could treat the language as a limit (i.e. infinite union) of finitary languages defined by the "truncations" $G_i$ ...


6

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 the language of D.) It might be worth looking at your example in terms of the Chomsky-Schützenberger theorem. The theorem's statement for the two grammars in ...


6

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 Pushdown automata Non context free grammar Lr(k) grammar Turing Machines If interest level drops keep reading a fun book https://en.wikipedia.org/wiki/...


5

As you already noted, a single example or any finite number of words in $L$ is not going to be the right notion. So why not look beyond? A somewhat famous paper did so in 1967 and revealed what happens when you try to learn in the limit. An alternative interpretation of your question leads to the field of descriptive complexity theory where one looks for a ...


5

Juan Bermejo Vega has given an accurate summary of what is said in the original paper. I will give you a higher-level description. I will recommend, in your case, to avoid thinking of the amplitudes as probabilities altogether. They are related to probabilities, but this is not especially helpful to think about for these finite automata. I suspect that ...


5

For sure, the automata performs a measurement after reading each symbol "a" and applying an associated unitary $V_a$. Yet, it is not really meaningful to compute the amplitudes of the state to be measured over $|q_{0}⟩$ and $|q_{1}⟩$ and to put them on the diagram, for the automata does neot measure the projectors $|q_{0}⟩\langle q_{0}|$, and $|q_{1}⟩\langle ...


5

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 you get then seems to be similar to how grammars could be read as language equations, which could be generalized to equations between formal power series. This ...


5

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 families of languages related to ALGOL", Journal of the ACM, 9: 350–371, 1962. For what regards PDAs with bounded stack reversals they are equivalent to bounded ...


5

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). I quick idea is the following (I assume you're familiar with the NCL model): given an NCL graph $G$, you can replace red and blue directed edges with a ...


5

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 rewriting? Regulated rewriting alters the "derivation mode" of context-free grammars by adding some control mechanism to the derivation relation. This control ...


4

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 interpretation of the starting symbol $S$ and the terminal $a$) will be more than one with high probability; here I literally mean the same terminal $a$. If we consider ...


4

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 the maximal lookahead needed across $L(G)$. But it appears that in practice, the need for a $k$ lookahead is restricted to a small portion to the language, so ...


4

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 to teach formal notations for networking at one time, but these things have dropped out of the curriculum in favour of security ; which is interesting when a ...


4

A context-free grammar is cyclic if there exists a non-terminal $A$ and a derivation in one or more steps $A\Rightarrow^+ A$. It is left-recursive if there exists a non-terminal $A$, a mixed sequence of terminals and non-terminals $\gamma$, and a derivation in one or more steps $A\Rightarrow^+ A\gamma$. Hence cyclic implies left-recursive, but the converse ...


4

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 wrong, but it doesn't appear to be more efficient than the approach where you convert to a CFG. Basic Idea: It can be viewed as a sort of dynamic programming ...


4

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 equality cannot be considered a case of definition (what could be better depicted by $\triangleq$) since the predicate List appears on both sides of the equality. ...


4

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’re interested in.


4

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 of the following. $S - aBa$ $S -> ba$ This would be the infinite set $$\{a^nbab^n \mid n \geq 0 \} = \{ba, abab, aababb, aaababbb, \dotsc \}$$ (See here) Now ...


4

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 can also find in this book several references.


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