BuK/IIm19/Ausarbeitungen Lüpke/Brainstorming VL03 Luepke

Wiki-Quelltext dieser Seite.

<language>Python</language>
<language>Python</language>
== 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 \}$.<br>
$M = \{aaa,aba,aab,baa,bab,abb,bba,bbb\}$

<code id="5e8da562c99f4">
A = ['a', 'b']
M = ['aaa','aba','aab','baa','bab','abb','bba','bbb']

def inM(w):
    return w in M
</code>

<run id="5e8da562c9a7e">
print(inM('not'))
print(inM('a'))
print(inM('aba'))
</run>

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

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.

<code>
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
</code>
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. 
<run id="5e97538546f0b">
isWord('abbbabaa')
</run>

=== Primzahlen ===
Eine Primzahl ist eine natürliche Zahl, die größer als 1 und ausschließlich durch sich selbst und durch 1 teilbar ist ([https://de.wikipedia.org/wiki/Primzahl Wikipedia, 16.04.2020]).