<foo> simply produces <foo>in the text).
<URL: http://somewhere.tld/ >,
and it will be automatically made into a link.
(Do not try any other way or it might count as an attempt to spam.)mailto: URI,
e.g. mailto:my.email@somewhere.tld,
if you do not have a genuine Web site).
jonas (2018-02-13T18:54:08Z)
Thank you for the answer. Perhaps I should have figured that out on my own, because I knew all the prerequisites.
I knew that a regular grammar looks like a system of linear equations, where the nonterminal symbols look like the variables to solve for, the terminal symbols look like parameter constants carried symbolically to the solutions, the right arrow looks like an equals sign, alternation looks like addition, and concatenation looks like non-commutative multiplication. If I remember correctly, I learnt this from Bach Iván's introductory textbook, which explains the algorithm you describe in 3.4 as an analog of solving a linear equation by eliminating variables.
I knew that the number of words of length $ n $ from the alphabet $ {a,b} $ with no two adjacent $ b $ is the Fibonacci number $ F_{n+1} $. I've read Concrete Mathematics chapter 7, which explains how to solve such problems in general. The method of solution explained there uses a system of linear equations where the variable to solve for are the symbolic sum of each word in the language (weighted if parsing is ambiguous), which is just like the equations mentioned above, except that concatenation is replaced by commutative multiplication because we don't care about the order of symbols. I did understand that that method is general and works for every similar language, although I don't think I've explicitly articulated that it's exactly all regular languages that this covers and that the equations are based on the production rules of the regular grammar. That chapter also gives a similar example with the Catalan numbers, in which case the language is not regular, and so the generator function isn't rational, although I don't think I realized how general that procedure was, and may have assumed the Catalan numbers were among the luckier cases.
I also knew that the solution of a system of linear equations is rational. I knew that the solution of a system of polynomial equations is algebraic (I haven't heard that such equations were called "algebraic equations"), and that this is because in theory you can reduce such an equation to a single polynomial by a general procedure, even though it isn't worth carrying out that computation in practice (except for eliminating each linear equation).
Ruxor (2018-02-12T11:16:14Z)
@jonas: The basic idea is that rational languages can be seen as solutions to a set of linear equations and algebraic languages can be seen as solutions to a set of algebraic equations. For the latter, consider the rules of a context-free grammar G and, for each nonterminal symbol T, introduce the language L(G,T) generated by T following G: each set of rules like T→α|… gives you an equation for L(G,T) as a union ("sum") of concatenations ("monomials") of the various L(G,X) or constants, so it can be considered an algebraic equation in the "semi-ring" of languages (where addition is union and multiplication is concatenation). The analogy can be made even better by considering weighted languages (i.e., multisets of words, with weights belonging to some semiring), but I have to admit I don't know the details.
One consequence, however, is that the generating function of an algebraic language (which counts the number of words of a given length) is, indeed, algebraic (as a power series, "algebraic" over the field of rational functions), while the generating function of a rational language is rational. An instance of this is that the Catalan numbers, which count well-balanced sequences of parentheses, are the coefficients of an algebraic function.
jonas (2018-02-12T07:45:44Z)
Is there an explanation somewhere for why context-free languages are called “algébriques”? I haven't heard that name before, and it doesn't make sense to me.
Ruxor (2017-11-23T18:08:33Z)
@Xavier Combelle: Oui, les services informatiques de Télécom ont cassé des choses en migrant mon compte d'un disque à un autre. Je ne sais pas comment ils ont fait leur compte (le fichier est pourtant bien disponible sur le serveur) ni quand ça sera réparé. En attendant, j'ai mis une copie du document dans <URL: http://www.madore.org/~david/.tmp/notes-inf105.pdf >.
Xavier Combelle (2017-11-23T14:39:02Z)
404 not found on https://perso.telecom-paristech.fr/~madore/inf105/notes-inf105.pdf
Ruxor (2017-11-17T14:40:53Z)
@JMU: Non, je compile avec l'option -shell-escape de pdflatex et je m'en sers pour invoquer un script trivial qui écrit le numéro de version dans un fichier .tex que j'inclus ensuite. Voir lignes 83‒91 de <URL: http://git.madore.org/cgit/teach/inf105.git/tree/notes-inf105.tex?id=f1826f0f50ca2ff35761222b64d6312ac87bbc77 >, ainsi que le script lui-même <URL: http://git.madore.org/cgit/teach/inf105.git/tree/vc?id=f1826f0f50ca2ff35761222b64d6312ac87bbc77 >.
JMU (2017-11-17T12:30:33Z)
Rien à voir, mais ma curiosité est titillée à la vue de la référence du commit dans le fichier compilé. Tu as mis un post-commit hook qui édite le .tex ?
xavier (2017-11-11T18:09:44Z)
ok merci pour la clarification :)
Ruxor (2017-11-11T13:44:10Z)
@xavier: Il y a un résultat théorique, pour lequel je n'ai d'ailleurs aucune référence, qui dit que si une fonction est calculable avec probabilité 1 par une machine de Turing disposant d'un générateur aléatoire fort (i.e., il y a un programme T, faisant appel à un oracle, qui, quel que soit n, calcule f(n) avec probabilité 1 si l'oracle répond aléatoirement), alors en fait cette fonction est calculable sans générateur aléatoire (i.e., par une machine de Turing ordinaire). Donc au moins en ce sens-là (i.e., si on demande que le même résultat soit calculé avec probabilité 1), le fait d'ajouter un générateur aléatoire n'apporte rien. Mais dans l'autre sens, toute séquence aléatoire *donnée* est, avec probabilité 1, incalculable par une machine de Turing (ça c'est essentiellement trivial comme fait). En l'occurrence, je suppose l'absence de générateur aléatoire pour éviter toute discussion sur la question.
xavier (2017-11-11T13:07:20Z)
Note 25 sur le générateur aléatoire : Hum si on en rajoute un à une machine de Turing on y gagne quoi? Uniquement le fait d'avoir de l'aléatoire "fort" (c'est quoi cette bête) ou on gagne autre chose?
ooten (2017-11-11T12:51:28Z)
Il est super ton cours même si je ne l'ai que très partiellement parcouru. J'ai toujours aimé les long cours théoriques fruit d'un travail parfois multi séculaire dans ma jeunesse. Celui là en aurait certainement fait parti ☺