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>

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