43 Beziehungen: Ableitung (Informatik), Abzählbare Menge, Alphabet (Informatik), Äquivalenzrelation, Backus-Naur-Form, Berechenbarkeitstheorie, Chomsky-Hierarchie, Compilerbau, Deterministisch kontextfreie Sprache, Disjunkt, Erweiterte Backus-Naur-Form, Formale Sprache, Geordnetes Paar, Grammatik, Graphersetzungssystem, Kleenesche und positive Hülle, Kommunizierendes Grammatik-System, Kontextfreie Grammatik, Kontextsensitive Grammatik, Leeres Wort, LF(k)-Grammatik, LL(k)-Grammatik, LR(k)-Grammatik, Marcel Schützenberger, Mathematisches Modell, Monotone Grammatik, Nichtterminalsymbol, Noam Chomsky, Phrasenstrukturgrammatik, Produktionsregel, Reguläre Grammatik, Rekursiv aufzählbare Menge, Semi-Thue-System, Sprachwissenschaft, Syntaxtheorie, Teilmenge, Terminalsymbol, Theoretische Informatik, Transitionsrelation, Transitive Hülle (Relation), Tupel, Wachsend kontextsensitive Sprache, Wort (theoretische Informatik).
Ableitung (Informatik)
Als Ableitung wird in der theoretischen Informatik der Vorgang bezeichnet, ein Wort nach den Regeln einer formalen Grammatik zu erzeugen.
Neu!!: Formale Grammatik und Ableitung (Informatik) · Mehr sehen »
Abzählbare Menge
In der Mengenlehre wird eine Menge A als abzählbar unendlich bezeichnet, wenn sie die gleiche Mächtigkeit hat wie die Menge der natürlichen Zahlen \mathbb.
Neu!!: Formale Grammatik und Abzählbare Menge · Mehr sehen »
Alphabet (Informatik)
In der Informatik und der mathematischen Logik ist ein Alphabet eine endliche Menge voneinander unterscheidbarer Symbole, die auch Zeichen oder Buchstaben genannt werden.
Neu!!: Formale Grammatik und Alphabet (Informatik) · Mehr sehen »
Äquivalenzrelation
Unter einer Äquivalenzrelation versteht man in der Mathematik eine zweistellige Relation, die reflexiv, symmetrisch und transitiv ist.
Neu!!: Formale Grammatik und Äquivalenzrelation · Mehr sehen »
Backus-Naur-Form
Die Backus-Naur-Form oder Backus-Normalform (kurz BNF) ist eine kompakte formale Metasprache zur Darstellung kontextfreier Grammatiken (Typ-2-Grammatiken in der Chomsky-Hierarchie).
Neu!!: Formale Grammatik und Backus-Naur-Form · Mehr sehen »
Berechenbarkeitstheorie
Die Berechenbarkeitstheorie (auch Rekursionstheorie) ist ein Teilgebiet der theoretischen Informatik und der mathematischen Logik, die sich mit dem Begriff der Berechenbarkeit befasst, insbesondere damit, welche Probleme mit Hilfe einer Maschine (genauer: eines mathematischen Modells einer Maschine) oder eines anderen mathematischen Modells der Berechenbarkeit lösbar sind.
Neu!!: Formale Grammatik und Berechenbarkeitstheorie · Mehr sehen »
Chomsky-Hierarchie
Chomsky-Hierarchie, gelegentlich Chomsky-Schützenberger-Hierarchie (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger), ist ein Begriff aus der theoretischen Informatik.
Neu!!: Formale Grammatik und Chomsky-Hierarchie · Mehr sehen »
Compilerbau
Compilerbau, deutsch Übersetzerbau, ist eine Disziplin der Informatik, die sich mit dem Entwurf und der Programmierung von Compilern, die einen Quelltext in einen Zielcode umsetzen, beschäftigt.
Neu!!: Formale Grammatik und Compilerbau · Mehr sehen »
Deterministisch kontextfreie Sprache
Eine deterministisch kontextfreie Sprache ist eine Sprache, die von einem deterministischen Kellerautomaten akzeptiert wird.
Neu!!: Formale Grammatik und Deterministisch kontextfreie Sprache · Mehr sehen »
Disjunkt
Zwei disjunkte Mengen In der Mengenlehre heißen zwei Mengen A und B disjunkt (‚getrennt‘), elementfremd oder durchschnittsfremd, wenn sie kein gemeinsames Element besitzen.
Neu!!: Formale Grammatik und Disjunkt · Mehr sehen »
Erweiterte Backus-Naur-Form
Die Erweiterte Backus-Naur-Form, kurz EBNF, ist eine Erweiterung der Backus-Naur-Form (BNF), die ursprünglich von Niklaus Wirth zur Darstellung der Syntax der Programmiersprache Pascal eingeführt wurde.
Neu!!: Formale Grammatik und Erweiterte Backus-Naur-Form · Mehr sehen »
Formale Sprache
Eine formale Sprache ist eine abstrakte Sprache, bei der im Unterschied zu natürlichen Sprachen oft nicht die Kommunikation im Vordergrund steht, sondern die Definition und Anwendung formaler Systeme im engeren Sinn und der Logik im weiteren, allgemeinen Sinn.
Neu!!: Formale Grammatik und Formale Sprache · Mehr sehen »
Geordnetes Paar
Ein geordnetes Paar, auch 2-Tupel oder Dupel genannt, ist in der Mathematik eine wichtige Art und Weise, zwei mathematische Objekte zu einer Einheit zusammenzufassen.
Neu!!: Formale Grammatik und Geordnetes Paar · Mehr sehen »
Grammatik
allegorisch dargestellt als Gärtnerin, Gemälde von Laurent de La Hyre (1650) Die Grammatik oder auch Sprachlehre (von, ‚Buchstabe‘) bezeichnet in der Sprachwissenschaft (Linguistik) jede Form einer systematischen Sprachbeschreibung.
Neu!!: Formale Grammatik und Grammatik · Mehr sehen »
Graphersetzungssystem
Beispiel für Graphersetzungsregel (Optimierung aus dem Compilerbau: Multiplikation mit 2 durch Addition ersetzt) Graphersetzungssysteme dienen der formalen Beschreibung der Veränderung von Graphen.
Neu!!: Formale Grammatik und Graphersetzungssystem · Mehr sehen »
Kleenesche und positive Hülle
Die kleenesche Hülle (auch endlicher Abschluss, Kleene-*-Abschluss, Verkettungshülle oder Sternhülle genannt) eines Alphabets \Sigma oder einer formalen Sprache L ist die Menge aller Wörter, die durch beliebige Konkatenation (Verknüpfung) von Symbolen des Alphabets \Sigma bzw.
Neu!!: Formale Grammatik und Kleenesche und positive Hülle · Mehr sehen »
Kommunizierendes Grammatik-System
Kommunizierende Grammatik-Systeme bestehen aus mehreren formalen Grammatiken, die über eine Möglichkeit verfügen, miteinander zu kommunizieren.
Neu!!: Formale Grammatik und Kommunizierendes Grammatik-System · Mehr sehen »
Kontextfreie Grammatik
In der Theorie der formalen Sprachen ist eine kontextfreie Grammatik (CFG) eine formale Grammatik, die nur solche Ersetzungsregeln enthält, bei denen immer genau ein Nichtterminalsymbol auf eine beliebig lange Folge von Nichtterminal- und Terminalsymbolen abgeleitet wird.
Neu!!: Formale Grammatik und Kontextfreie Grammatik · Mehr sehen »
Kontextsensitive Grammatik
Die kontextsensitiven Grammatiken (kurz CSG, von engl. context-sensitive grammar) sind eine Klasse formaler Grammatiken und identisch mit den Typ-1-Grammatiken der Chomsky-Hierarchie.
Neu!!: Formale Grammatik und Kontextsensitive Grammatik · Mehr sehen »
Leeres Wort
Das leere Wort ist in der Theoretischen und in der Praktischen Informatik ein Wort, das aus keinem einzigen Zeichen besteht, also die Länge 0 hat.
Neu!!: Formale Grammatik und Leeres Wort · Mehr sehen »
LF(k)-Grammatik
Dieser Artikel setzt Vorkenntnisse im Bereich Theoretische Informatik und Compilerbau voraus. ---- Eine LF(k)-Grammatik ist eine spezielle kontextfreie Grammatik, welche die Grundlage eines LF(k)-Parsers bildet.
Neu!!: Formale Grammatik und LF(k)-Grammatik · Mehr sehen »
LL(k)-Grammatik
Dieser Artikel setzt Vorkenntnisse im Bereich Theoretische Informatik und Compilerbau voraus. ---- Eine LL(k)-Grammatik (im Gegensatz zu LF(k)-Grammatik auch schwache LL(k)-Grammatik) ist eine spezielle kontextfreie Grammatik, welche die Grundlage eines LL(k)-Parsers bildet.
Neu!!: Formale Grammatik und LL(k)-Grammatik · Mehr sehen »
LR(k)-Grammatik
In der theoretischen Informatik und dem Compilerbau bezeichnet LR(k)-Grammatik eine spezielle kontextfreie Grammatik, welche die Grundlage eines LR-Parsers bildet.
Neu!!: Formale Grammatik und LR(k)-Grammatik · Mehr sehen »
Marcel Schützenberger
Marcel Schützenberger Marcel-Paul Schützenberger, auch Marco Schützenberger, (* 24. Oktober 1920 in Paris; † 29. Juli 1996 ebenda) war ein französischer Mathematiker.
Neu!!: Formale Grammatik und Marcel Schützenberger · Mehr sehen »
Mathematisches Modell
Ein mathematisches Modell ist ein mittels mathematischer Notation erzeugtes Modell zur Beschreibung eines Ausschnittes der beobachtbaren Welt.
Neu!!: Formale Grammatik und Mathematisches Modell · Mehr sehen »
Monotone Grammatik
Eine monotone Grammatik (auch nichtverkürzende Grammatik, beschränkte Grammatik oder expansive Grammatik) ist eine formale Grammatik, die nur Produktionsregeln enthält, deren rechte Seite nicht kürzer als die linke Seite ist.
Neu!!: Formale Grammatik und Monotone Grammatik · Mehr sehen »
Nichtterminalsymbol
Ein Nichtterminalsymbol (auch Nichtterminal, Nonterminalsymbol oder Variable genannt) einer formalen Grammatik ist ein Symbol, das nicht in den endgültigen Wörtern vorkommt, die in der Grammatik erzeugt werden können.
Neu!!: Formale Grammatik und Nichtterminalsymbol · Mehr sehen »
Noam Chomsky
Noam Chomsky, 2017 220px Avram Noam Chomsky (* 7. Dezember 1928 in Philadelphia, Pennsylvania, USA) ist ein US-amerikanischer Sprachwissenschaftler sowie politischer Publizist und Aktivist.
Neu!!: Formale Grammatik und Noam Chomsky · Mehr sehen »
Phrasenstrukturgrammatik
Der Begriff Phrasenstrukturgrammatik (englisch phrase structure grammar) bezeichnet formale Grammatiken, die nach dem Konstituenten-Prinzip einen Satz schrittweise in kleinere Einheiten zerlegen.
Neu!!: Formale Grammatik und Phrasenstrukturgrammatik · Mehr sehen »
Produktionsregel
Eine Produktionsregel (auch Regel, Produktion oder Ersetzungsregel genannt) ist in der Theorie formaler Grammatiken eine Regel, die angibt, wie aus Wörtern durch eine Grammatik neue Wörter bzw.
Neu!!: Formale Grammatik und Produktionsregel · Mehr sehen »
Reguläre Grammatik
Eine reguläre Grammatik ist in der Informatik eine formale Grammatik vom Typ 3 der Chomsky-Hierarchie.
Neu!!: Formale Grammatik und Reguläre Grammatik · Mehr sehen »
Rekursiv aufzählbare Menge
Als rekursiv aufzählbare Menge (auch semi-entscheidbare Menge, positiv semi-entscheidbare Menge, halb-entscheidbare Menge, berechenbar aufzählbare Menge, kurz r.e., c.e.) wird in der Berechenbarkeitstheorie eine Menge von natürlichen Zahlen bezeichnet, wenn es einen Algorithmus gibt, der die Elemente dieser Menge aufzählt.
Neu!!: Formale Grammatik und Rekursiv aufzählbare Menge · Mehr sehen »
Semi-Thue-System
Semi-Thue-System (oder auch Umformungssystem, Wortersetzungssystem oder Stringersetzungssystem) ist in der Theoretischen Informatik ein Regelsystem zur Transformation von Wörtern.
Neu!!: Formale Grammatik und Semi-Thue-System · Mehr sehen »
Sprachwissenschaft
Sprachwissenschaft, auch Linguistik (zu ‚Zunge‘, ‚Sprache‘), untersucht in verschiedenen Herangehensweisen die menschliche Sprache.
Neu!!: Formale Grammatik und Sprachwissenschaft · Mehr sehen »
Syntaxtheorie
Der Terminus Syntaxtheorie bezeichnet theoretische Beschreibungs- und Erklärungsansätze, die sich mit den möglichen strukturellen Konfigurationen in Sätzen natürlicher Sprachen befassen.
Neu!!: Formale Grammatik und Syntaxtheorie · Mehr sehen »
Teilmenge
Mengendiagramm: ''A'' ist eine (echte) Teilmenge von ''B''. Die mathematischen Begriffe Teilmenge und Obermenge beschreiben eine Beziehung zwischen zwei Mengen.
Neu!!: Formale Grammatik und Teilmenge · Mehr sehen »
Terminalsymbol
Ein Terminalsymbol (auch Terminalzeichen oder kurz Terminal genannt) einer formalen Grammatik ist ein Symbol, das einzeln nicht weiter durch eine Produktionsregel ersetzt werden kann.
Neu!!: Formale Grammatik und Terminalsymbol · Mehr sehen »
Theoretische Informatik
Mind-Map zu einem Teilbereich der theoretischen Informatik Die theoretische Informatik beschäftigt sich mit der Abstraktion, Modellbildung und grundlegenden Fragestellungen, die mit der Struktur, Verarbeitung, Übertragung und Wiedergabe von Informationen in Zusammenhang stehen.
Neu!!: Formale Grammatik und Theoretische Informatik · Mehr sehen »
Transitionsrelation
Eine Transitionsrelation (auch Übergangsrelation) ist in der Informatik eine Relation, die mögliche Übergänge beschreibt.
Neu!!: Formale Grammatik und Transitionsrelation · Mehr sehen »
Transitive Hülle (Relation)
Die transitive Hülle bzw.
Neu!!: Formale Grammatik und Transitive Hülle (Relation) · Mehr sehen »
Tupel
Tupel (abgeleitet von mittellateinisch quintuplus ‚fünffach‘, septuplus ‚siebenfach‘, centuplus ‚hundertfach‘ etc.) sind in der Mathematik neben Mengen eine wichtige Art und Weise, mathematische Objekte zusammenzufassen.
Neu!!: Formale Grammatik und Tupel · Mehr sehen »
Wachsend kontextsensitive Sprache
Wachsend kontextsensitive Sprachen (abgekürzt: GCSL) sind ein Begriff aus der Theorie der Formalen Sprachen, einem Teilgebiet der Theoretischen Informatik.
Neu!!: Formale Grammatik und Wachsend kontextsensitive Sprache · Mehr sehen »
Wort (theoretische Informatik)
In der theoretischen Informatik ist ein Wort eine endliche Folge von Symbolen eines Alphabets.
Neu!!: Formale Grammatik und Wort (theoretische Informatik) · Mehr sehen »