Beschreibung regulärer Sprachen mit regulären Ausdrücken

Reguläre Sprachen können außer durch eine Grammatik auch durch sogenannten reguläre Ausdrücke beschrieben werden.

Reguläre Ausdrücke formuliert man mit regulären Operatoren. Die wichtigsten regulären Operatoren sind die folgenden:

• a* - "a-Stern": a beliebig oft (auch 0 mal) hintereinander
• ab - Verkettung: ein a, dann ein b
• a|b - Oder: entweder ein a oder ein b
• Mit runden Klammern () können Teilausdrücke gruppiert werden

(1) α1 = c*h* beschreibt alle Zeichenketten, die zunächst aus beliebig vielen Buchstaben c bestehen und anschließend aus beliebig vielen Buchstaben h. ¹⁾. L₁={ε,c,h,ccch,ccchhh,hhhh,cc,…}.

(2) α2 = c*|h* beschreibt die alle Zeichenketten, die entweder nur aus c's oder nur aus h's bestehen. L₂={ε,c,h,cc,hh,ccc,hhh,…}.

(3) α3 = (c|h)* beschreibt die alle Zeichenketten, die aus beliebig vielen c's und h's bestehen. L₃={ε,c,h,hc,ch,ccc,hchh,…}.

Welche Sprachen werden durch die folgenden regulären Ausdrücke beschrieben? Liste eine Beispielmenge von akzeptierten Wörtern auf, aus der hervorgeht, welche Regeln gelten.

(A) α4 = 01*0 L= {00, 010, 0110, 01110, 011110, 0111110, …}

(B) α5 = (01)* L= {ε, 01, 0101, 010101, 01010101, 0101010101,… }

(C) α6 = 0|(10*)* L= {ε, 0, 1, 10, 100, 1000, 11, 101, 10100, 100100, … }

(D) α7 = (1(110)*)* L= {ε, 1, 1110, 1110110, 11, 11101110, … }

(E) α8 = 1(1*|10*) L= {1, 11, 111, 1111, 11111, 110, 1100, 11000, … }

(F) α9 = 0|1*|10* L= {ε, 0, 1, 11, 111, 1111, 10, 100, 1000, 10000, … }

(G) α10 = 1*0*(0|1) L= { 0, 1, 10, 11, 110, 111, 11001, 1110001, … }

Mit der "Minimalausstattung" von drei Operatoren (ohne die Klammern) lassen sich im Prinzip schon alle regulären Ausdrücke schreiben. Bequemer, kürzer und übersichtlicher geht es, wenn man weitere Operatoren hinzunimmt, hier ist allerdings zu beachten, dass es unterschiedliche "Dialekte" solcher Erweiterungen gibt.

Die meisten Programmiersprachen verfügen über Funktionen oder Bibliotheken, um Strings anhand von regulären Ausdrücken zu finden. Meist gibt es auch weitere Funktionen wie Rückbezüge, mit denen sich komplexe Ersetzungen und Ähnliches realisieren lassen.

Auf der Seite https://regex101.com/ kannst du reguläre Ausdrücke testen. Außerdem werden die Ausdrücke und Matches erklärt.

Öffne die Seite https://regex101.com/ und sorge dafür, dass die Einstellungen wie im Screenshot zusehen angepasst sind²⁾

Überprüfe jetzt deine Ergebnisse aus Aufgabe 1, indem du den regulären Ausdruck in die Eingabezeile "regular Expression" schreibst und die zu testenden Wörter der regulären Sprache in das Feld "Test String", pro Zeile ein Wort.

Es soll erkannt werden, ob ein String das korrekte Format für eine Telefonnummer hat.

Eine korrekte Telefonnummer besteht aus:

• Einer Vorwahl, die mit einer 0 beginnt und danach mindestens eine andere Ziffer enthält.
• Einem der folgenden Zeichen zur Abtrennung der Vorwahl: -, / oder Leerzeichen
• Einer mindestens einstelligen Zahl, die nicht mit 0 beginnt.