Formale Sprachen #37 - Kontextfrei geschnitten regulär

Wir sehen uns an, warum eine kontextfreie Sprachen geschnitten mit einer regulären Sprache wieder eine kontextfreie Sprache ergibt. Man kann dies mit einem Produktautomaten zeigen, der sich gleichzeitig wie der Kellerautomat und der endliche Automat verhält und das Eingabewort nur akzeptiert, falls beide Automaten das Wort akzeptieren.

[@sebbsebb9787]

Hey! danke für die tollen und sehr hilfreichen Videos!

[@rebeccah2415]

Wenn man eigentlich für seine letzte Prüfung im Studium lernen sollte, aber neue Theoretische Informatik-Videos von Leif viel spannender sind :D

[@ParalyticAngel]

Wie sieht der Produktautomat des Schnitts einer regulären Sprache zu einem Kellerautomaten dann aus?

[@SumbaSlice]

Danke für den Beweis. Hab es endlich verstanden. Gehe ich recht in der Annahme, dass der Schnitt einer regulären und einer kontextfreien Sprache also kontextfrei ist aber NICHT REGULÄR?

[@NLogSpace]

Herauszufinden ob das so ist oder nicht ist eine super Übungsaufgabe!

[@SumbaSlice]

@@NLogSpace Ich frage, weil das eine Altklausur-Aufgabe war. Meine Lerngruppe und ich kommen auf unterschiedliche Ergebnisse. Ich dachte, wenn da einer Licht ins Dunkel bringen kann, dann NLogSpace

[@CptCool117]

@@SumbaSlice Die Aussage reguläre Sprache geschnitten kontextfreie Sprache ergibt nicht eine reguläre Sprache stimmt nicht. Gegenbeispiel: Nimm die reguläre Sprache L_1 = {ab}, die also nur das Wort ab enthält, und die kontextfreie Sprache L_2 = {a^n b^n}. Wenn wir L_1 und L_2 schneiden, dann erhalten wir die Sprache L_3 = {ab}. Die ist regulär, und weil gilt, dass reguläre Sprachen Teilmenge von den kontextfreien Sprachen ist, ist sie auch kontextfrei. 😇
Ich hätte noch eine Anschlussfrage: Man soll die folgende Aussage bewerten: "Der Schnitt einer regulären Sprache und einer kontextfreien Sprache ist immer regulär". Wie kann ich begründen, dass das nicht immer gilt? @NLogSpace

[@boroxx8863]

bester mann!

[@iharbakhanovich]

Vielen Dank. Super

[@arnoclaude317]

Ich verstehe das Argument nicht ganz , ob zwei reguläre/kontextfreie Sprachen unter Schnitt abgeschlossen sind. Wenn man zwei kontextfreie Sprachen hat, dann sind doch beide eine Teilmenge aller kontextfreien Sprachen, oder? Und wenn das der Fall ist, dann befindet sich unter Anderem ihr Schnitt trivialerweise auch in der Menge der kontextfreien Sprachen?
Wo ist mein Denkfehler?

[@NLogSpace]

Der Denkfehler: Wenn wir eine Menge von Sprachen (in diesem Fall die Menge aller kontextfreien Sprachen) haben, dann muss nicht unbedingt der Schnitt von zwei Sprachen aus dieser Menge wieder in dieser Menge liegen.
Beispiel: Eine Menge M enthält zwei Sprachen:
M = { {ab,bc}, {bc,cd} }
Der Schnitt der beiden ist die Sprache {bc}. Aber die Sprache {bc} ist nicht in M enthalten.

[@arnoclaude317]

@@NLogSpace Macht Sinn. Ich habs mir bisher nur geometrisch anhand eines Venn Diagramms vorgestellt. Danke für die blitzschnelle Antwort!

[@boroxx8863]

Ich hab leider folgendes Problem: ich muss beweisen anhand einer context freien und regulären Sprache dass,
L1(a^i b^i+j a^j | i,j >=0 ) kontextfrei ist.
Dazu habe ich mir überlegt ich nehme die Sprache L1 (a^i b^i a^j ) die Contextfrei ist und Schneide Sie. aber ich weiß leider nicht mit welcher Requlären Sprache oder Regulärem Ausdruck um auf die obige SPrache zu kommen...

[@e3e3onjz61]

Tolles Video - vielen Dank!
Wenn die beiden Sprachen keine gemeinsamen Worte besitzen, dann ist ihr Schnitt die leere Menge und diese ist eine reguläre Sprache.
Somit ist die Aussage "Kontextfrei geschnitten reguläre ist wieder kontextfrei" nicht allgemein gültig, oder?

[@NLogSpace]

Danke!
Doch, die Aussage ist allgemein gültig. Jede reguläre Sprache ist auch kontextfrei.

[@e3e3onjz61]

@@NLogSpace Ach ja natürlich! :x

[@thecouchpotato4652]

Leider war das kein Beweis, dass der Schnitt von kontextfreien Sprachen und regulären Sprachen wieder kontextfrei ist, sondern ein Beispiel. Ich habe nach einem formalen Beweis gesucht...

[@NLogSpace]

Wenn Du einen formal aufgeschriebenen Beweis suchst, dann schau am besten in irgendein Lehrbuch zu dem Thema. Auf diesem Kanal erkläre ich nur die Beweisideen, meistens anhand von Beispielen.

[@ceyda8592]

Das ganze ist super verständlich aber wie ist es eigentlich mit Regulär \ Kontextfrei ? Das wäre ja im Prinzip regulär schnitt komplement von kontextfrei. Aber danach weiß ich nicht weiter da kontextfreie sprachen ja nicht unter dem komplement abgeschlossen sind

[@NLogSpace]

Regulär \ Kontextfrei ist im Allgemeinen nicht kontextfrei. Das sieht man leicht, wenn man weiß, dass kontextfreie Sprachen nicht unter Komplement abgeschlossen sind.

[@MIKEZAY]

Kannst ein video machen zu Vereinigung zweier Kellerautomaten 🥺