Kellerautomat in Python

L(PDA) = {anbn | n>0}

class Stack:
    def __init__(self):
        self.stackliste = []
        self.stacklistenlaenge = 0

    def pop(self):
        if self.istLeer() == False:
            self.stacklistenlaenge = self.stacklistenlaenge - 1
            return self.stackliste.pop()

    def peek(self):
        if self.istLeer() == False:
            return self.stackliste[self.stacklistenlaenge - 1]

    def push(self, inhalt):
        self.stackliste.append(inhalt)
        self.stacklistenlaenge = self.stacklistenlaenge + 1

    def getStacklistenlaenge(self):
        return self.stacklistenlaenge

    def istLeer(self):
        if self.stacklistenlaenge <= 0:
            return True
        else:
            return False
#---------------------------------------------------
def Zustandsuebergangsfunktion(symbol):
    global state
    if state == "q0":
        if symbol == "a":
            state = "q1"
            pdaStack.pop()
            pdaStack.push("Z")
            pdaStack.push("P")
            return True
        else:
            return False
    if state == "q1":
        if symbol == "a":
            pdaStack.pop()
            pdaStack.push("P")
            pdaStack.push("P")
            state = "q1"
            return True
        elif symbol == "b":
            pdaStack.pop()
            state = "q2"
            return True
        else:
            return False
    if state == "q2":
        if symbol == "b":
            if pdaStack.peek() == "P":
                state = "q2"
                pdaStack.pop()
                if pdaStack.peek() == "Z":
                    state = "q3"
                return True
        else:
            return False
    if state == "q3":
        if pdaStack.peek() == "Z":
            pdaStack.pop()
            return True
        else:
            return False
#---------------------------------------------------
def Akzeptor(wort):
    global state
    for i in range(len(wort)):
        testsymbol = wort[i]
        aktzustand = Zustandsuebergangsfunktion(testsymbol)
        print("Zustand:     ", state, "\tAktueller Stack:  ", pdaStack.stackliste)
        if aktzustand == False:
            return False
    if pdaStack.peek() == "Z" and state == "q3":
        return True
    else:
        return False
#---------------------------------------------------

pdaStack = Stack()
pdaStack.push("Z")
state = "q0"
print("Startzustand:", state, "\tLeerzustand Stack:", pdaStack.stackliste)

ergebnis = Akzeptor("aaaaabbbbb")
print("---------\nAkzeptiert?",    ergebnis)

 

Musterlösung Haha-Automat (Akzeptor)

L(DEA) ={(ha)n! | n>0)

state = "q0"
def Zustandsuebergangsfunktion(symbol):
    global state
    if state == "q0":
        if symbol=="h":
            state = "q1"
            return True
        else:
            return False
    if state == "q1":
        if symbol=="a":
            state = "q2"
            return True
        else:
            return False
    if state == "q2":
        if symbol=="!":
            state = "q3"
            return True
        elif symbol =="h":
            state = "q1"
            return True
        else:
            return False
    if state == "q3":
        return False

def Akzeptor(wort):
    global state
    for i in range(len(wort)):
        testsymbol = wort[i]
        aktzustand = Zustandsuebergangsfunktion(testsymbol)
        if aktzustand == False:
            print("war nix")
            return False
    if state == "q3":
        print("stimmt!")
        return True

ergebnis = Akzeptor("hahahaha!")
print(ergebnis)

 

Musterlösung Moore-Automat am CPX

Ampelschaltung als Moore-Automat

import board
import time
import neopixel
import touchio

NeopixelReihe = neopixel.NeoPixel(board.NEOPIXEL, 10)
NeopixelReihe.auto_write = False
B_A1 = touchio.TouchIn(board.A1)
zustand = "q0"
startzeit = time.monotonic()
dt = time.monotonic()

AusgabeR = [(16, 0, 0), (0, 0, 0), (0, 0, 0)]
AusgabeY = [(0, 0, 0), (16, 16, 0), (0, 0, 0)]
AusgabeG = [(0, 0, 0), (0, 0, 0), (0, 16, 0)]
AusgabeRY = [(16, 0, 0), (16, 16, 0), (0, 0, 0)]


def resetTimer():
    global startzeit
    startzeit = time.monotonic()


def macheAusgabe(zustand):
    if zustand == "q0":
        NeopixelReihe[2] = AusgabeG[0]
        NeopixelReihe[1] = AusgabeG[1]
        NeopixelReihe[0] = AusgabeG[2]
    
    if zustand == "q1":
        NeopixelReihe[2] = AusgabeY[0]
        NeopixelReihe[1] = AusgabeY[1]
        NeopixelReihe[0] = AusgabeY[2]
        
    if zustand == "q2":
        NeopixelReihe[2] = AusgabeR[0]
        NeopixelReihe[1] = AusgabeR[1]
        NeopixelReihe[0] = AusgabeR[2]

    if zustand == "q3":
        NeopixelReihe[2] = AusgabeRY[0]
        NeopixelReihe[1] = AusgabeRY[1]
        NeopixelReihe[0] = AusgabeRY[2]
        NeopixelReihe.show()


def zustandsuebergangsfunktion():
    global zustand
    global dt
    global startzeit
    if zustand == "q0":
        macheAusgabe(zustand)
        if B_A1.value:
            zustand = "q1"
            resetTimer()
            return
        
    elif zustand == "q1":
        macheAusgabe(zustand)
        if dt > 1.0:
            resetTimer()
            zustand = "q2"
            return
    
    elif zustand == "q2":
        macheAusgabe(zustand)
        if dt > 1.0:
            resetTimer()
            zustand = "q3"
            return
    
    elif zustand == "q3":
        macheAusgabe(zustand)
        if dt > 1.0:
            resetTimer()
            zustand = "q0"
            return

while True:
    zustandsuebergangsfunktion()
    dt = time.monotonic() - startzeit
    time.sleep(0.1)