Sind kontextfreie Sprachen Entscheidbar?

Inhaltsverzeichnis:

1. Sind kontextfreie Sprachen Entscheidbar?
2. Wann ist eine Grammatik eindeutig?
3. Wann ist eine Grammatik mehrdeutig?
4. Wann ist eine Sprache nicht regulär?
5. Wann ist ein Automat deterministisch?
6. Wie funktioniert ein Kellerautomat?

Sind kontextfreie Sprachen Entscheidbar?

Der Schnitt zweier kontextfreier Sprachen ist nattuerlich entscheidbar: jede einzelne ist entscheidbar => gibt einband-DTM1,2 die die sprachen L1, L2 entscheiden (inbesondere sich nie aufhaengen).

Wann ist eine Grammatik eindeutig?

Eindeutige Grammatik Eine kontextfreie Grammatik G ist dann eindeutig, wenn für jedes Wort aus L(G) genau eine mögliche Ableitung aus dem Startsymbol existiert. ... Damit er nicht "hängen bleibt", muss die Grammatik eindeutig sein; es darf nur ein Weg vom Tokenstrom zum Startsymbol existieren.

Wann ist eine Grammatik mehrdeutig?

Eine Grammatik, die für mindestens ein Wort zwei Syntaxbäume hat, heißt mehrdeutige Grammatik. Wenn es für jedes erzeugte Wort eine einzige (eindeutig bestimmte) Linksableitung, d.h. also auch nur einen einzigen Syntaxbaum gibt, nennen wir die Grammatik eindeutig.

Wann ist eine Sprache nicht regulär?

Reguläre Sprachen können von endlichen Automaten erkannt werden. ... Wenn also eine Sprache L={aib2i|i∈N} L = { a i b 2 i | i ∈ N } beschrieben wird, müsste gezählt werden, wie oft a vorkommt. a kann aber beliebig oft vorkommen. Das ist ein Indiz dafür, dass es sich nicht um eine reguläre Sprache handelt.

Wann ist ein Automat deterministisch?

Deterministische endliche Automaten – kurz DEA (Informatik) oder DFA (Englisch: deterministic finite state machine)– sind endlichen Automaten . ... Hierbei gilt, dass ein determinisitischer endlicher Automat immer eindeutig ist, bei welcher Eingabe welcher Zustandsübergang ausgeführt wird.

Wie funktioniert ein Kellerautomat?

Ein (Keller-)Automat liest eine aus einzelnen Zeichen bestehende Eingabe und akzeptiert (oder erkennt) diese – oder auch nicht. Die Menge der akzeptierten Eingaben bildet die durch den Automaten definierte Sprache. Der nichtdeterministische Kellerautomat erkennt genau die kontextfreien Sprachen (Typ 2, vgl.