Theoretische Informatik Flashcards
1
Q
Begriffe
A
- Sprache = Teilmenge aus Menge aller möglichen Wörter eines Alphabets
- Grammatik: beschreibt Sprachen aus endlich vielen Wörten
2
Q
Chromsky Hierarchie Typ0
A
- alle Formalen Grammatiken ohne Einschränkungen
3
Q
Chromsky-Hierarchie Typ1
A
- Kontextsensitiv
- für alle Regeln w1 –> w2, gilt:
- I w1 I <= I w2 I (rechte Seite nicht kürzer als Linke)
- bzw. w1 kann Symbolfolge sein, muss aber mind. 1 Nichtterminalsymbol enthalten
4
Q
Chromsky-Hierachrie Typ2
A
- kontextfrei
- Typ1 UND in jeder Regel der Grammatik muss auf linker Seite ein Nichtterminimalsymbol stehen, aud rechter Seite beliebige nicht leere Folge von Terminalen- und Nichtterminalensymbolen
- Grammatik meister Programmiersprachen
5
Q
Chromsky- Hierarchie Typ3
A
- regulär
- Typ2 UND auf rechter Seite genau ein Terminalsymbol und maximal 1 weiteres Nichtterminalsymbol
- einheitlich immer vor oder immer hinter Terminalsymbol
- je nachdem
- linksregulär oder
- rechtsreguläre Grammatik
- je nachdem
6
Q
Chromsky-Hierachie
A
7
Q
Zusammenfassung
A
- Sprache: Teilmenge aller Wörter eines Alphapet, durch Grammatik beschrieben
- Regulärer Ausdruck: Muster für Wörter
- Chromsky-Hierachie Grammatik
- Syntaxbaum, Syntaxdiagramm & BNF Schreibweise veranschaulichen kontextfreie Grammatik
- XML Auszeichnungssprache, Datenformat & Metasprache
