Brainstorming VL03 Luepke

Aus ProgrammingWiki

Archivierte Version vom 2020-04-16T08:56:11+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

isWord('abbbabaa')

Brainstorming VL03 Luepke

Entscheidbarkeit und Aufzählbarkeit

Suche