Die Mathe-Redaktion - 17.10.2017 07:50 - Registrieren/Login
Auswahl
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 Okt. 2017

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

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Satz von Myhill Nerode
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Satz von Myhill Nerode
Chris77223
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 18.05.2017
Mitteilungen: 6
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2017-05-18


Ich möchte mit dem Satz von Myhill und Nerode zeigen, dass die Sprache L={a^(b)|b>=1 ist eine Zweierpotenz } regulär ist oder dass sie nicht regulär ist.
Meine Ideen:
Bisher nicht so viele, ich würde aber sagen, dass es hier nur eine Äquivalenzklasse gibt, nämlich L und dass sich die Sprache also immer nur mit weiteren a's erweitert und und der Index somit endlich ist und die Sprache deshalb regulär. Oder liege ich hier völlig falsch?



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 1141
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2017-05-18


Erweitern mit dem Suffix "a" führt nicht zwangsläufig zu einem Wort der Sprache.

Bspw. gehören die Worte "a" und "aa" unterschiedlichen Äquivalenzklassen an, da sich ersteres mit "a" erweitern lässt, letzteres hingegen nicht.


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



  Profil  Quote  Link auf diesen Beitrag Link
Chris77223
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 18.05.2017
Mitteilungen: 6
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2017-05-18


Aber das würde heißen, dass die Sprache doch nicht regulär ist, weil es unendlich viele Äquivalenzklassen gibt. Würde das als Argumentation reichen oder was müsste ich da formal als Beweis hinschreiben? Das ist mein erster Beweis mit diesem Satz und ich bin deshalb noch sehr unsicher. Schon jetzt danke für die Hilfe.



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 1141
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2017-05-19


Man könnte deine Überlegung sicherlich noch etwas formalisieren, aber prinzipiell stimmt das.
Es gibt unendlich viele Äquivalenzklassen, daher ist die Sprache nicht regulär.


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



  Profil  Quote  Link auf diesen Beitrag Link
Chris77223
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 18.05.2017
Mitteilungen: 6
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2017-05-19


Okay, danke für deine Hilfe.



  Profil  Quote  Link auf diesen Beitrag Link
Chris77223 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]