Inhaltsverzeichnis
35 Beziehungen: Akzeptieren (Automaten- und Komplexitätstheorie), Automat (Informatik), Chomsky-Hierarchie, Determinismus (Algorithmus), Deterministisch kontextfreie Sprache, Endlicher Automat, Englische Sprache, Fachliteratur, Formale Grammatik, Formale Sprache, Grammatik, Gzip, Homomorphismus, Jeffrey Ullman, John E. Hopcroft, Karl Heinz Böhling, Kellerautomat, Klasse (Mengenlehre), Komplement (Mengenlehre), Kontextfreie Grammatik, Kontextfreie Sprache, Kontextsensitive Sprache, Menge (Mathematik), Nichtdeterminismus, Palindrom, Produktionsregel, Pumping-Lemma, Reguläre Grammatik, Reguläre Sprache, Sprache, Stapelspeicher, Theoretische Informatik, Wachsend kontextsensitive Sprache, Wort (theoretische Informatik), Zeichenkette.
Akzeptieren (Automaten- und Komplexitätstheorie)
Akzeptieren ist ein Begriff aus der Automaten- und Komplexitätstheorie, Teilgebieten der theoretischen Informatik.
Sehen Lineare Sprache und Akzeptieren (Automaten- und Komplexitätstheorie)
Automat (Informatik)
Ein Automat oder eine abstrakte Maschine ist in der Informatik, speziell in der Automatentheorie, das Modell eines digitalen, zeitdiskreten Rechners.
Sehen Lineare Sprache und Automat (Informatik)
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.
Sehen Lineare Sprache und Chomsky-Hierarchie
Determinismus (Algorithmus)
Ein deterministischer Algorithmus ist ein Algorithmus, bei dem nur definierte und reproduzierbare Zustände auftreten.
Sehen Lineare Sprache und Determinismus (Algorithmus)
Deterministisch kontextfreie Sprache
Eine deterministisch kontextfreie Sprache ist eine Sprache, die von einem deterministischen Kellerautomaten akzeptiert wird.
Sehen Lineare Sprache und Deterministisch kontextfreie Sprache
Endlicher Automat
Abbildung 1: Beispiel eines EA, der eine Tür beschreibt Ein endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat;, FSM) ist ein Modell eines Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen.
Sehen Lineare Sprache und Endlicher Automat
Englische Sprache
Die englische Sprache (Eigenbezeichnung: IPA) ist eine ursprünglich in England beheimatete germanische Sprache, die zum westgermanischen Zweig gehört.
Sehen Lineare Sprache und Englische Sprache
Fachliteratur
Die Fachliteratur, je nach Definition auch Fachprosa genannt, ist ein Teilgebiet der nichtbelletristischen Literatur.
Sehen Lineare Sprache und Fachliteratur
Formale Grammatik
Formale Grammatiken sind mathematische Modelle von Grammatiken, die zur eindeutigen Erzeugung und Beschreibung formaler Sprachen dienen.
Sehen Lineare Sprache und Formale Grammatik
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.
Sehen Lineare Sprache und Formale Sprache
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.
Sehen Lineare Sprache und Grammatik
Gzip
gzip ist ein freies Kompressionsprogramm, das – ebenso wie das entsprechende Dateiformat gzip – praktisch für alle Computerbetriebssysteme verfügbar ist (unter den Bedingungen der GPL auch im Quelltext).
Sehen Lineare Sprache und Gzip
Homomorphismus
Als Homomorphismus (von „gleich“ und morphé „Form, Gestalt“; nicht zu verwechseln mit Homöomorphismus) werden in der Mathematik Abbildungen bezeichnet, die eine (oft algebraische) mathematische Struktur erhalten bzw.
Sehen Lineare Sprache und Homomorphismus
Jeffrey Ullman
Jeffrey David Ullman (* 22. November 1942 in New York City) ist ein US-amerikanischer Informatiker.
Sehen Lineare Sprache und Jeffrey Ullman
John E. Hopcroft
John E. Hopcroft, 2009 John Edward Hopcroft (* 7. Oktober 1939 in Seattle) ist ein amerikanischer Informatiker.
Sehen Lineare Sprache und John E. Hopcroft
Karl Heinz Böhling
Karl Heinz Böhling (* 13. Mai 1930 in Leer; † 23. März 2016) war ein deutscher Mathematiker, Informatiker und Hochschullehrer.
Sehen Lineare Sprache und Karl Heinz Böhling
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.
Sehen Lineare Sprache und Kellerautomat
Klasse (Mengenlehre)
Als Klasse gilt in der Mathematik, Klassenlogik und Mengenlehre eine Zusammenfassung beliebiger Objekte, definiert durch eine logische Eigenschaft, die alle Objekte der Klasse erfüllen.
Sehen Lineare Sprache und Klasse (Mengenlehre)
Komplement (Mengenlehre)
In der Mengentheorie und anderen Teilgebieten der Mathematik sind zwei verschiedene Komplemente definiert: Das relative Komplement und das absolute Komplement.
Sehen Lineare Sprache und Komplement (Mengenlehre)
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.
Sehen Lineare Sprache und Kontextfreie Grammatik
Kontextfreie Sprache
In der Theoretischen Informatik ist eine kontextfreie Sprache (CFL) eine formale Sprache, die durch eine kontextfreie Grammatik beschrieben werden kann.
Sehen Lineare Sprache und Kontextfreie Sprache
Kontextsensitive Sprache
Die kontextsensitiven Sprachen (englisch context-sensitive languages, abgekürzt durch CSL) sind eine Klasse der formalen Sprachen, einem Teilgebiet der Theoretischen Informatik.
Sehen Lineare Sprache und Kontextsensitive Sprache
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.
Sehen Lineare Sprache und Menge (Mathematik)
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.
Sehen Lineare Sprache und Nichtdeterminismus
Palindrom
Als Palindrom („rückwärts laufend“) werden in der Sprachwissenschaft Wörter, Wortreihen oder Sätze bezeichnet, die rückwärts gelesen genau denselben Text oder zumindest einen Sinn ergeben.
Sehen Lineare Sprache und Palindrom
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.
Sehen Lineare Sprache und Produktionsregel
Pumping-Lemma
Das Pumping-Lemma bzw.
Sehen Lineare Sprache und Pumping-Lemma
Reguläre Grammatik
Eine reguläre Grammatik ist in der Informatik eine formale Grammatik vom Typ 3 der Chomsky-Hierarchie.
Sehen Lineare Sprache und Reguläre Grammatik
Reguläre Sprache
In der theoretischen Informatik ist eine reguläre Sprache oder reguläre Menge oder erkennbare Sprache eine formale Sprache, die einigen Einschränkungen unterliegt.
Sehen Lineare Sprache und Reguläre Sprache
Sprache
Unter Sprache versteht man im allgemeinen Sinn alle komplexen Systeme der Kommunikation.
Sehen Lineare Sprache und Sprache
Stapelspeicher
Vereinfachte Darstellung eines Stacks mit den Funktionen Push (drauflegen) und Pop (herunternehmen) In der Informatik bezeichnet ein Stapelspeicher oder Kellerspeicher (kurz Stapel oder Keller, häufig auch mit dem englischen Wort Stack bezeichnet) eine häufig eingesetzte dynamische Datenstruktur.
Sehen Lineare Sprache und Stapelspeicher
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.
Sehen Lineare Sprache und Theoretische Informatik
Wachsend kontextsensitive Sprache
Wachsend kontextsensitive Sprachen (abgekürzt: GCSL) sind ein Begriff aus der Theorie der Formalen Sprachen, einem Teilgebiet der Theoretischen Informatik.
Sehen Lineare Sprache und Wachsend kontextsensitive Sprache
Wort (theoretische Informatik)
In der theoretischen Informatik ist ein Wort eine endliche Folge von Symbolen eines Alphabets.
Sehen Lineare Sprache und Wort (theoretische Informatik)
Zeichenkette
Eine Zeichenkette, Zeichenfolge, Zeichenreihe oder ein String (aus dem Englischen) ist in der Informatik eine endliche Folge von Zeichen (z. B. Buchstaben, Ziffern, Sonderzeichen und Steuerzeichen) aus einem definierten Zeichensatz.
Sehen Lineare Sprache und Zeichenkette
Auch bekannt als Lineare Grammatik.