3
$\begingroup$

Statement comes from this answer. A blanket statement that this is a well-known fact is made in this other question.

I have never heard of a language equation. But I am just a student. Given the syntax, is this equating the derivations of a CFG grammar to equations?

In other words, is this bit from the answer $A=ABa$ meant to be considered equivalent to a BNF derivation $A \rightarrow ABa$? (where $A$ and $B$ mean the same as in the original answer -- variables that decompose to terminals containing $a$)

Or is there some other meaning being expressed here? From the second question that I found after I typed this question it seems to mean something different. Can someone "ELIStudent"?

$\endgroup$
  • $\begingroup$ Yes, the set of equations is isomorphic with the ste of productions. They mean different things but the in both cases you will end up with a set of all strings in the language. I thought that was reasonably well explained in the answer, but in maths, as they say, everything is obvious after you prove it :-) (And "well-known" is the same subtle put-down in maths as in any other field -- eg., "the well-known financial analyst / actor / ...", a phrase which is often intended to reinforce your obvious outsiderness. "What? You don't know who that is? What a dork!") $\endgroup$ – rici Nov 3 '16 at 4:06
  • $\begingroup$ @rici Excellent one-sentence summary, thanks. $\endgroup$ – Dave Nov 3 '16 at 19:20
  • $\begingroup$ @rici Also I wasn't in any way detracting from the original answer. I'm a student (old, but still a student) so not being well-known to me is not an indicator of faulty explanation on that end. I just have to learn it that's all. Funny you should mention that phrasing. I've seen it called the "curse of knowledge" when a learned person doesn't realize the depths of ignorance of the student. Or as Charles Wells put it in his Handbook of Mathematical Discourse the "you don't know shriek." Though he suggested it needed a more insulting name to help discourage it's use. :) $\endgroup$ – Dave Nov 3 '16 at 19:25
  • 1
    $\begingroup$ If something is really well-known, there is no point saying so, no? We all know it and we all know that we know it. So the only point is to send a subliminal message. But perhaps I'm being harsh... The other tendency one has to avoid is to start a lecture by saying "This is difficult..." As my uncle (an educator) used to say, there is no better way to discourage understanding than to tell someone they're not going to the understand. Anyway, best of luck with the learning... $\endgroup$ – rici Nov 3 '16 at 20:01
5
$\begingroup$

A good way to think about these equations is to imagine them as sets over valid words. Say I have an alphabet $\Sigma = \{a, b\}$, then the rule $$ A \leftarrow A a \mid b $$

says that there's some set $A$ that is isomorphic to the set $(A * \{a\}) \cup \{b\}$. Here the $*$ operation is the product/concatenation operation lifted over sets, that is $$ \{a, b, c\} * \{d, e, f\} = \{ad, ae, af, bd, be, bf, cd, ce, cf\} $$

Going back to our grammar rule, it is basically declaring the existence of a set $A$ of words that satisfies the equation $$ A = (A * \{a\}) \cup \{b\}. $$

Now, there's a huge class of sets of words that satisfies this equation. For example, the set $A_\bot = \{b, ba, baa, baaa, baaaa, \dots\}$ is a valid solution since a $b$ or appending any element of $A_\bot$ with another $a$ will result in a word that is already in $A_\bot$. However, you should check that $$ A_{bb} = \{b, bb, ba, bba, baa, bbaa, baaa, bbaaa, \dots\} $$ is also a valid solution to this equation. In particular, $b$ is already in $A_{bb}$, and for any element $ba^k$ or $bba^k$ in $A_{bb}$, its concatenation with $a$ results in $ba^{k+1}$ and $bba^{k+1}$, which are also already in $A_{bb}$. Therefore, $A_{bb}$ is also a valid fixed point.

In fact, for any given ground set of words $S = \{w_1, w_2, w_3, \dots\}$, we can construct a closure $A_S$ which contains every word in $S$ and similarly satisfies the above equation. In particular, the closure operator is the same isomorphism:

\begin{align*} A_S^{k + 1} &= (A_S^k * \{a\}) \cup \{b\} \\ A_S &= \bigcup_k^\infty A_S^k \end{align*}

So now we get to the real question. If there are an infinite supply of solutions for this equation, then what good is it as a characterization of some grammar? Well, intuitively, we hope to just characterize those words that are generated from this rule "from scratch". In effect, we wish to treat these rules as free objects. That is, we care about the case where the underlying generator $S = \{\}$. Let $$ A(S) = (S * \{a\}) \cup \{b\} $$ then we want $$ A_* = \bigcup_k A^{(k)}(\{\}) $$ to be the set generated by our grammar rule, where $A^{(k)} = A(A(\stackrel{k}{\dots} A(\cdot)))$.

This then gives some intuition of what we mean by the "least solution." $A(S)$ is monotone in the sense that $S \subseteq S' \implies A(S) \subseteq A(S')$; in fact, this holds over all grammar rules. Since the least element over the class of possible sets that $S$ can take (ordered on set inclusion) is the empty set, then effectively the "freely generated" language that we desire also turns out to be the smallest (ordered on set inclusion) fixed point, that is, $A(\{\}) \subseteq A(S')$ for any set $S'$.

In general, you'll see a lot of these "smallest solution" clauses all around the landscape of computer science. For example, any recursive program is the smallest solution to some program equation; any constructable inductive datatype is the smallest solution to some inductive datatype equation; any valid program semantic is the smallest solution to some logical equation; etc. It turns out that these classes of topological closures corresponds elegantly to a notion of finiteness. For example, the set of all finitary words $\Sigma^*$ is itself a least fixed-point. Since computations themselves can be seen as some enumeration process of finite objects, the analogy holds quite naturally; least fixed-points typically gives some assurance of some form of computability.

In conclusion, if you see the phrase "least solution" or "the least fix-point," it often means that the problem concerns finite objects that are freely-generated in the sense that only things that can be derived "from scratch" are considered.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.