Regulärer Ausdruck für Wort w ist durch 20 teilbar

Question

Aufgabe:

Zu folgender Sprache einen regulären Ausdruck angeben:

{w є {0, …, 9}* | w ist durch 20 teilbar}, Wort: 4200

Des weiteren soll zu gegebener Sprache eine rechts oder linkslineare Grammatik angegeben werde.

Problem/Ansatz:

Meine Idee ist folgende, jedoch bin ich mir nicht sicher ob es richtig ist:

regulärer Ausdruck = 2|4|6|8(Ɛ|0|2|4|6|8)*0*

Answer 1

Wenn du das letzte Sternchen in ein + änderst und das ε weglässt, stimmt es.

Grüße

Nachtrag 10.12.2019: Verbesserung: 

(0-9)*(0|2|4|6|8)0+ aufgrund der Diskussion in den Kommentaren

Comments

Wie ist in diesem Automaten die Zahl 500 mitgemeint?

500 ist durch 20 teilbar?

---

So habe ich es verstanden. Es geht wohl kaum um die Anzahl der Ziffern oder die Quersumme.

---

Ich verstehe

regulärer Ausdruck = 2|4|6|8(Ɛ|0|2|4|6|8)*0*

nicht.

Problem: Hier kommt gar keine 5 vor, es sei denn, die ist in Epsilon versteckt.

---

Verdammt.

Da habe ich garnicht dran gedacht.

Na, dann muss der RegEx um folgendes erweitert werden:

| (1-9)+(0|2|4|6|8)0+

---

Habe das nun oben in deiner Antwort ergänzt. Am besten liest man aber unsere Diskussion, damit man versteht, was da überlegt wurde.

---

Das war jetzt etwas ungeschickt, der reg ex sollte nur erweitert und nicht ersetzt werden. Ich bearbeite nochmal ;)

---

Alles klar. Anscheinend ist RegEx = Regulärer Ausdruck :)

---

Regular Expression, genau.

---

2|4|6|8(Ɛ|0|2|4|6|8)*0* | (1-9)+(0|2|4|6|8)0+

5560,

5040,

48580

3820

und

479500

sind auch durch 20 teilbar.

Wie genau sind die alle mitgemeint?

---

Nach dem *0* kommt eine Alternative:

Die sagt dann, wähle irgendeine Zahl zwischen 0-9 und füge anschließend eine gerade Zahl oder 0 und eine 0 an.

Man kann den RegEx kürzen (das hätte ich vorher machen sollen, damit es zu keinem Missverständnis kommt.)

Schau ihn dir nochmal an:

(0-9)+(0|2|4|6|8)0+

---

1. Heisst das, dass  (1-9)+(0|2|4|6|8)0+ nun vollständig ist?

+ steht für beliebig viele (auch 0 oder eine negative Anzahl ?) Wiederholungen von dem unmittelbar vorher? Das würde einleuchten ohne das Plus am Schluss. Hast du dann auch die durch 20 teilbaren Zahlen, die kleiner als 99 sind mit dabei?

2. Was war vorher mit den Sternchen gemeint?

---

Ahhhh!!! Ich hab ein Plus mit Sternchen vertauscht.. Heute ist aber auch der Wurm drin. Entschuldige bitte das Wirrwar.

Das erste Plus muss zum Sternchen.

(0-9)*(0|2|4|6|8)0+

Dann bedeutet es:

Wähle eine Zahl zwischen 0 und 9 und dies beliebig oft oder kein mal (->Sternchen).

Dann entweder 0, 2, 4, 6 oder 8 und dann mindestens eine aber maximal unbegrenzt Nullen (-> Plus).

Der Senkrechtstrich ist die Alternative, die runden Klammern schließen einen Bereich ein, für den die Zeichen Alternative (|), Möglichkeit (?), beliebige (auch keine) Wiederholung (*) und ein oder mehrere Wiederholungen (+).

---

Danke für die Erklärung der Schreibweise.

Jetzt fehlen mir nur noch die negativen durch 20 teilbaren Zahlen. Da keine Grundmenge angegeben ist, kannst du aber die natürlichen Zahlen (inklusive Null) durchaus voraussetzen.

---

Bezüglich der Klammern:

Es gibt da unterschiedliche Meinungen, am häufigsten zu finden sind:

Runde Klammern, um Teile des RegEx als Block zusammenzufassen,

Eckige Klammern, um Zahlenbereiche darzustellen

Und geschweifte Klammern, um eine Anzahl anzugeben.

Negative Zahlen kannst so berücksichtigen:

-?[0-9]*(0|2|4|6|8)0+

Einfach ein fakultatives Minus vorsetzen.

Wenn du dazu nochmal was zum nachschlagen brauchst:

http://www.regexe.de/hilfe.jsp