# Tag Info

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

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

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

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

9

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.

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 ... 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 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. 6 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: $$S \to aSb$$ $$S \to ba$$ This generates the infinite set $$\{a^nbab^n \mid n \geq 0 \} = \{ba, abab, aababb, aaababbb, \dotsc \}$$ (See here) Now what if ... 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/... 6 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 address due to space (and time to write down this answer). A statement that reads, "There exists no "reasonable" computational model capable of ... 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 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 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. 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 ... 5 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, "There exists no computation model capable of recognising languages that a Turing Machine cannot." I would recommend not phrasing it this way, because ... 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 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 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 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 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. ... 3 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-grammars, or more generally, Regulated Array Grammars of Finite Index, Part I: Theoretical Investigations by Henning FERNAU, Rudolf FREUND and Markus HOLZER which ... 3 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 source of difficulty is purely computational; the statistical aspects are quite straightforward. If you were able to find the smallest DFA consistent with your ... 3 How can inherited attributes be simulated with synthesized ones: an example. The way of doing it is to postpone the evaluation of any attribute that uses directly or indirectly an inherited attribute, by abstracting it into a function that takes the inherited attribute as argument. There may be several such arguments. Here is a fragment of a simple example,... 3 For tree automata, you have the Mostowski hierarchy, which is about the complexity of acceptance condition: each level is of the form$(i,j)$with$i\in\{0,1\}$and$i\leq j$. Being at level$(i,j)$means that there is a parity automaton using parities from$i$to$j\$ recognizing the language. For more on parity condition, see here: https://en.wikipedia.org/...

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