Informatiker Board | formale Sprachen | Regulären Ausdruck für Sprache finden

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Regulären Ausdruck für Sprache finden

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Regulären Ausdruck für Sprache finden

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

Regulären Ausdruck für Sprache finden

Zitatantwort auf diesen Beitrag erstellen

Hallo!!!

Ich soll einen regulären Ausdruck für die Sprache $[latex] L=\{w \in \{1,2,4,5,7,9\}^{*}, w \text{ ist eine Dezimalzahl, die durch 7 teilbar ist} \} [/latex]$ finden, mir fällt aber keiner ein. Könnt ihr mir helfen?

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von marie m: 25.01.2014 01:44.

25.01.2014 01:42

Nehmen Sie marie m in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Ich glaube, dass das nicht möglich ist. Leider habe ich momentan keine Ahnung wie man den Beweis dazu führt.

Ist gegeben, dass es einen solchen Automaten gibt?

VG,

Karlito

25.01.2014 15:28

Nehmen Sie Karlito in Ihre Freundesliste auf

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

Ich soll zeigen dass die Sprache regulär ist und ich dachte ich könnte es zeigen indem ich einen regulären Ausdruck finde. Gibt es einen anderen Weg um zu zeigen dass die Sprache regulär ist?

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von marie m: 25.01.2014 15:38.

25.01.2014 15:37

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Mein momentaner gedanklicher Ansatz:

Es kann jeden erdenklichen Suffix geben und es kann jeden erdenklichen Präfix geben. Es gibt weiterhin eine unendliche Zahl an kombinationen mit einem Infix und der Infix hängt immer von Prä- und Suffix ab.... Ich glaube das kann man mit einem regulären Ausdruck nicht bewerkstelligen.

Anderere Ansätze:
- Alternierende Quersumme, wie in Wikipedia: Fehlende fähigkeit zu Rechen mit Regulären ausdrücken
- Alternative Methode lt Wikipedia: Ebenfalls nicht möglich, da Rechnen nicht möglich...

Fragen:
- welche Eigenschaften sind an der gegebenen MEnge an Ziffern bezüglich der Teilbarkeit durch 7 gegeben?

VG,

Karlito

25.01.2014 15:45

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Zitat:

Original von marie m
Ich soll zeigen dass die Sprache regulär ist und ich dachte ich könnte es zeigen indem ich einen regulären Ausdruck finde. Gibt es einen anderen Weg um zu zeigen dass die Sprache regulär ist?

Es gibt noch die Möglichkeit, dass man einen akzeptierenden Automaten erstellt. Soweit ich weiß, ist das jedoch äquivalent zu einem regulären Ausdruck. Ich befürchte, die Sprache ist nicht regulär...

VG,

Karlito

25.01.2014 15:48

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

Ich habe einen Automaten gemalt aber ich will es noch mit einen anderen Weg machen.

25.01.2014 16:28

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Dann scanne doch bitte mal den Automaten.

VG,

Karlito

25.01.2014 16:50

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

(S. Anhang) Der Startzustand ist 0.

marie m hat dieses Bild (verkleinerte Version) angehängt:

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von marie m: 25.01.2014 17:05.

25.01.2014 17:03

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hefitg! Wenn ich dazu komme, prüfe ich den mal...

VG,

Karlito

25.01.2014 17:22

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

Ok!
Könnte man auch anstatt den Automaten zu malen einfach die verbale Beschreibung des Automaten geben?

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von marie m: 25.01.2014 21:40.

25.01.2014 21:40

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Wenn es konsisten und wasserdicht ist, ist das auch immer ein Weg, den man gehen kann.

Manchmal macht es das sogar besser Nachvollziehbar. Vielleicht ist eine Kombination sogar das beste...

VG,

Karlito

25.01.2014 21:46

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Tut mir leid, ich habe einen Fehler gefunden. Beispiel: 21.

Zustand 0 -> Zustand 1 -> Zustand 1 (Kein Finalzustand)

Ich glaube weiterhin, dass man keinen Automaten konstruieren kann, sorry Augenzwinkern

Aber leider kann ich es (noch) nicht beweisen.

VG,

Karlito

26.01.2014 22:48

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Regulären Ausdruck für Sprache finden