dimanche 2 février 2020

La théorie des langages.

A force de bricoler et d'essayer d'améliorer des partie de logicielle que j'ai faites, je suis tombé sur Flex et Bison puis sur des référence à la théorie des langages formel. 
J'ai acheté le boucain (introduction to formal languages Révéz) mais j'ai des difficultés:
-- j'imagine des choses qui ne sont pas ce qui est présenté dans le live et donc je ne comprends pas ce que je lis.
-- je fais des digressions constamment dans différent domaines y compris en réalisant un générateur de langage utilisant une grammaire générative. 

Donc je n'avance pas et ce n'est pas seulement un problème de travail assidu. 

Des managers  qui m'ont observé depuis le  début de ma carrière on constaté un certain manque d'ambition mais on pourrait parfois émettre l'hypothèse d'une ambition démesurée qui peut aisément être prise pour de l'inconséquence, ou de la folie voir de la bêtise.

Vous avez déjà été prévenue sur les risques que je prends dans ce Blog. Ils sont démesurés par rapport à mes connaissances des sujets abordés.

Donc la théorie des langages est importante car pour moi elle chapeaute les autres théories.
Pour bien comprendre la manière de penser d'un étranger il est préférable de bien connaître sa langue, pas seulement savoir parler couramment mais connaître sa structure. Au début on est incapable de reproduire les sons aussi par ce qu'on est incapable de les reconnaître, enfin....la raison est probablement plus complexe.

Il est donc possible que les obstacles rencontrés dans la recherche fondamentale en physique soit du à l'absence d'un langage adapté. Mais quel langage chercher? La théorie des langages pourrait-elle nous aider en essayant de s'orienter vers de nouvelle structures? Ces langages seront ils encore manipulés directement par des cerveaux humains ou prises en charge presque totalement à l'aide des ordinateurs?  On pourrait même se demander si les nouveaux langages qui vont être utilisés avec les ordinateur quantiques ne vont pas donner naissance à de nouvelles théories mathématiques. 

Mais je suis obligé d'arrêter, il faut quitter le mode recherche pour revenir en mode apprentissage: limiter les rêveries, fixer des horaires, quantifier le nombre de pages lues.

Pour moi la recherche nécessite une part d'incompétence:  vous êtes obligé à un moment donné d'utiliser  des domaines de connaissance qui vous sont étrangers . C'est pour cette raison qu'il faut des équipes pluridisciplinaires. 

Je  suis une grosse équipe de gens très incompétents à moi tout seul.... plus  Google.

Ici une tentative de développement d'un  générateur de langage (tout type  Chomsky 0-4)
Cela n'est pas complètement testé donc à vos risques et périls!

A python pgm: langage generator from grammar rules

The test suite for this programm

It works with  grammars that generates  words with infinit length.
It just cut the derivation when the length is higher than a chosen limit.
But it is not always possible to predict the length of the finnal word when rules would shrink a word like aPb-->ac .
That kind of rules gives normally a warning messages and we might not see all words having a length below the chosen limit in the final result.

Before publishing it I received comments that  the pgm wasn't working. They can say it officially now!

This pgm might be usefull to generate special kind of permutation like in the exemple given at the end of the source: generating L={P|Na(P)=Nb(P}  Vn={S,A,B} Vt={a,b}. I am still searching a way to make a test suit and generating an equivalent language with itertools.

A lot of interesting problems arise simply by trying to resolve practical problems like building a subset of the language and limiting the length of the words.

Some vague idees:
-- Structure of a language: we could compare language just by comparing the general form of the tree we explore during the derivation (abstraction of the alphabet itself).
-- how to add  shrinking rules  that will collapse parts of the language.
-- how to find a generative grammar from a preexisting language
-- how to optimize a generative grammar (by having less rules or more efficient rules during the derivation).
-- is it possible to have a canonical form for a generative grammar.

The general idee would  be to find new langages that could by their structure expand the possibilties of  existing langages.

After having tested some generative grammar with my program I had to make some modifications.
One of them was to let the program run even if I encounter situations where there are still non terminal characters but no rule can apply.
This is the case of this grammar
    F=[("S","a"),       ("S","CD"),       ("C","ACB"),       ("C","AB"),       ("AB","aBA"),      ("Aa","aA"),       ("Ba","aB"),       ("AD","Da"),       ("BD","Ea"),       ("BE","Ea"),       ("E","a")]
 generating L={ a^n² |n in 1,2,3,....}

This grammar generates (if I made no mistakes) a lot of non-derivable words. A lot more than the word in L: I had to wait hours before seeing the  first words appearing.

A way to recognize this kind of grammar would appear be more useful  to me than the Chomsky types. But I am a programmer not a linguist.
There is also perhaps a way to determine some rules that have no chance to reappear during derivation. Again a way to classify the grammar and the language.
How to transform this grammar to a more efficient one? When is it possible?
They are so many possibilities, but computers could help.