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, um ein Gefühl dafür zu bekommen, wie die Wörter durch die 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
    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>

<run id="5e97538546f0b">
isWord('abbbabaa')
</run>