Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Regulären Ausdruck angeben
Autor
Universität/Hochschule J Regulären Ausdruck angeben
Schutze
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 23.10.2020
Mitteilungen: 47
  Themenstart: 2021-04-27

Hallo, Ich habe ein Problem mit folgender Aufgabe: Gegeben ist das Alphabet {a, b, c, d}. Ich soll nun einen regulären Ausdruck angeben, sodass: a) Die Folge "aa" genau zweimal in den Wörtern enthalten ist. (aaa ist keine doppelte Folge) b) Die Folge "bab" mindestens dreimal in den Wörtern enthalten ist (babab ist keine doppelte Folge) Ich habe nun schon recht viel ausprobiert, aber letzten Endes leider keine Ahnung, wie ich hierbei vorgehen soll. In einer weiteren Aufgabe soll ich zu den beschriebenen Sprachen EA angeben. Das konnte ich soweit lösen und habe nun für a) den riesen Umweg genommen und aus meinem DEA einen regulären Ausdruck hergeleitet, aber das ist erstens mehr als umständlich, zweitens wird der Ausdruck natürlich extrem lang und unübersichtlich und drittens denke ich, dass das nicht der vorgesehene Lösungsweg ist, auch wenn er natürlich ein richtiges Ergebnis produziert. In den Vorlesungen habe ich bislang nur ziemlich einfache reguläre Ausdrücke kennengelernt (sowas wie c(ab|aba)*) und mir sind soweit keine Operatoren bekannt, durch die ich z.B. diese "genau" oder "mindestens" Anforderung erfüllen kann. Vielleicht kann mir ja jemand dabei helfen bzw. mich in die richtige Richtung lenken. Viele Grüße


   Profil
matroid
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.03.2001
Mitteilungen: 14387
Wohnort: Solingen
  Beitrag No.1, eingetragen 2021-04-27

Hallo Schutze, stöber doch mal hier https://www.sttmedia.de/regulaere-ausdruecke Gruß Matroid


   Profil
Sismet
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 22.03.2021
Mitteilungen: 129
Wohnort: Heidelberg
  Beitrag No.2, eingetragen 2021-04-27

\(\begingroup\)\(\newcommand{\IQ}{\mathbb{Q}} \newcommand{\IR}{\mathbb{R}} \newcommand{\IZ}{\mathbb{Z}} \newcommand{\IN}{\mathbb{N}} \newcommand{\IC}{\mathbb{C}} \newcommand{\ba}{\begin{align*}} \newcommand{\ea}{\end{align*}} \newcommand{\be}{\begin{equation*}} \newcommand{\ee}{\end{equation*}} \newcommand{\wo}{\backslash} \) Hey, hier mal eine mögliche Herangehensweise für die b), das Prinzip ist aber auch für die a) anwendbar: -Jedes Wort der Sprache sieht so aus: $w_1babw_2babw_3babw_4$ mit $w_1,w_2,w_3,w_4\in \{a,b,c,d\}^*$ -Wähle also den regulären Ausdruck $\beta\alpha\beta\alpha\beta\alpha\beta$ mit $\alpha=(bab)$ und $\beta=(a|b|c|d)^*$. Dann garantiert dir $\alpha$ dass $bab$ mind. 3 mal vorkommt und $\beta$ sichert dir, dass du alle Wörter mit dieser Eigenschaft darstellen kannst. -Jetzt kann es aber sein, dass du dadurch eventuell mehr Wörter bilden kannst als du möchtest, dann kannst du anfangen die einzelnen $\alpha$ und $\beta$ unabhängig voneinander zu verändern um das gewünschte Ergebnis zu erhalten. Grüße Sismet\(\endgroup\)


   Profil
Schutze
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 23.10.2020
Mitteilungen: 47
  Beitrag No.3, vom Themenstarter, eingetragen 2021-04-28

Danke für den Link, Matroid. Da werde ich später mal reinschauen. Danke auch dir, Sismet. Wenn ich mir das so anschaue, stelle ich fest, dass ich bei b) einfach zu kompliziert gedacht habe. Viele Grüße


   Profil
Schutze hat die Antworten auf ihre/seine Frage gesehen.
Schutze hat selbst das Ok-Häkchen gesetzt.

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-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]