Un "automat binar modulo M" generează formele binare (peste alfabetul {0,1}) ale numerelor naturale, clasificându-le după resturile împărțirii la M; încercăm să formulăm limbajul binar al multiplilor de M (= 15).

Formele binare ale multiplilor (nenuli) de 3 sunt date de următoarea expresie regulată:
((110*(11)*0*) | (1(01*0)+10*))⁺ (11)*

Pentru multiplii de 5:
1((0w*) | (1(01)*1w*)) 10* unde w = 01*0(01)*1

De exemplu pentru trei operanzi, permutation([1,2,3], [A, B, C]) instanțiază variabilele A, B, C cu câte unul dintre numerele indicate, rezultând câte o permutare de [1,2,3]; apoi, arth_tree([A,B,C], Expr) va forma expresiile aritmetice cu operanzii dați de instanțierea curentă pentru [A,B,C] și rămâne să reținem expresia curentă în cazul în care valoarea acesteia este cea dorită.

Generarea limbajului expresiilor aritmetice cu o listă dată de operanzi, folosind Prolog.

Să se demonstreze că nu există expresii aritmetice de valoare 24, formate cu 3 operatori obișnuiți și cu operanzii 3, 4, 6 și 7.