+ Antworten
Seite 1 von 2 12 LetzteLetzte
Ergebnis 1 bis 20 von 23

Pumping Lemma ...

Eine Diskussion über Pumping Lemma ... im Forum Hausaufgaben. Teil des Reallife-Bereichs; BOAH ich hab Bücher,Skripte,Beispiele,alles aber ich raffs net^^ ... das is so ätzend^^ wir sollen für die Form 01(01)*10(10)* das ...

  1. #1

    Pumping Lemma ...

    BOAH ich hab Bücher,Skripte,Beispiele,alles aber ich raffs net^^ ...
    das is so ätzend^^

    wir sollen für die Form 01(01)*10(10)* das Pumping Lemma anwenden bloss komme ich mit den UVW allein schon net klar 0o ... das is so kacke kann mir das vll. irgendwer so erklären, dass man das versteht ^^ ich raffs 0 und bin da net der einzige

    das einzige was ich weiss, dass man das Splitten muss und n>= 5 is

  2. #2
    UF Supporter
    Avatar von BseBear
    Registriert seit
    27.09.2003
    Ort
    Stuttgart
    Alter
    31
    Beiträge
    3.945
    Name
    Michael
    Nick
    bsebear
    viel Spaß! Das is son Scheiß, dass ichs nach der Klausur schnell wieder vergessen hab...

  3. #3
    Zitat Zitat von BseBear Beitrag anzeigen
    viel Spaß! Das is son Scheiß, dass ichs nach der Klausur schnell wieder vergessen hab...
    naja der Prof meinte bei uns is das net Klausur relevant weils eh keiner richtig kann^^

  4. #4
    (:
    Avatar von Liontiger
    Registriert seit
    09.07.2004
    Ort
    Siegen
    Alter
    29
    Beiträge
    1.038
    Name
    Tim
    Nick
    Liontiger
    Clans
    ToC
    seit wann ist das denn ein Grund was nicht in ner Klausur dranzunehmen

  5. #5
    Zitat Zitat von ToC.Liontiger Beitrag anzeigen
    seit wann ist das denn ein Grund was nicht in ner Klausur dranzunehmen
    hab ich mich auch gefragt aber mir kanns nur recht sein^^

  6. #6
    Das Pumping Lemma ist doch sehr simpel, da man dort immer mit dem gleichen Prinzip ran geht.

    Also wenn ich es richtig sehe ist deine Sprache
    01 (01)* 10 (10)*
    Wobei dies eine ungenügende Defintion ist, da nicht klar ist ob die * gleich oder unterschiedlich laufen dürfen, das solltest du zuvor genau angeben.

    Man kann es auch zusammenfassen als
    (01)+ (10)+

    Dann kannst eine Sbstitution auf 01 mit x und 10 mit y anwenden, hast also
    x+ y+

    Und jetzt schau dir einfach mal ganz allg. Beispiele an.
    Der immer gleiche Trick ist einfach x^n zu wählen, da du damit uv einschränkst wegen |uv| <= n

  7. #7
    UF Supporter
    Avatar von BseBear
    Registriert seit
    27.09.2003
    Ort
    Stuttgart
    Alter
    31
    Beiträge
    3.945
    Name
    Michael
    Nick
    bsebear
    [Klugscheißmodus]+ is kein allgemeines Zeichen zur Beschreibung einer Sprache Deshalb is das so umständlich mitm Sternchen[/Klugscheißmodus]

  8. #8
    Off Topic:
    Wenn ich + Element einer Bijektion zur Menge der natürlichen Zahle außer 0 betrachte ist es ein gültiges Zeichen.
    So wird es auch im Allg. betrachtet.

    Aber ja, generell sollte man Sprachen direkt als Menge definieren, jedoch habe ich hier das + analog zum * gewählt.

    Besser wäre etwas wie
    L := { 01 (01)^m 10 (10)^n | n,m => 0 }
    L' := { (01)^m (10)^n | n,m > 0 }
    L' = L

    Die einzeige Frage ist, ob auch n = m gelten soll.

  9. #9
    also folgendes... wir müssen den Ausdruck 01(01)* 10(10)* Splitten da wir ja sonst mehrere Vs haben
    der Automat is gegegeben gewesen
    ............0.................0............ 1 ........... 0
    (so) <----- (S1) <------ (S2) --->(S3)----> (B)
    ............................------->.....................<----
    ...............................1............................... 0

    n>= 5 .... dann haben wir das Wort

    010110 genommen und sehen das |v|>=1 und |uv|<=n
    so aber wir haben keinen schimmer wie wir das jetzt für n+1 etc. beweisen sollen....


    weiterhin haben wir das Wort 011010 und sehen das |v|>=1 und |uv|<=n
    so aber wir haben keinen schimmer wie wir das jetzt für n+1 etc. beweisen sollen....

    thx schonmal im Vorraus^^ morgen müssen wir abgeben^^ hab zwar schon die nötigen Punkte für die Klausurteilnahme zusammen aber trotzdem will ich das verstehen .... und übrigens werden V1 & V2 auch verschieden wiederholt das is egal
    Geändert von blackplague (26.11.2008 um 16:48 Uhr)

  10. #10
    Sicher, das dies den Automaten darstellen soll ?
    Dann stimmt aber etwas mit der Defintion der Sprache nicht.

    Also ich hätten den Automaten ja so beschrieben

    A := (Z, S, s0, d, F)

    Z := {0, 1}
    S := {A, B, C, D, E, F, G}
    s0 := A
    F := {F}
    d ergibt sich aus der graphischen Darstellung:

    Code:
                        1
                    --------->
    
       0      1      0             0   _   1    
    A ---> B ---> C ---> D     E ---> |F| ---> G
                                       ¯       
                    <---                  <---
                      1                     0
    oder (verkürzt) so:
    A := (Z, S, s0, d, F)

    Z := {0, 1}
    S := {A, B, C, D, E}
    s0 := A
    F := {E}
    d ergibt sich aus der graphischen Darstellung:

    Code:
       0      1      1      0    _ 
    A ---> B ---> C ---> D ---> |E| 
                                 ¯       
             <---          <---
               0             1
    Sei L := { 01 (01)^m 10 (10)^n | n,m => 0 }
    Angenommen du wählst n =5, dann hast du wegen x Element von L und |x| >= 5 als mögliche Werte

    01 10 10 (10)^n , n => 0
    01 01 10 (10)^n , n => 0

    Wegen |uv| <= n, also |uv| <=5 und |v| => 1 bleiben für uv nur folgende Werte übrig:

    0
    01
    011
    010
    0110
    0101
    01101
    01011

    Und wie man sieht kann man eine Folge bestimmen für die es gilt.
    Zum Beispiel:
    0110 mit v = 10
    0101 mit v = 01

    Damit es nicht gilt dürfte es aber gar keine Folge geben für dies es funktioniert, da dieses Lemma nur verlangt, dass es überhaupt eine Folge gibt für die es funktioniert. Wenn man es mit Quantoren schreibt sieht man es deutlicher:
    Sei L keine nicht reguläre Sprache und Z* ihre Zeichenmengen ohne das leere Wort, dann gilt die folgende Aussage.

    Es existiert ein n > 0 für alle x Element von L so das gilt: |x| >= n. Daraus folgt, dass u,v,w Elemente von Z* mit folgenden Eigenschaften existieren: x = uvw und |v| > 0 und |uv| <= n. Des weiteren gilt für alle i >= 0, dass u v^i w ein Element von L ist.


    Das Pumping Lemma gilt i.d.R immer dann nicht, wenn sich die Sprache etwas "merken" müsste, da dies reguläre Sprachen nicht können.
    Wäre also n = m gesetzt, dann würde es nicht funktionieren.

    Es läuft hier also nur auf
    L' := { (01)^m (10)^n | n,m > 0 }
    zurück und nicht auf
    L' := { (01)^n (10)^n | n > 0 }
    weshalb das Pumping Lemma hier funktioniert.

    Ferner kann man sogar sagen, dass es eine reguläre Sprache ist.
    Dies ist aber sogar offensichtlich, da du einen endlichen Automaten konstruieren kannst, denn:

    Eine Sprache L heißt regulär, wenn sie eine der folgenden äquivalenten Bedingungen erfüllt:
    • L wird von einer regulären Grammatik erzeugt.
    • L wird von einem endlichen Automaten akzeptiert.
    • L kann durch einen regulären Ausdruck dargestellt werden.

  11. #11
    jo das Pumping Lemma soll auch funzen^^

    ups sehe gerade der Automat is komisch geworden^^ pfeile müssen anders rum also so ... hatte vorhin kein Grafiktablett^^
    Miniaturansichten angehängter Grafiken Miniaturansichten angehängter Grafiken Klicke auf die Grafik für eine größere Ansicht 

Name:	test.jpg 
Hits:	1 
Größe:	42,7 KB 
ID:	36449  

  12. #12
    Sehr gut, dann bin ich auch nicht verwirrt ^^

  13. #13
    Bärnr Bäär
    Avatar von OliViero
    Registriert seit
    19.10.2008
    Ort
    Zürich
    Alter
    25
    Beiträge
    7.272
    Nick
    Petadroli
    Clans
    cause.F7C
    manchmal frage ich mich warum so Genies in nem Forum rumgammeln wenn sie doch nen Nobelpreis gewinnen könnten
    Unus pro omnibus, omnes pro uno!

  14. #14
    weil sie nett sind
    und gerne anderen Helfen^^

  15. #15
    asozialist
    Avatar von anunknownperson
    Registriert seit
    10.06.2003
    Ort
    wunderreich der nacht
    Beiträge
    1.762
    gibt keine nobelpreise für mathematiker und informatiker...
    The Feynman Problem-Solving Algorithm:
    (1) write down the problem;
    (2) think very hard;
    (3) write down the answer.

  16. #16
    Bärnr Bäär
    Avatar von OliViero
    Registriert seit
    19.10.2008
    Ort
    Zürich
    Alter
    25
    Beiträge
    7.272
    Nick
    Petadroli
    Clans
    cause.F7C
    aber fuer physiker...
    Unus pro omnibus, omnes pro uno!

  17. #17
    asozialist
    Avatar von anunknownperson
    Registriert seit
    10.06.2003
    Ort
    wunderreich der nacht
    Beiträge
    1.762
    die wissen aber nichts über automatentheorie!
    The Feynman Problem-Solving Algorithm:
    (1) write down the problem;
    (2) think very hard;
    (3) write down the answer.

  18. #18
    Administrator
    Avatar von stefros
    Registriert seit
    28.07.2001
    Ort
    Hamburg
    Alter
    33
    Beiträge
    62.610
    Name
    Stefan
    Nick
    stefros1983
    Clans
    United-Forum
    Jo, der reinste Bahnhof hier.

  19. #19
    (:
    Avatar von Liontiger
    Registriert seit
    09.07.2004
    Ort
    Siegen
    Alter
    29
    Beiträge
    1.038
    Name
    Tim
    Nick
    Liontiger
    Clans
    ToC
    ^.^ so gehts mir leider auch o0
    nur das ich den mist verstehen müsste
    machen das zeug in 'Grundlagen der theoretischen Informatik' aber irgendwie is das der Horror

  20. #20
    Wo studierst du denn ?
    Ich höre derzeit auch theo. Informatik, jedoch gehe ich eher selten zur Vorlesung / Übung, da ich es nur als Studienleistung brauche und mich darüber eh nicht prüfen lassen darf
    Außerdem bin ich faul und mache nur was ich machen muss oder will

+ Antworten
Seite 1 von 2 12 LetzteLetzte

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •