Die Mathe-Redaktion - 25.03.2017 06:55 - Registrieren/Login
Auswahl
Schwarzes Brett
Fragensteller hat Anwort gelesen, aber bisher nicht weiter reagiert2017-03-24 23:29 bb
MPCT 2017 Planung
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Feb. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 319 Gäste und 1 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Informatik » Theoretische Informatik » kontextfreie Sprachen
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule kontextfreie Sprachen
Austinn
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.01.2017
Mitteilungen: 35
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2017-02-16 16:05


hallo zusammen,

ich habe folgende Sprache:
∑={a, b, c}
Alle ∑-Wörter gerader Länge, in denen "a" allenfalls in der zweiten Worthälfte vorkommt.

Rein von meiner Intuition her würde ich sagen, dass diese Sprache keine reguläre ist.
Ich habe mir überlegt
L={b^2n c^n a^n}
(weiß nicht, ob das bis jetzt so stimmt, da ich etwas verwirrt bin, weil ja Wörter auch mit c anfangen können, also L={c^2n b^n a^n} )

Wenn das bis jetzt so stimmt, wäre einer so nett und würde mir zeigen, wie ich mit dem pumping lemma beweisen kann, dass diese Sprache nicht regulär ist?



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 917
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2017-02-16 16:29


Mein Vorgehen wäre:


Die Sprache kann man wie folgt schreiben:

<math>(b|c)^n(a|b|c)^n</math>

Wir nehmen jetzt an, dass die Sprache regulär ist.
Also existiert eine natürliche Zahl <math>p</math>, ab dieser Länge man alle Wörter zerlegen und "pumpen" kann.

Wie betrachten nun das Wort
<math>w=b^pa^p=xyz</math>
Dieses liegt in der Sprache und besitzt eine Länge <math>\geq p</math>.
Da <math>|xy|\leq p</math> gilt, ergibt sich <math>y=b+</math>.
Damit liegt das Wort <math>xz</math> jedoch nicht in der Sprache, da es entweder ungerade ist oder ein oder mehrere <math>a</math> in der 1. Hälfte besitzt.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



  Profil  Quote  Link auf diesen Beitrag Link
Austinn
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.01.2017
Mitteilungen: 35
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2017-02-16 16:52


Warum betrachten wir das Wort <math>w=b^pa^p=xyz</math>?
Muss denn "c" auch nicht im Wort liegen?



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 917
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2017-02-16 18:56


Du willst doch alle Wörter über dem Alphabet <math>\Sigma=\{a;b;c\}</math>, die eine gerade Länge besitzen und bei denen erst in der zweiten Hälfte das <math>a</math> auftauchen kann?

Falls ja, schreibt mal exemplarisch alle Wörter mit 2 Buchstaben auf, die diese Forderung erfüllen.

Falls nein, poste die Aufgabe bitte im Originallaut.



  Profil  Quote  Link auf diesen Beitrag Link
Austinn
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.01.2017
Mitteilungen: 35
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2017-02-16 22:38


2017-02-16 18:56 - DerEinfaeltige in Beitrag No. 3 schreibt:
Falls ja, schreibt mal exemplarisch alle Wörter mit 2 Buchstaben auf, die diese Forderung erfüllen.

Das wären ba und ca.

Das was mich verwirrt, es können doch auch Wörter wie bbca in der Sprache sein, oder?

<math>w=b^pa^p=xyz</math> hier betrachten wir doch keine c's,
bin deswegen etwas verwirrt...



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 917
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2017-02-16 22:48


2017-02-16 22:38 - Austinn in Beitrag No. 4 schreibt:
2017-02-16 18:56 - DerEinfaeltige in Beitrag No. 3 schreibt:
Falls ja, schreibt mal exemplarisch alle Wörter mit 2 Buchstaben auf, die diese Forderung erfüllen.

Das wären ba und ca.

Das was mich verwirrt, es können doch auch Wörter wie bbca in der Sprache sein, oder?

<math>w=b^pa^p=xyz</math> hier betrachten wir doch keine c's,
bin deswegen etwas verwirrt...


Die Wörter mit 2 Buchstaben stimmen schon nicht.
Es gibt nicht nur 2, sondern 6 verschiedene.
ba, bb, bc, ca, cb, cc

Und zum Pumping-Lemma:
Die Zerlegung muss für ein beliebiges Wort funktionieren.
Also wählt man für den Widerspruchsbeweis ein möglichst Einfaches, das sich nicht zerlegen lässt.
Du könntest bspw. genausogut die Klasse <math>(b|c)^pa(a|b|c)^{p-1}</math> betrachten. Das ändert nichts an obigem Beweis. Keines dieser Wörter lässt sich so zerlegen, dass <math>xz</math> in der Sprache liegt.



-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



  Profil  Quote  Link auf diesen Beitrag Link
Austinn
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.01.2017
Mitteilungen: 35
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2017-02-17 13:45


verstehe...

Kannst du mir vielleicht noch mit dieser Sprache helfen.
Ich vermute, dass die Sprache kontextfrei ist, da ich keinen Automaten dafür finden kann, aber mir fällt auch keine Beweisidee ein.
Was meinst du?



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 917
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2017-02-17 14:27


Da das Wort wieder aus zwei voneinander abhängigen Hälften besteht, geht das ganz ähnlich wie oben. (eigentlich ist es hier sogar einfacher)

1. Nimm an, die Pumpkonstante <math>p</math> existiert.
2. Betrachte ein möglichst einfaches Wort der Sprache mit einem Präfix der Länge <math>p</math>.
3. Überlege, ob man dieses Wort zerlegen und pumpen kann. Falls du <math>w</math> geschickt gewählt hast, sollte man leicht zeigen können, dass es i.A. keine solche Zerlegung gibt.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



  Profil  Quote  Link auf diesen Beitrag Link
Austinn
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.01.2017
Mitteilungen: 35
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2017-02-17 17:51


wäre hier ein Wort beispielsweise <math>w=0^p2^p=xyz</math> ?



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 917
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2017-02-18 09:44


Ja, sicherlich.
Jetzt führe den Beweis zu Ende.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



  Profil  Quote  Link auf diesen Beitrag Link
Austinn hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]