/ Informatik

Compilerbau & Formale Sprachen

Mächtigkeit regulärer Sprachen, DFA-Übergänge, Ableitungsschritte in CNF, FIRST/FOLLOW-Mengen, LL(1)-Parsertabellen, Token-Längen, Syntaxbaumtiefe und NFA→DFA-Zustandsexplosion.

8 Rechner in dieser Kategorie, jeweils mit automatischer Variablen-Umstellung.

I01

Regulärer Ausdruck Zeichenanzahl

Anzahl der über einem Alphabet möglichen Zeichenketten fester Länge: Möglichkeiten = Alphabet^Länge.

I02

DFA Zustandsübergänge

Maximale Anzahl Zustandsübergänge eines deterministischen endlichen Automaten: Übergaenge = Zustaende · Alphabet (|δ| = |Q|·|Σ|).

I03

Grammatik Ableitungsschritte

Minimale Ableitungslänge in Chomsky-Normalform für ein Wort der Länge n: MinSchritte = 2·n − 1.

I04

FIRST/FOLLOW-Menge Größe

Maximale Größe einer FIRST- bzw. FOLLOW-Menge einer kontextfreien Grammatik: MaxGröße = Terminale + 1 (inklusive ε bzw. $/EOF).

I05

LL(1) Parsertabelle Größe

Anzahl der Felder in einer LL(1)-Parsertabelle: Einträge = Nichtterminale · Terminale (|M| = |N|·|T+$|).

I06

Token-Länge Lexer

Gesamtlänge des Quellcodes aus Tokenanzahl und durchschnittlicher Tokenlänge: Gesamtlänge = Tokens · DurchschnLänge.

I07

Syntaxbaumtiefe

Minimale Tiefe eines binären Syntaxbaums mit gegebener Blattanzahl: MinTiefe = ⌈log₂(Blaetter + 1)⌉.

I08

NFA zu DFA Zustandsexplosion

Maximale Zustandsanzahl des durch Potenzmengenkonstruktion erzeugten DFA: MaxDFAZustaende = 2^NFAZustaende.