BuK/IIm20/Vorlesung 8 Thomas

Wiki-Quelltext dieser Seite.

<language>Python</language>
== Übungsaufgabe ==

Schreiben Sie Prozeduren für G (Primzahlverschlüsselung) und $G^{−1}$:$G(A^∗)→A^∗$. Erzeugen Sie auch den Stream für $A^∗$ bei gegebenem Alphabet A unter Verwendung der Primzahlverschlüsselung als Gödelisierung.

<code id="609ec36cdc7b5">
import math
from itertools import chain

alphabet = ['a','b','c']
 
def prim(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    else:
        for i  in range(2,int(math.sqrt(n))+1):
            if n % i == 0:
                return False
        return True

def nextPrim(n):
    c = n + 1
    while(True):
        if prim(c):
            return c
        c += 1

def G(word):
    g = 1
    p = 1
    for char in word:
        if char not in alphabet:
            return "word not in alphabet"
    
        i = 0
        while i < len(alphabet):
            if char == alphabet[i]:
                i += 1
                break
            i += 1

        p = nextPrim(p)
        g *= p**i
    return g


def Gminus1(goedelnum):
    l = faktorisiere(goedelnum)
    l.append(0)
    r = []
    c = 0
    search = l[0]
    for num in l:
        if(search == num):
            c+=1
        else:
            r.append(alphabet[c-1])
            c = 1
            search = num
    return "".join(r)

def faktorisiere(n):
    l = []
    for i in chain([2], range(3, n//2 + 1, 2)):
        while n % i == 0:
            l.append(i)
            n = n // i
        if i > n:
            break
    return l
</code>

<run id="609ec36cdc81f">
print(G("abc"))
print(Gminus1(2250))

print(G("aba"))
print(Gminus1(90))

print(G("ababbabaacc"))
print(Gminus1(636539951960324922510))

print(G("ba"))
print(Gminus1(12))
print(Gminus1(2252))
</run>