matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Schulmathe
  Status Primarstufe
  Status Mathe Klassen 5-7
  Status Mathe Klassen 8-10
  Status Oberstufenmathe
    Status Schul-Analysis
    Status Lin. Algebra/Vektor
    Status Stochastik
    Status Abivorbereitung
  Status Mathe-Wettbewerbe
    Status Bundeswettb. Mathe
    Status Deutsche MO
    Status Internationale MO
    Status MO andere Länder
    Status Känguru
  Status Sonstiges

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenFormale SprachenPumping Lemma kontextfrei
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Formale Sprachen" - Pumping Lemma kontextfrei
Pumping Lemma kontextfrei < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Formale Sprachen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Pumping Lemma kontextfrei: mindestens viele a's wie b's
Status: (Frage) überfällig Status 
Datum: 09:21 Mi 22.05.2013
Autor: bandchef

Aufgabe
Zeigen oder widerlegen Sie, dass die folgende Sprache kontextfrei ist.
[mm] $L=\{w | w \in \{a,b\}^{\*}\text{ mindestens so viele a's wie b's}\}$ [/mm]



Behauptung: L ist nicht kontextfrei.

Sei [mm]L[/mm] eine kontextfreie Sprache, dann gibt es eine
Konstante [mm]n \in \mathbb N[/mm], so dass sich jedes [mm]z \in L[/mm] mit
[mm]|z|\geq n[/mm], so als z=uvwxy schreiben lässt, dass [mm]|vwx|\leq n[/mm],
[mm]|vx|\geq 1[/mm] und [mm]u v^i w x^i y \in L[/mm] für alle [mm]i \geq 0[/mm]
gilt:

wähle: $z=w=aaabbb [mm] \in [/mm] L$

Dieses Wort sollte jedenfalls in der Sprache liegen. Mir ist natürlich auch klar, dass diese Sprache nicht kontextfrei ist. Kann man mit dem PL zeigen, DASS die Sprache kontextfrei IST? Wenn nicht, wie macht man das dann hier?

        
Bezug
Pumping Lemma kontextfrei: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 03:10 Do 23.05.2013
Autor: tobit09

Hallo bandchef,

leider habe ich im Moment nicht die Zeit, mir das genau zu überlegen. Aber ich gehe davon aus, dass diese Sprache kontextfrei ist. Zum Nachweis gebe eine kontextfreie Grammatik $G$ mit $L(G)=L$ an (und weise natürlich $L(G)=L$ nach).

Viele Grüße
Tobias

Bezug
        
Bezug
Pumping Lemma kontextfrei: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 10:20 Fr 24.05.2013
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
        
Bezug
Pumping Lemma kontextfrei: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:04 Fr 24.05.2013
Autor: tobit09

Hallo nochmal,


in der Tat ist die Sprache kontextfrei.

Eine kontextfreie Grammatik für diese Sprache ist z.B. gegeben durch die Produktionsregeln

     [mm] $S\to\varepsilon|aSbS|bSaS|aS$. [/mm]

Den Beweis, dass tatsächlich alle Wörter aus $L$ von dieser Grammatik erzeugt werden können, ist allerdings offenbar aufwendig.

Ob es einen leichteren Weg gibt, die Sprache als kontextfrei nachzuweisen, weiß ich nicht.


Viele Grüße
Tobias

Bezug
                
Bezug
Pumping Lemma kontextfrei: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:39 Fr 24.05.2013
Autor: bandchef

Wir haben die Aufgabe mittlerweile auch in der Schule gelöst. Unser Prof. hat es genauso gemacht, wie du und einfach eine Grammatik erstellt.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Formale Sprachen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.schulmatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]