Results 1 to 18 of 18

Thread: Pumping Lemma

  1. #1

    Title
    Veteran
    Join Date
    May 2017
    Posts
    2
    Thanks Thanks Given 
    0
    Thanks Thanks Received 
    0
    Thanked in
    0 Posts

    Pumping Lemma

    Halli Hallo,

    warum muss das Pumping Lemma für reguläre Sprachen auf alle regulären Sprachen zutreffen?

    gibts keine kontextfreien Sprachen, auf die das Pumping Lemma für reguläre Sprachen zutrifft?

    Danke Sehr!
    /

  2. #2
    1student's Avatar
    Title
    Super Moderator
    Join Date
    Aug 2011
    Location
    Disneyland Vienna
    Posts
    1,718
    Thanks Thanks Given 
    291
    Thanks Thanks Received 
    1,014
    Thanked in
    867 Posts
    Quote Originally Posted by hiroot View Post
    warum muss das Pumping Lemma für reguläre Sprachen auf alle regulären Sprachen zutreffen?
    Da das Pumping Lemma für reguläre Sprachen eine Eigenschaft beschreibt, die auf alle regulären Sprachen zutrifft.

    Quote Originally Posted by hiroot View Post
    gibts keine kontextfreien Sprachen, auf die das Pumping Lemma für reguläre Sprachen zutrifft?
    Überlege dir am besten, was auf kontextfreie Sprachen zutreffen muss, damit sie das Pumping Lemma für reguläre Sprachen erfüllen.
    "If you can dream it, you can do it."
    -- Walt Disney
    ʘ‿ʘ

  3. #3

    Title
    Principal
    Join Date
    May 2011
    Posts
    63
    Thanks Thanks Given 
    13
    Thanks Thanks Received 
    7
    Thanked in
    3 Posts
    Hallo,
    Bitte um Hilfe
    Was wählt man hier als w ?
    L={ a^n 1^k b^m | k>=0, n<m }
    Last edited by kave; 02-06-2017 at 15:51.

  4. #4
    1student's Avatar
    Title
    Super Moderator
    Join Date
    Aug 2011
    Location
    Disneyland Vienna
    Posts
    1,718
    Thanks Thanks Given 
    291
    Thanks Thanks Received 
    1,014
    Thanked in
    867 Posts
    Quote Originally Posted by kave View Post
    Hallo,
    Bitte um Hilfe
    Was wählt man hier als w ?
    L={ a^n 1^k b^m | k>=0, n<m }
    Hallo, die Bedingung n < m ist hier wesentlich.
    Das Wort w muss so gewählt werden, dass n < m erfüllt ist (und w von der Schranke des Pumping Lemmas abhängt), gleichzeitig soll die Bedingung nach dem "Aufpumpen" nicht mehr gelten.
    "If you can dream it, you can do it."
    -- Walt Disney
    ʘ‿ʘ

  5. #5

    Title
    Principal
    Join Date
    May 2011
    Posts
    63
    Thanks Thanks Given 
    13
    Thanks Thanks Received 
    7
    Thanked in
    3 Posts
    Quote Originally Posted by 1student View Post
    Hallo, die Bedingung n < m ist hier wesentlich.
    Das Wort w muss so gewählt werden, dass n < m erfüllt ist (und w von der Schranke des Pumping Lemmas abhängt), gleichzeitig soll die Bedingung nach dem "Aufpumpen" nicht mehr gelten.
    w = a^l b^l+1 ?

  6. #6
    1student's Avatar
    Title
    Super Moderator
    Join Date
    Aug 2011
    Location
    Disneyland Vienna
    Posts
    1,718
    Thanks Thanks Given 
    291
    Thanks Thanks Received 
    1,014
    Thanked in
    867 Posts
    Quote Originally Posted by kave View Post
    w = a^l b^l+1 ?
    Sieht gut aus, wenn mit "l" die Konstante des Pumping Lemmas gemeint ist.
    "If you can dream it, you can do it."
    -- Walt Disney
    ʘ‿ʘ

  7. The Following User Says Thank You to 1student For This Useful Post:


  8. #7

    Title
    Principal
    Join Date
    May 2011
    Posts
    63
    Thanks Thanks Given 
    13
    Thanks Thanks Received 
    7
    Thanked in
    3 Posts
    Quote Originally Posted by 1student View Post
    Sieht gut aus, wenn mit "l" die Konstante des Pumping Lemmas gemeint ist.
    Danke

  9. #8

    Title
    Principal
    Join Date
    May 2011
    Posts
    63
    Thanks Thanks Given 
    13
    Thanks Thanks Received 
    7
    Thanked in
    3 Posts
    Click image for larger version. 

Name:	19451952_10213048708078230_853137910_o.jpg 
Views:	78 
Size:	100.4 KB 
ID:	25791

  10. #9
    1student's Avatar
    Title
    Super Moderator
    Join Date
    Aug 2011
    Location
    Disneyland Vienna
    Posts
    1,718
    Thanks Thanks Given 
    291
    Thanks Thanks Received 
    1,014
    Thanked in
    867 Posts
    Quote Originally Posted by kave View Post
    Click image for larger version. 

Name:	19451952_10213048708078230_853137910_o.jpg 
Views:	78 
Size:	100.4 KB 
ID:	25791
    "If you can dream it, you can do it."
    -- Walt Disney
    ʘ‿ʘ

  11. #10

    Title
    Principal
    Join Date
    May 2011
    Posts
    63
    Thanks Thanks Given 
    13
    Thanks Thanks Received 
    7
    Thanked in
    3 Posts
    Click image for larger version. 

Name:	Screen Shot 2018-01-16 at 1.20.16 PM.png 
Views:	41 
Size:	73.1 KB 
ID:	25897Click image for larger version. 

Name:	Screen Shot 2018-01-16 at 1.22.00 PM.png 
Views:	36 
Size:	63.5 KB 
ID:	25898

    Hallo,
    Bei Aufgabe 1.5 c) , ist das Wort w (a^m b^2m a^2m b^m ) sicher aus L ?

  12. #11
    1student's Avatar
    Title
    Super Moderator
    Join Date
    Aug 2011
    Location
    Disneyland Vienna
    Posts
    1,718
    Thanks Thanks Given 
    291
    Thanks Thanks Received 
    1,014
    Thanked in
    867 Posts
    Quote Originally Posted by kave View Post
    Bei Aufgabe 1.5 c) , ist das Wort w (a^m b^2m a^2m b^m ) sicher aus L ?
    Ja, das Wort liegt in L.
    u = am bm
    "If you can dream it, you can do it."
    -- Walt Disney
    ʘ‿ʘ

  13. #12

    Title
    Principal
    Join Date
    May 2011
    Posts
    63
    Thanks Thanks Given 
    13
    Thanks Thanks Received 
    7
    Thanked in
    3 Posts
    Quote Originally Posted by 1student View Post
    Ja, das Wort liegt in L.
    u = am bm
    ah ja
    Danke!

  14. #13

    Title
    Principal
    Join Date
    May 2011
    Posts
    63
    Thanks Thanks Given 
    13
    Thanks Thanks Received 
    7
    Thanked in
    3 Posts
    Click image for larger version. 

Name:	27046484_10214896562193428_1174978055_o.jpg 
Views:	42 
Size:	115.7 KB 
ID:	25899

    @1student
    Kannst du mir bitte kurz bestätigen, ob das stimmt?
    Danke!

  15. #14
    1student's Avatar
    Title
    Super Moderator
    Join Date
    Aug 2011
    Location
    Disneyland Vienna
    Posts
    1,718
    Thanks Thanks Given 
    291
    Thanks Thanks Received 
    1,014
    Thanked in
    867 Posts
    Quote Originally Posted by kave View Post
    @1student
    Kannst du mir bitte kurz bestätigen, ob das stimmt?
    Danke!
    Wieso ist dein z plötzlich nach vorne gewandert?
    Es wäre wahrscheinlich auch gut irgendwo zu vermerken, was k ist.
    "If you can dream it, you can do it."
    -- Walt Disney
    ʘ‿ʘ

  16. #15

    Title
    Veteran
    Join Date
    Jan 2018
    Posts
    1
    Thanks Thanks Given 
    0
    Thanks Thanks Received 
    0
    Thanked in
    0 Posts
    Bitte um Hilfe

  17. #16
    1student's Avatar
    Title
    Super Moderator
    Join Date
    Aug 2011
    Location
    Disneyland Vienna
    Posts
    1,718
    Thanks Thanks Given 
    291
    Thanks Thanks Received 
    1,014
    Thanked in
    867 Posts
    Quote Originally Posted by annakieu541 View Post
    Bitte um Hilfe
    Dann poste bitte eine konkrete Frage. Leider kann ich keine Gedanken lesen.
    "If you can dream it, you can do it."
    -- Walt Disney
    ʘ‿ʘ

  18. The Following User Says Thank You to 1student For This Useful Post:


  19. #17

    Title
    Veteran
    Join Date
    Mar 2018
    Posts
    1
    Thanks Thanks Given 
    0
    Thanks Thanks Received 
    0
    Thanked in
    0 Posts
    Click image for larger version. 

Name:	Screen Shot 2018-03-14 at 10.42.51.jpg 
Views:	16 
Size:	66.1 KB 
ID:	25914

    Musterlösung SS17

    Könnte man hier auch mit w=b^m c^m beweisen?
    Nachdem |xy|<=m und w=b^m c^m kann xy nur aus Symbolen b bestehen

    zB i = 2, xy^2 z = b^m+|y| c^m , was aber nicht der Fall ist! Widerspruch

  20. #18
    1student's Avatar
    Title
    Super Moderator
    Join Date
    Aug 2011
    Location
    Disneyland Vienna
    Posts
    1,718
    Thanks Thanks Given 
    291
    Thanks Thanks Received 
    1,014
    Thanked in
    867 Posts
    Quote Originally Posted by younggod View Post
    Click image for larger version. 

Name:	Screen Shot 2018-03-14 at 10.42.51.jpg 
Views:	16 
Size:	66.1 KB 
ID:	25914

    Musterlösung SS17

    Könnte man hier auch mit w=b^m c^m beweisen?
    Nachdem |xy|<=m und w=b^m c^m kann xy nur aus Symbolen b bestehen

    zB i = 2, xy^2 z = b^m+|y| c^m , was aber nicht der Fall ist! Widerspruch
    Willkommen im Forum!

    Ja, das wäre genauso möglich.
    "If you can dream it, you can do it."
    -- Walt Disney
    ʘ‿ʘ

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •