TD 3 - Calcul non commutatif avec sympy

L'objectif du TD est de manipuler les séries génératrices de langages vues en cours.

In [1]: 
from sympy import *

On définit un alphabet de deux lettres \(A=\{a,b\}\):

In [2]: 
a,b = symbols('a,b', commutative = False)

Affichons les mots de longueur 4 pour tester :

In [3]: 
A4 = expand((a+b)**4)
In [4]: 
print A4

a*b*a*b + a*b*a**2 + a*b**2*a + a*b**3 + a**2*b*a + a**2*b**2 + a**3*b + a**4 + b*a*b*a + b*a*b**2 + b*a**2*b + b*a**3 + b**2*a*b + b**2*a**2 + b**3*a + b**4

Il y en a bien 16.

Pour travailler avec des mots, ces expressions ne sont pas très lisibles. Si on a un langage (pas de multiplicités), on peut utiliser une représentation en liste :

In [5]: 
print A4.as_ordered_terms()

[a*b*a*b, a*b*a**2, a*b**2*a, a*b**3, a**2*b*a, a**2*b**2, a**3*b, a**4, b*a*b*a, b*a*b**2, b*a**2*b, b*a**3, b**2*a*b, b**2*a**2, b**3*a, b**4]
In [6]: 
ll = A4.as_ordered_terms()

Pour afficher des mots plutôt que des monômes avec des * et des **, on bricole une petite expression régulière :

In [7]: 
import re
pat = re.compile(r'((\w)\*\*(\d+))')
In [8]: 
w = ll[3];w
Out[8]:
a*b**3
In [9]: 
pat.findall(str(w))
Out[9]:
[('b**3', 'b', '3')]
In [10]: 
def mon2word(w):
    return pat.sub(lambda x: x.group(2)*int(x.group(3)),str(w)).replace('*','')
In [11]: 
print map(mon2word,ll)

['abab', 'abaa', 'abba', 'abbb', 'aaba', 'aabb', 'aaab', 'aaaa', 'baba', 'babb', 'baab', 'baaa', 'bbab', 'bbaa', 'bbba', 'bbbb']

Le langage de Dyck

C'est le langage des mots de parenthèses bien formés, ou des arbres binaires. Il est défini par la grammaire (on note \(( = a\) et \() = b\)) \[ D\rightarrow \epsilon|aDbD \] qu'on écrit plutôt comme une équation entre séries formelles \[ D = 1 + aDbD\] le terme \(D_n\) formé des mots de longueur \(2n\) est alors \[D_n = \sum_{i=0}^{n-1}aD_ibD_{n-1-i}.\]

Ecrire une fonction dyck(n) renvoyant le terme de degré \(n\).

Pour calculer ce genre de fonction récursive, ils est plus efficace d'enregistrer les valeurs déjà calculées dans un dictionnaire.

In [16]: 
dd = {0:1, 1:a*b}
def dyck(n):
    # votre code ici
    if n in dd: return dd[n]
    return expand(sum([a*dyck(i)*b*dyck(n-1-i) for i in range(n)]))
In [17]: 
dyck(2)
Out[17]:
a*b*a*b + a**2*b**2
In [18]: 
dyck(3)
Out[18]:
a*b*a*b*a*b + a*b*a**2*b**2 + a**2*b*a*b**2 + a**2*b**2*a*b + a**3*b**3
In [19]: 
dyck(4)
Out[19]:
a*b*a*b*a*b*a*b + a*b*a*b*a**2*b**2 + a*b*a**2*b*a*b**2 + a*b*a**2*b**2*a*b + a*b*a**3*b**3 + a**2*b*a*b*a*b**2 + a**2*b*a*b**2*a*b + a**2*b*a**2*b**3 + a**2*b**2*a*b*a*b + a**2*b**2*a**2*b**2 + a**3*b*a*b**3 + a**3*b**2*a*b**2 + a**3*b**3*a*b + a**4*b**4
In [20]: 
D4 = dyck(4).as_ordered_terms()
In [21]: 
print map(mon2word,D4)

['abababab', 'ababaabb', 'abaababb', 'abaabbab', 'abaaabbb', 'aabababb', 'aababbab', 'aabaabbb', 'aabbabab', 'aabbaabb', 'aaababbb', 'aaabbabb', 'aaabbbab', 'aaaabbbb']

On peut maintenant introduire une variable commutative \(x\) :

In [22]: 
var('x')
Out[22]:
x
In [23]: 
d5 = dyck(5)
In [24]: 
d5.subs({a:x,b:x}) # Les substitutions se font avec un dictionnaire
Out[24]:
42*x**10

Vérifier que les premiers termes de la srie obtenue en effectuant cette substitution ont bien pour coefficients les nombres de Catalan.

Le code de Fibonacci

Le code de Fibonacci est \(C=\{b,ab\}\). C'est un code préfixe, c'est à dire qu'aucun de ses mots n'est préfixe d'un autre. Ceci assure que toute concaténation de mots de \(C\) est déchiffrable de manière unique. Soit \(F=C^*\) le langage engendré par \(C\), et \(F_n=A^n\cap F\) l'ensemble de ses mots de longueur \(n\).

In [25]: 
ff = {0:1, 1:b, 2:a*b+b*b}

def fib(n):
    # votre code ici
    if n in ff: return ff[n]
    return expand(b*fib(n-1)+a*b*fib(n-2))
In [26]: 
fib(3)
Out[26]:
a*b**2 + b*a*b + b**3

Répéter les manipulations précédents pour retrouver les premiers termes de la série génératrice des nombres de Fibonacci.

Arbres binaires

On représentera un arbre binaire sous la forme o ou (o,A,B) où A et B sont des arbres binaires.

Ecrire une fonction bintrees(n) renvoyant la liste des arbres binaires à \(n\) feuilles.

In [27]: 
var('o')
def bintrees(n):
    if n==1: return [o]
    else:
        ll = []
        for i in range(1,n):
            ll.extend([(o,u,v) for u in bintrees(i) for v in bintrees(n-i)])
        return ll
In [28]: 
print bintrees(5)

[(o, o, (o, o, (o, o, (o, o, o)))), (o, o, (o, o, (o, (o, o, o), o))), (o, o, (o, (o, o, o), (o, o, o))), (o, o, (o, (o, o, (o, o, o)), o)), (o, o, (o, (o, (o, o, o), o), o)), (o, (o, o, o), (o, o, (o, o, o))), (o, (o, o, o), (o, (o, o, o), o)), (o, (o, o, (o, o, o)), (o, o, o)), (o, (o, (o, o, o), o), (o, o, o)), (o, (o, o, (o, o, (o, o, o))), o), (o, (o, o, (o, (o, o, o), o)), o), (o, (o, (o, o, o), (o, o, o)), o), (o, (o, (o, o, (o, o, o)), o), o), (o, (o, (o, (o, o, o), o), o), o)]

Ecrire une fonction parcours(t) renvoyant les mots de Dyck associés aux arbres par un parcours préfixe.

In [33]: 
def parcours(t):
    # votre code ici
    if t == o: return ''
    return 'a'+ parcours(t[1])+'b'+ parcours(t[2])
In [34]: 
map(parcours, bintrees(5))
Out[34]:
['abababab',
 'ababaabb',
 'abaabbab',
 'abaababb',
 'abaaabbb',
 'aabbabab',
 'aabbaabb',
 'aababbab',
 'aaabbbab',
 'aabababb',
 'aabaabbb',
 'aaabbabb',
 'aaababbb',
 'aaaabbbb']
In []: