Brainstorming VL03 Luepke

Aus ProgrammingWiki

Archivierte Version vom 2020-04-16T18:02:38+00:00. Aktuelle Version

Entscheidbarkeit und Aufzählbarkeit

ÜA zu Beispiel 1 und 2

A^* = \{a, b\}^* und M \subset A^* = \{ w \space | \space w \in A^* \space\text{und}\space |w| = 3 \}.

M = \{aaa,aba,aab,baa,bab,abb,bba,bbb\}

A = ['a', 'b']
M = ['aaa','aba','aab','baa','bab','abb','bba','bbb']

def inM(w):
    return w in M

print(inM('not'))
print(inM('a'))
print(inM('aba'))

A^* = \{a, b\}^* und M \subset A^* = \{ w = aw' \space | \space w' \in A^* \}.

Um solche Mengen in einem Programm verfügbar zu machen, kann man das Cantorsche Diagonalisierungsverfahren 1. Art zuhilfe nehmen. Dadurch bekommt man ein Gefühl dafür, wie Wörter durch eine Prozedur sinnvoll aufgezählt werden können.

import itertools
from itertools import permutations

def generate(f, x):
  return itertools.accumulate(itertools.repeat(x), lambda v,_:f(v))

def isWord(word): 
    if (word[0] != 'a'):
        print('False')
        return
    if (word == 'a'):
        print('True')
        return 
    for index, i in enumerate(generate(lambda x: 1+x, 0)):
        for aIndex, aPart in enumerate(generate(lambda x: x[0]+x, 'a')):
            for bIndex, bPart in enumerate(generate(lambda x: x[0]+x, 'b')):
                perms = ['a'+''.join(p) for p in permutations(aPart+bPart)]
                perms.append('a'+aPart)
                perms.append('a'+bPart)
                if checkWord in perms:
                    print('True')
                    return
                if (bIndex >= i):
                    break
            if (aIndex >= i):
                break

Hier reichen ein oder zwei zusätzliche Zeichen und das Programm kann nur durch manuellen Abbruch oder Absturz der Laufzeitumgebung beendet werden. Ob das Wort valide ist, weiß man auch nach Absturz nicht.

isWord('abbbabaa')

Primzahlen

Eine Primzahl ist eine natürliche Zahl, die größer als 1 und ausschließlich durch sich selbst und durch 1 teilbar ist (Wikipedia, 16.04.2020).

Brainstorming VL03 Luepke

Entscheidbarkeit und Aufzählbarkeit

ÜA zu Beispiel 1 und 2

Primzahlen

Suche