Beweisen Sie, dass eine Sprache, die $ gcd $ verwendet, nicht kontextfrei ist

  • Wie würden Sie nachweisen, dass die folgende Sprache nicht kontextfrei ist?

    $$ L = \ {a ^ nb ^ m | \, gcd (n, m) = 1 \} $$

    Ich habe den Verdacht, dass die Lösung das Pumping-Lemma verwendet, aber ich bin nicht sicher, wie sie angewendet werden soll |>

    18 July 2012
    Kaveh
2 answers
  • Sei $ p $ die Pumplänge, die vom Pumpemaxma garantiert wird (für kontextfreie Sprachen). Dann wählen wir $ m \ neq n $ so, dass $ m, n \ geq p $ und beide Primzahlen sind. Dann ist eindeutig $ s = a ^ {n} b ^ {m} \ in L $.

    Durch das pumpende Lemma können wir $ s $ so teilen, dass $ s = uvxyz $ und

    1. $ | vxy | \ leq p $
    2. $ | vy | \ geq 0 $
    3. $ s '= uv ^ {i} xy ^ {i} z \ in L $ für alle $ i \ in \ mathbb {N} $

    Für diese Sprache gibt es drei ähnliche Fälle und einen trivialen Fall. Der triviale Fall ist, dass entweder $ v $ oder $ y $ sowohl $ a $ s als auch $ b $ s enthält. In diesem Fall hat $ s '$ nicht die richtige Reihenfolge und daher $ s' \ notin L $.

    Die nichttrivialen Fälle:

    1. $ v $ und $ y $ sind beide Zeichenfolgen von $ a $ s, dann erhalten wir, wenn wir $ s $ pumpen, $ s '= a ^ {n + ik} b ^ {n} $ wobei $ k \ geq 1 $. Dann ist $ s '\ in L $, wenn $ gcd (n + ik, m) = 1 $ ist, jedoch hat die modulare Gleichung $ n + ik \ equiv 0 (m) $ die Lösung $ i \ equiv nk ^ {- 1}. (m) $, und da $ m $ Primzahl ist, wird garantiert, dass $ k ^ {- 1} $ existiert. Daher würde jedes Element der Residuenklasse $ i \ equiv nk ^ {- 1} (m) $ $ gcd (n + ik, m) & gt; 1 $. Ergo $ s '\ notin L $.

      Kurze Version: Wir können den String so pumpen, dass $ n + ik $ ein Vielfaches von $ m $ für jedes $ k $ ist mit $ 1 \ leq k \ leq p & lt; m, n $ (was wir zu Beginn festgelegt haben).
    2. $ v $ und $ y $ sind beide Zeichenfolgen von $ b $, aber dieser Fall ist der Fall Nur den symmetrischen Fall zu Fall 1, so leiten wir auch in diesem Fall einen Widerspruch ab.
    3. $ v = a ^ {k} $ und $ y = b ^ {h} $ für einige $ k $ und $ h $ mit $ 1 \ leq k + h \ leq p $. Wenn wir dann pumpen, erhalten wir $ s '= a ^ {n + ik} b ^ {m + ih} $. Jetzt hat $ s '\ in L $, falls $ n + ik \ equiv m + ih (m) $ keine Lösung hat, aber wie Sie sicher von hier aus sehen können, ergibt das Umordnen nur $ n + i (k + h) \ äquiv 0 (m) $, und wie zuvor hat dies die Lösung $ i \ equiv n (k + h) ^ {- 1} (m) $. Also leiten wir wieder einen Widerspruch ab.

    Daher gibt es in $ L $ mindestens eine Zeichenfolge, die nicht gemäß dem pumpenden Lemma unterteilt werden kann und habe noch eine

    18 July 2012
    Raphael
  • Trick: Eine Sprache ist nicht Kontextfreie Sprache , wenn sie mehr als ein Mal dieselbe Comaprision hat. Für Instanz: L = {a ^ nb ^ c ^ n | n & gt; 0} Wie Sie wissen, ist dies nicht kontextfrei. Warum? Wie Sie sehen können, sollte die Anzahl von b gleich sein wie die Nummer eines "This is first Comarision" und danach wieder die Anzahl von c soll die gleiche sein wie die Anzahl von b oder die Anzahl der vorherigen a. Hierfür ist ein Stapel von 2 erforderlich gleiche Anzahl von Vorkommen von a und b.so ist dies nicht "pda", da Sie wissen, dass pda nur einen Stapel hat ...

     Another Beautifull Example: L={a^nb^na^mb^m|m,n >0} Tell me weather this language is CFL or not. 
     

    Erneut hier Suchen Sie nach der Anzahl der Vergleiche zwischen derselben Entität: Hier sollte die Anzahl von b gleich der Anzahl von a sein. Im Fall von a^nb^n... Hier ist nur eine Kompromiss zwischen "n" jetzt zum a ^ mb ^ m gehen Auch hier hängt die Anzahl von b von der Zahl a ab, wobei die Anzahl von keinem von irgendjemandem abhängt. Also zwischen a und b für die Leistung m gibt es nur einen Vergleich, deshalb ist es so ist L={a^nb^na^mb^m|m,n >0} ist CFL

     Ex: L = {a^nb^ma^nb^m | m>n>0} Tell me weather It's CFL or not By seeing number of comaprision Answer: Yes This is CFL
     

    Nun kommen wir zu Ihren Fragen:

    L = {a ^ n, b ^ m | gcd (n, m) = 1}

    Hier können wir den Wert von n und m nicht auswählen, sodass gcd immer 1 ist .... Finden Sie hier eine Kompromittierung:

      What Will be the value of m,n ???
     It's depend upon condition that whenever you will choose value of m, or n it shuld be either > and equal to m in case of value selection for m or same for value selection for m (This is first comarision between m and n or reverse for selecting value)  Now think 
     

    Eine andere Entscheidung: GCD von m, n soll sein 1 (Dies ist ein weiterer Kompromiss für m, n), so dass hier zwei Kompromisse vorhanden sind, zeigen, dass es sich nicht um CFL handelt.

      And Acrding to pumping Lemma Theorem:
        1)Select any string belongs to L
        2)devide it in xYz part make sure that Y shuld not have o length.
        3)Take any value of "i" acrding  to your wish.
        4)make x(Y)^iz and check weather it's belong to L if not then it will prove that it is not regular. i>and equal to 1.
     
    < Denken Sie: Können Sie einen PDA konstruieren? Dafür haben Sie einen einzigen Stapel ... Defensiv Sie werden zu einem Schluss kommen ... Wenn Sie immer noch nicht verstanden haben, schreibe ich mehr für Sie ...

    16 April 2012