Informatik-Blog

In der  Theoretischen Informatik  ist eine  kontextfreie Sprache  ( englisch   context-free language ,  CFL ) eine  formale Sprache , die durch eine  kontextfreie Grammatik  beschrieben werden kann. Eine kontextfreie Grammatik erlaubt einen definierten Leseprozess (Interpretation) von Ausdrücken einer formalen Sprache. Dabei kann zum einen entschieden werden, ob ein Ausdruck den Regeln der Grammatik entspricht, und zum anderen im Verlauf der Analyse ein  Syntaxbaum  erstellt werden. Ein Programm, das dies leistet, heißt  Parser . Parser werden insbesondere zur Verarbeitung von  Programmiersprachen  verwendet. Auch in der  Computerlinguistik  versucht man,  natürliche Sprachen  durch Regeln kontextfreier Grammatiken zu beschreiben. Kontextfreie Sprachen werden auch als  Typ-2 -Sprachen der  Chomsky-Hierarchie  bezeichnet. Die Klasse aller kontextfreien Sprachen beinhaltet die...

Ein  nichtdeterministischer endlicher Automat  ( NEA ;  englisch   nondeterministic finite automaton ,  NFA ) ist ein  endlicher Automat , bei dem es für den Zustandsübergang mehrere gleichwertige Möglichkeiten gibt.  Ein  deterministischer endlicher Automat  ( DEA ;  englisch   deterministic finite state machine  oder  deterministic finite automaton ,  DFA ) ist ein  endlicher Automat , der unter Eingabe eines Zeichens seines Eingabealphabetes (den möglichen Eingaben) von einem Zustand, in dem er sich befindet, in einen eindeutig bestimmten Folgezustand wechselt. Von jedem (Final-)Zustand  {\displaystyle q_{n}\in \{F,Q\}}  muss für jedes Zeichen des Eingabealphabets  {\displaystyle \Sigma }  ein Übergang in einen Folgezustand existieren. [1]   Unterschiede Im Unterschied zum  deterministischen endlichen Automaten  sind die Möglichkeiten nicht eindeutig, dem Automaten ist...

https://www.standardsicherung.schulministerium.nrw.de/cms/zentralabitur-gost/faecher/getfile.php?file=4761 Darstellung, wenn man ein Wort widerlegen soll: A -> brB -> brbrB -> brbrbl -> brbrblfsD -> Widerspruch! Es gibt keine Produktion mit dem Nichtterminal D auf der linken Seite, deren rechte Seite mit dem Terminal fs beginnt. Daher lässt sich das Wort nicht ableiten und gehört somit nicht zur Autosprache. Überprüfung ob eine Grammatik rechtsregulär ist: Eine Grammatik ist rechtsregulär, wenn für alle Produktionen folgende Regeln gelten: 1. Die linke Seite einer Produktion besteht nur aus einem Nichtterminal 2. Die rechte Seite der Produktion enthält das leere Wort, ein Terminal oder in Terminal gefolgt von einem Nichtterminal. Die Grammatik L(G) erfüllt beide Kriterien für eine rechtsreguläre Grammatik. Auf der linken Seite der Produktionen stehen nur Nichtterminale und auf der rechten Seite entweder das leere Wort oder ein Terminal gefolgt von einem...

  Unter Synatx versteht man allgemein ein Regelsystem zur Kombination elementarer Zeichen zu zusammengesetzten Zeichen in natürlichen oder künstlichen Zeichensystemen. Die Syntaxregeln der Grammatik der deutschen Sprache geben, z.B. an, in welcher Reihenfolge die Satzglieder (elementar) in einem Satz (zusammengesetzt) angeordnet werden dürfen. Eine formale Sprache L über einem Alphabet ∑ ist eine Teilmenge aller möglichen Verknüpfungen des Alphabets. Neben der Bezeichnung Nicht-Terminal (N) wird auch häufig der Begriff Variable (V) verwendet. Ebenso wird die Menge der Terminale auch mit ∑ angegeben, da die Terminale die Symbole des Alphabets der Sprache sind. Die Grammatik der lal-Sprache wird formal wie folgt dargestellt: G lal = (N, T, S, P) Die Grammatik ist eine 4-Tupel N = {S, A, B} Die Nichtterminale sind Platzhalter für die Erzeugung von Worten. S steht als Platzhalter für die erste, A für die zwei...

Formal definiert man einen Kellerautomaten als 7-Tupel (Q, S ,K,δ,q 0 ,#,F): -          Q ist eine nicht leere, endliche Menge von Zuständen -         S ist ein nicht leeres, endliches Eingabealphabet. -         K ist ein nicht leeres, endliches Kelleralphabet -         d ist die Übergangsfunktion, die jeder Kombination aus einem Zustand, einem Eingabezeichen und einem Kellerzeichen einen Nachfolgezustand und eine Kelleroperation zuordnet -         q 0 ϵ Q ist der Startzustand -         # ϵ K ist das Anfangssymbol im Keller -         F ist die Menge der akzeptierenden Endzustände, wobei F eine Teilmenge von Q ist Der im Beispiel erläuterte Kellerautomat für die Sprache L = {a n b n |n ϵ N} lässt sich somit wie folgt formal defi...