46 Beziehungen: Ableitung (Informatik), Akzeptieren (Automaten- und Komplexitätstheorie), Algorithmus, Alphabet (Informatik), Anwendungsfall, Backus-Naur-Form, Bioinformatik, Chomsky-Hierarchie, Chomsky-Normalform, Cocke-Younger-Kasami-Algorithmus, Compiler, Computerlinguistik, Computerprogramm, Determinismus (Algorithmus), Deterministisch kontextfreie Sprache, Disjunkt, Entscheidbar, Formale Grammatik, Formale Sprache, Greibach-Normalform, Jeffrey Ullman, John E. Hopcroft, Kartesisches Produkt, Kellerautomat, Kleenesche und positive Hülle, Kontextfreie Sprache, Landau-Symbole, Lineare Sprache, Mehrdeutige Grammatik, Menge (Mathematik), Nichtdeterminismus, Nichtterminalsymbol, Parser, Parsergenerator, Produktionsregel, Programmiersprache, Quelltext, Relation (Mathematik), Terminalsymbol, Tree Adjoining Grammar, Tupel, Uwe Schöning, Wahrscheinlichkeitsmaß, Wort (theoretische Informatik), Wortproblem (Berechenbarkeitstheorie), Zeitkomplexität.
Ableitung (Informatik)
Als Ableitung wird in der theoretischen Informatik der Vorgang bezeichnet, ein Wort nach den Regeln einer formalen Grammatik zu erzeugen.
Neu!!: Kontextfreie Grammatik und Ableitung (Informatik) · Mehr sehen »
Akzeptieren (Automaten- und Komplexitätstheorie)
Akzeptieren ist ein Begriff aus der Automaten- und Komplexitätstheorie, Teilgebieten der theoretischen Informatik.
Neu!!: Kontextfreie Grammatik und Akzeptieren (Automaten- und Komplexitätstheorie) · Mehr sehen »
Algorithmus
sowjetischen Briefmarke anlässlich seines 1200-jährigen Geburtsjubiläums Ein Algorithmus (benannt nach al-Chwarizmi, von arabisch: Choresmier) ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen.
Neu!!: Kontextfreie Grammatik und Algorithmus · 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!!: Kontextfreie Grammatik und Alphabet (Informatik) · Mehr sehen »
Anwendungsfall
Beispiel eines Anwendungsfalldiagramms in der Unified Modeling Language. Die beiden Anwendungsfälle SMS verschicken und Fotomessage verschicken eines Mobilfunkbetreibers sind spezifiziert. Hierarchie von Anwendungsfällen im Cockburn-Stil Ein Anwendungsfall (engl. use case) bündelt alle möglichen Szenarien, die eintreten können, wenn ein Akteur versucht, mit Hilfe des betrachteten Systems ein bestimmtes fachliches Ziel (engl. business goal) zu erreichen.
Neu!!: Kontextfreie Grammatik und Anwendungsfall · 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!!: Kontextfreie Grammatik und Backus-Naur-Form · Mehr sehen »
Bioinformatik
Oberflächenprotein eines Influenza-Virus (Modell) Die Bioinformatik ist eine interdisziplinäre Wissenschaft, die Probleme aus den Lebenswissenschaften mit theoretischen computergestützten Methoden löst.
Neu!!: Kontextfreie Grammatik und Bioinformatik · 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!!: Kontextfreie Grammatik und Chomsky-Hierarchie · Mehr sehen »
Chomsky-Normalform
Die Chomsky-Normalform (Abk.: CNF) ist in der theoretischen Informatik eine Normalform für kontextfreie Grammatiken.
Neu!!: Kontextfreie Grammatik und Chomsky-Normalform · Mehr sehen »
Cocke-Younger-Kasami-Algorithmus
Der Cocke-Younger-Kasami-Algorithmus (CYK-Algorithmus) ist ein Algorithmus aus dem Gebiet der theoretischen Informatik.
Neu!!: Kontextfreie Grammatik und Cocke-Younger-Kasami-Algorithmus · Mehr sehen »
Compiler
Ein Compiler (auch Kompilierer; von ‚zusammentragen‘ bzw. ‚aufhäufen‘) ist ein Computerprogramm, das Quellcodes einer bestimmten Programmiersprache in eine Form übersetzt, die von einem Computer (direkter) ausgeführt werden kann.
Neu!!: Kontextfreie Grammatik und Compiler · Mehr sehen »
Computerlinguistik
Die Computerlinguistik (CL) oder linguistische Datenverarbeitung (LDV) untersucht, wie natürliche Sprache in Form von Text- oder Sprachdaten mit Hilfe des Computers algorithmisch verarbeitet werden kann.
Neu!!: Kontextfreie Grammatik und Computerlinguistik · Mehr sehen »
Computerprogramm
Ein Computerprogramm oder kurz Programm ist eine den Regeln einer bestimmten Programmiersprache genügende Folge von Anweisungen (bestehend aus Deklarationen und Instruktionen), um bestimmte Funktionen bzw.
Neu!!: Kontextfreie Grammatik und Computerprogramm · Mehr sehen »
Determinismus (Algorithmus)
Ein deterministischer Algorithmus ist ein Algorithmus, bei dem nur definierte und reproduzierbare Zustände auftreten.
Neu!!: Kontextfreie Grammatik und Determinismus (Algorithmus) · Mehr sehen »
Deterministisch kontextfreie Sprache
Eine deterministisch kontextfreie Sprache ist eine Sprache, die von einem deterministischen Kellerautomaten akzeptiert wird.
Neu!!: Kontextfreie 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!!: Kontextfreie Grammatik und Disjunkt · Mehr sehen »
Entscheidbar
In der theoretischen Informatik heißt eine Eigenschaft auf einer Menge entscheidbar (auch rekursiv, rekursiv ableitbar), wenn es ein Entscheidungsverfahren für sie gibt.
Neu!!: Kontextfreie Grammatik und Entscheidbar · Mehr sehen »
Formale Grammatik
Formale Grammatiken sind mathematische Modelle von Grammatiken, die zur eindeutigen Erzeugung und Beschreibung formaler Sprachen dienen.
Neu!!: Kontextfreie Grammatik und Formale Grammatik · 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!!: Kontextfreie Grammatik und Formale Sprache · Mehr sehen »
Greibach-Normalform
Die Greibach-Normalform ist ein Begriff der theoretischen Informatik, der im Zusammenhang mit kontextfreien Sprachen von Interesse ist.
Neu!!: Kontextfreie Grammatik und Greibach-Normalform · Mehr sehen »
Jeffrey Ullman
Jeffrey David Ullman (* 22. November 1942 in New York City) ist ein US-amerikanischer Informatiker.
Neu!!: Kontextfreie Grammatik und Jeffrey Ullman · Mehr sehen »
John E. Hopcroft
John E. Hopcroft, 2009 John Edward Hopcroft (* 7. Oktober 1939 in Seattle) ist ein amerikanischer Informatiker.
Neu!!: Kontextfreie Grammatik und John E. Hopcroft · Mehr sehen »
Kartesisches Produkt
Das kartesische Produkt A \times B der beiden Mengen A.
Neu!!: Kontextfreie Grammatik und Kartesisches Produkt · Mehr sehen »
Kellerautomat
Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der theoretischen Informatik, ein Konstrukt, das verwendet wird, um gewisse Eigenschaften von Problemen und Algorithmen zu analysieren und zu beweisen.
Neu!!: Kontextfreie Grammatik und Kellerautomat · 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!!: Kontextfreie Grammatik und Kleenesche und positive Hülle · Mehr sehen »
Kontextfreie Sprache
In der Theoretischen Informatik ist eine kontextfreie Sprache (CFL) eine formale Sprache, die durch eine kontextfreie Grammatik beschrieben werden kann.
Neu!!: Kontextfreie Grammatik und Kontextfreie Sprache · Mehr sehen »
Landau-Symbole
Landau-Symbole (auch O-Notation) werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben.
Neu!!: Kontextfreie Grammatik und Landau-Symbole · Mehr sehen »
Lineare Sprache
Die Linearen Sprachen (englisch linear languages, LIN) sind ein Fachbegriff aus der Theoretischen Informatik.
Neu!!: Kontextfreie Grammatik und Lineare Sprache · Mehr sehen »
Mehrdeutige Grammatik
Existieren bzgl.
Neu!!: Kontextfreie Grammatik und Mehrdeutige Grammatik · Mehr sehen »
Menge (Mathematik)
Symbolische Darstellung einer Menge von Vielecken leer. Als Menge wird in der Mathematik ein abstraktes Objekt bezeichnet, das aus der Zusammenfassung einer Anzahl einzelner Objekte hervorgeht.
Neu!!: Kontextfreie Grammatik und Menge (Mathematik) · Mehr sehen »
Nichtdeterminismus
Nichtdeterminismus ist ein Konzept aus der theoretischen Informatik, in dem Algorithmen oder Maschinen (meist Turingmaschinen oder endliche Automaten) nicht nur genau eine Berechnung zu einer bestimmten Eingabe durchlaufen können (deterministisch), sondern es bei gleicher Eingabe mehrere Möglichkeiten für den Übergang in den nachfolgenden Zustand gibt.
Neu!!: Kontextfreie Grammatik und Nichtdeterminismus · 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!!: Kontextfreie Grammatik und Nichtterminalsymbol · Mehr sehen »
Parser
Ein Parser („analysieren“, bzw. „Teil“; im Deutschen gelegentlich auch Zerteiler) ist ein Computerprogramm, das in der Informatik für die Zerlegung und Umwandlung einer Eingabe in ein für die Weiterverarbeitung geeigneteres Format zuständig ist.
Neu!!: Kontextfreie Grammatik und Parser · Mehr sehen »
Parsergenerator
Im Compilerbau ist ein Parsergenerator ein Computerprogramm, das auf Grundlage einer Spezifikation einen Parser generiert.
Neu!!: Kontextfreie Grammatik und Parsergenerator · 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!!: Kontextfreie Grammatik und Produktionsregel · Mehr sehen »
Programmiersprache
Quelltext eines Programms in der Programmiersprache C++. Scratch. Eine Programmiersprache ist eine formale Sprache zur Formulierung von Datenstrukturen und Algorithmen, d. h.
Neu!!: Kontextfreie Grammatik und Programmiersprache · Mehr sehen »
Quelltext
siehe eigene Artikel. Quelltext, auch Quellcode oder unscharf Programmcode genannt, ist in der Informatik der für Menschen lesbare, in einer Programmiersprache geschriebene Text eines Computerprogrammes.
Neu!!: Kontextfreie Grammatik und Quelltext · Mehr sehen »
Relation (Mathematik)
Eine Relation („Beziehung“, „Verhältnis“) ist allgemein eine Beziehung, die zwischen Dingen bestehen kann.
Neu!!: Kontextfreie Grammatik und Relation (Mathematik) · 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!!: Kontextfreie Grammatik und Terminalsymbol · Mehr sehen »
Tree Adjoining Grammar
Tree-adjoining grammars (TAG), auch Baumadjunktions-Grammatiken, sind formale Grammatiken, die von Aravind Joshi eingeführt wurden und in der Computerlinguistik für die Beschreibung von natürlichen Sprachen verwendet werden.
Neu!!: Kontextfreie Grammatik und Tree Adjoining Grammar · 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!!: Kontextfreie Grammatik und Tupel · Mehr sehen »
Uwe Schöning
Uwe Schöning (* 28. Dezember 1955 in Ulm) ist ein deutscher Informatiker.
Neu!!: Kontextfreie Grammatik und Uwe Schöning · Mehr sehen »
Wahrscheinlichkeitsmaß
Ein Wahrscheinlichkeitsmaß dient dazu, den Begriff der Wahrscheinlichkeit zu quantifizieren und Ereignissen, die durch Mengen modelliert werden, eine Zahl im Intervall zuzuordnen.
Neu!!: Kontextfreie Grammatik und Wahrscheinlichkeitsmaß · Mehr sehen »
Wort (theoretische Informatik)
In der theoretischen Informatik ist ein Wort eine endliche Folge von Symbolen eines Alphabets.
Neu!!: Kontextfreie Grammatik und Wort (theoretische Informatik) · Mehr sehen »
Wortproblem (Berechenbarkeitstheorie)
Als Wortproblem einer formalen Sprache bezeichnet man in der Theoretischen Informatik das Entscheidungsproblem, zu einem gegebenen Wort festzustellen, ob dieses zur Sprache gehört oder nicht.
Neu!!: Kontextfreie Grammatik und Wortproblem (Berechenbarkeitstheorie) · Mehr sehen »
Zeitkomplexität
Unter der Zeitkomplexität eines Problems wird in der Informatik die Anzahl der Rechenschritte verstanden, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe.
Neu!!: Kontextfreie Grammatik und Zeitkomplexität · Mehr sehen »