Sprache ist kontextfrei?
Gefragt von: Meinhard Thiele B.Sc. | Letzte Aktualisierung: 14. Juli 2021sternezahl: 4.8/5 (43 sternebewertungen)
In der Theoretischen Informatik ist eine kontextfreie Sprache (englisch context-free language, CFL) eine formale Sprache, die durch eine kontextfreie Grammatik beschrieben werden kann.
Wann ist eine Sprache Kontextfrei?
Eine Sprache L heißt kontextfrei, wenn es eine kontextfreie Grammatik G gibt, die L erzeugt, d.h. wenn L(G) = L. Beachte: Nur Variablen X dürfen ersetzt werden: der Kontext von X spielt keine Rolle. Kontextfreie Grammatiken sind mächtig, weil rekursive Definitionen ausgedrückt werden können.
Ist eine reguläre Sprache Kontextfrei?
Es gibt keine kontextfreie Sprache, die von einer regulären Grammatik erzeugt werden kann. Die Menge der kontextfreien Sprachen, die von einer regulären Grammatik erzeugt werden können, entspricht genau der Menge der regulären Sprachen.
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 nicht kontextfrei?
Eine Grammatik ist eine kontextfreie Grammatik (CFG), wenn die endliche Menge der Produktionen eingeschränkt ist auf P ⊆ VN × V ∗. Eine kontextfreie Produktion (A, λ) wird als λ-Produktion bezeichnet. Besitzt eine CFG keine λ-Produktionen, so heißt sie λ-frei. Eine Regel (u, v) ∈ P wird üblicherweise als u → v notiert.
Reguläre und kontextfreie Sprachen
38 verwandte Fragen gefunden
Wann ist eine kontextfreie Grammatik mehrdeutig?
Definition: Linksableitung Sei G eine kontextfreie Grammatik, x ∈ L(G). ... Definition: Mehrdeutigkeit Eine Grammatik heißt genau dann mehrdeutig, wenn es (mindestens) ein x ∈ L(G) gibt, zu dem es mindestens zwei Linksableitungen gibt.
Wann ist eine Grammatik regulär?
Reguläre Grammatik – Allgemein
Die Reguläre Grammatik stellt eine Typ 3 Grammatik der Chomsky-Hierarchie dar und erzeugt reguläre Sprachen. Es ist ein 4-Tupel, bestehend aus der Menge der Terminalsymbole, der Nichtterminale und der Produktionen, sowie einem Startsymbol.
Ist die Klasse der Entscheidbaren Sprachen abgeschlossen unter konkatenation?
Satz: Die Klasse der regulären Sprachen ist abgeschlossen unter allen booleschen Operationen, d.h. insbesondere unter Vereinigung, Schnitt und Komplement. Außerdem ist sie abgeschlossen unter Produkt (= Konkatenation), sowie unter der Sternoperation (und unter vielen weiteren Operationen).
Wie erkennt man reguläre Sprachen?
Eine Sprache ist regulär, wenn: die Sprache von einer regulären Grammatik erzeugt wird; endliche Automaten sie akzeptieren; und die Sprache durch einen regulären Ausdruck dargestellt werden kann.
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 akzeptiert ein Kellerautomat?
Kellerautomaten akzeptieren, wenn sowohl die Eingabe als auch der Keller leer sind. Die nichtdeterministischen PDAs akzeptieren die kontextfreien Sprachen. Es gibt kontextfreie Sprachen, die von keinem deterministischen PDA akzeptiert werden.
Wann ist eine Grammatik eindeutig?
Eine Grammatik heißt eindeutig, wenn es für jedes Wort w ∈ L(G) genau eine Linksableitung gibt. Nicht eindeutige Grammatiken nennt man auch mehrdeutig.
Was ist Linksrekursion?
linksrekursiv. Bedeutungen: [1] Informatik: eine Produktion oder eine Grammatik in den Formale Sprache betreffend.
Ist die Klasse der rekursiv Aufzählbaren Sprachen abgeschlossen unter Vereinigung?
Die Menge der rekursiv aufzählbaren Sprachen ist gegenüber Kleenescher Hüllenbildung, Konkatenation, Schnitt und Vereinigung abgeschlossen, nicht jedoch gegenüber dem Komplement.
Ist die Klasse der rekursiv Aufzählbaren Sprachen abgeschlossen unter Durchschnitt?
In welchen mengentheoretischen Eigenschaften unterscheiden sich rekursive Sprachen und rekursiv aufzählbare Sprachen? Die rekursiven Sprachen sind unter Komplementbildung abgeschlossen, die rekursiv aufzählbaren nicht (vgl. Punkt 8). Jede der beiden Sprachklassen ist unter Schnitt und Vereinigung abgeschlossen.
Sind alle Sprachen Entscheidbar?
Beweise. In den Übungsaufgaben wird gezeigt, dass zu jeder Grammatik G die Sprache L(G) entscheidbar ist.
Sind endliche Sprachen regulär?
Endliche Sprachen sind regulär
regulär ist. Man kann also sagen: Jede Sprache, die endlich viele Wörter enthält, ist regulär.
Was bedeutet das Wort regulär?
herkömmlich, hergebracht, althergebracht, gewohnt, gewöhnlich, gewohnheitsmäßig, geläufig, gebräuchlich, traditionell, konventionell, eingeführt, erprobt, klassisch, normal, regulär, gängig, gang und gäbe, nach alter Väter...
Was ist eine Grammatik Informatik?
Sie werden in der theoretischen Informatik, insbesondere in der Berechenbarkeitstheorie, und im Compilerbau zum einen angewendet, um eindeutig festzulegen, ob ein Wort Element einer Sprache ist und zum anderen, um Eigenschaften dieser formalen Sprachen zu untersuchen bzw. ... zu beweisen.