Kellerautomaten

Alle Dateien dieser Aktivität kommen in diesen Ordner. Ein Programm startest du im Terminal mit ruby und dem Namen der Datei.

Alle Dateien dieser Aktivität kommen in diesen Ordner. Ein Programm startest du im Terminal mit python3 und dem Namen der Datei.

Lege count.rb an:

# Stehen die runden Klammern richtig? Ein Zähler merkt sich, wie viele
# Klammern gerade offen sind.
def balanced(word)
    depth = 0
    word.each_char do |symbol|
        if symbol == '('
            depth += 1
        elsif symbol == ')'
            depth -= 1
            return false if depth < 0
        end
    end
    depth == 0
end

['(()())', '(()', '())(', ''].each do |word|
    puts "#{word.inspect} #{balanced(word)}"
end

ruby count.rb

"(()())" true
"(()" false
"())(" false
"" true

Lege count.py an:

# Stehen die runden Klammern richtig? Ein Zähler merkt sich, wie viele
# Klammern gerade offen sind.
def balanced(word):
    depth = 0
    for symbol in word:
        if symbol == '(':
            depth += 1
        elif symbol == ')':
            depth -= 1
            if depth < 0:
                return False
    return depth == 0


for word in ['(()())', '(()', '())(', '']:
    print(repr(word), balanced(word))

python3 count.py

'(()())' True
'(()' False
'())(' False
'' True

In Ruby ist ein Array schon ein Stack: stack.push(x) legt x oben drauf, stack.pop nimmt den obersten Wert herunter und gibt ihn zurück, stack.last zeigt ihn, ohne ihn wegzunehmen.

Lege brackets.rb an. Diese Zeilen kommen ans Ende, darüber schreibst du balanced:

['([]{})', '([)]', '((', ''].each do |word|
    puts "#{word.inspect} #{balanced(word)}"
end

In Python ist eine Liste schon ein Stack: stack.append(x) legt x oben drauf, stack.pop() nimmt den obersten Wert herunter und gibt ihn zurück, stack[-1] zeigt ihn, ohne ihn wegzunehmen.

Lege brackets.py an. Diese Zeilen kommen ans Ende, darüber schreibst du balanced:

for word in ['([]{})', '([)]', '((', '']:
    print(repr(word), balanced(word))

Lege pda.rb an. PDA steht für pushdown automaton, das englische Wort für Kellerautomat.

# Ein Kellerautomat prüft runde Klammern. Er liest das Wort Zeichen für
# Zeichen und hat einen Stack; ganz unten liegt #, das Zeichen für »leer«.
START = 'q0'
ACCEPTING = ['q0']
# [Zustand, gelesenes Zeichen, oberstes Zeichen des Stacks]
#   => [neuer Zustand, was an dessen Stelle auf den Stack kommt]
# Der Stack wird von unten nach oben geschrieben: '#(' heißt, # bleibt
# liegen und ( kommt oben drauf; '' heißt, das oberste Zeichen ist weg.
TRANSITIONS = {
    ['q0', '(', '#'] => ['q0', '#('],
    ['q0', '(', '('] => ['q0', '(('],
    ['q0', ')', '('] => ['q0', ''],
}

def accepts(word, trace: false)
    state = START
    stack = ['#']
    puts "      #{state}  #{stack.join}" if trace
    word.each_char do |symbol|
        top = stack.pop
        move = TRANSITIONS[[state, symbol, top]]
        # kein Übergang: der Fehlerzustand, das Wort ist abgelehnt
        return false if move.nil?
        state, push = move
        stack.concat(push.chars)
        puts "#{symbol.ljust(5)} #{state}  #{stack.join}" if trace
    end
    ACCEPTING.include?(state) && stack == ['#']
end

accepts('(()())', trace: true)
['(()())', '(()', '())(', ''].each do |word|
    puts "#{word.inspect} #{accepts(word)}"
end

accepts nimmt bei jedem Zeichen das oberste Zeichen mit pop vom Stack und schlägt mit Zustand, Zeichen und diesem obersten Zeichen in TRANSITIONS nach. Was dort steht, kommt mit concat wieder oben drauf, Zeichen für Zeichen. Starte es mit ruby pda.rb.

Lege pda.py an. PDA steht für pushdown automaton, das englische Wort für Kellerautomat.

# Ein Kellerautomat prüft runde Klammern. Er liest das Wort Zeichen für
# Zeichen und hat einen Stack; ganz unten liegt #, das Zeichen für »leer«.
START = 'q0'
ACCEPTING = {'q0'}
# (Zustand, gelesenes Zeichen, oberstes Zeichen des Stacks)
#   -> (neuer Zustand, was an dessen Stelle auf den Stack kommt)
# Der Stack wird von unten nach oben geschrieben: '#(' heißt, # bleibt
# liegen und ( kommt oben drauf; '' heißt, das oberste Zeichen ist weg.
TRANSITIONS = {
    ('q0', '(', '#'): ('q0', '#('),
    ('q0', '(', '('): ('q0', '(('),
    ('q0', ')', '('): ('q0', ''),
}


def accepts(word, trace=False):
    state = START
    stack = ['#']
    if trace:
        print(f'      {state}  {"".join(stack)}')
    for symbol in word:
        top = stack.pop()
        move = TRANSITIONS.get((state, symbol, top))
        # kein Übergang: der Fehlerzustand, das Wort ist abgelehnt
        if move is None:
            return False
        state, push = move
        stack.extend(push)
        if trace:
            print(f'{symbol:<5} {state}  {"".join(stack)}')
    return state in ACCEPTING and stack == ['#']


accepts('(()())', trace=True)
for word in ['(()())', '(()', '())(', '']:
    print(repr(word), accepts(word))

accepts nimmt bei jedem Zeichen das oberste Zeichen mit pop vom Stack und schlägt mit Zustand, Zeichen und diesem obersten Zeichen in TRANSITIONS nach. Was dort steht, kommt mit extend wieder oben drauf, Zeichen für Zeichen. Starte es mit python3 pda.py.

Kopiere pda.rb nach anbn.rb, zum Beispiel mit cp pda.rb anbn.rb im Terminal. Leere dort TRANSITIONS und ersetze die Zeilen am Ende:

accepts('aabb', trace: true)
['ab', 'aabb', 'aab', 'abab', 'ba', ''].each do |word|
    puts "#{word.inspect} #{accepts(word)}"
end

Kopiere pda.py nach anbn.py, zum Beispiel mit cp pda.py anbn.py im Terminal. Leere dort TRANSITIONS und ersetze die Zeilen am Ende:

accepts('aabb', trace=True)
for word in ['ab', 'aabb', 'aab', 'abab', 'ba', '']:
    print(repr(word), accepts(word))