www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 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
Forum "Formale Sprachen" - Pumping-Lemma
Pumping-Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Formale Sprachen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Pumping-Lemma: Beweis
Status: (Frage) überfällig Status 
Datum: 21:20 Di 15.05.2012
Autor: bandchef

Aufgabe
Beweisen oder widerlegen Sie mit dem Pumping-Lemma, dass die folgende Sprache regulär ist:

[mm] $L_1 [/mm] = [mm] \{ 0^j1^k0^l | j=k+l \text{ für }j,k,l \in \mathbb N \}$ [/mm]

So, dann fang ich nochmal an:

Vermutung: L ist regulär!

Sei [mm] $n_0$ [/mm] die Konstante des PL, dann gilt: [mm] $n_0 \in \mathbb [/mm] N$ mit [mm] $n_0 \geq [/mm] 1$:

$w = [mm] 0^{n_0}1^k0^l$ [/mm]



Für alle $w [mm] \in [/mm] L$ mit $|w| [mm] \geq n_0$ [/mm] mit $u,v,w [mm] \in \Sigma^{\star}_{\text{Bool}}$ [/mm] und $|uv| [mm] \leq [/mm] 1$ und $v [mm] \neq \epsilon$ [/mm] gilt die Zerlegung:

$w = [mm] \underbrace{0^{m_1}}_{\text{=u}} \underbrace{0^{m_2}}_{\text{=v}} \underbrace{1^k 0^l}_{\text{=w}}$ [/mm] mit [mm] $m_1+m_2=j$ [/mm]



Betrachte: $uv^iw [mm] \in [/mm] L$ mit i=2: $uv^2w = [mm] 0^{m_1}(0^{m_2})^21^k0^l [/mm] = [mm] 0^{m_1}0^{2m_2}1^k0^l [/mm] = ...?$



Und ab hier weiß ich dann nicht mehr weiter. Laut der Sprachdefinition von oben hängt die Anzahl der ersten Nulln [mm] $0^j$ [/mm] von der Anzahl der Zeichen [mm] $1^k$ [/mm] und [mm] $0^l$ [/mm] ab. Wenn ich jetzt bspw. k=2 und l=3 wähle, dann berechnet sich ja j=k+l=5. Dann sieht das Wort w ja so aus: 0000011000.

        
Bezug
Pumping-Lemma: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:20 Do 17.05.2012
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
        
Bezug
Pumping-Lemma: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:41 Mo 21.05.2012
Autor: sandp

hey,
Mit dem PL kann man nur zeigen, dass eine Sprache nicht regulär ist, die andere Richtung funktioniert nicht.
Um zu zeigen, dass eine Sprache regulär ist kannst du ja zum Beispiel eine Grammatik dafür angeben.
Gruß

Bezug
                
Bezug
Pumping-Lemma: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:27 Do 24.05.2012
Autor: bandchef

Ja, das weiß ich. Genau deswegen hab ich ja in der Vermutung geschrieben, dass ich vermute, dass L regulär ist. Dann kommt beim PL-Beweis raus, dass es eben nicht regulär ist. Und dann hab ich das gegenteil Bewiesen.

Ist das so richtig?

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


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]