Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Regulären Ausdruck konstruieren
Autor
Universität/Hochschule Regulären Ausdruck konstruieren
weilbaum
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 14.02.2021
Mitteilungen: 7
  Themenstart: 2021-02-21

Hallo zusammen, ich hänge im Moment daran fest, einen regulären Ausdruck zu der Sprache über $\Sigma=\{a,b,c\}$ zu konstruieren in der zwischen zwei $a$'s immer mindestens ein $b$ und ein $c$ stehen und zwischen zwei $b$'s immer mindestens ein $c$. Mein Problem dabei ist die Abhängigkeit zwischen den beiden Anforderungen, denn sobald ich zwischen $a$'s mindestens ein $b$ setze, muss ich darauf achten auch das $c$ zwischen die $b$'s zu setzen. Zuerst habe ich Ausdrücke konstruiert zu den beiden Teilanforderungen. Für die $b$'s: \(\beta = ba^*c^+a^*b\). Für die $a$'s: \(\alpha = a((c^*\beta c^+)\cup(c^+\beta c^*))a\) Mein ganzer Ausdruck setzt sich dann aus der Hülle der Teilausdrücke und $c$ Präfixen/Suffixen zusammen, also \(c^* \alpha^* c^*\) oder komplett ausgeschrieben: \[ c^* ( a((c^*ba^*c^+a^*b c^+)\cup(c^+ba^*c^+a^*b c^*))a )^* c^* \] Das kommt mir insgesamt mehr als suboptimal vor, gar nicht davon zu reden, dass ja auch noch Fehler drin sein können. Meine Fragen daher: Kann das stimmen? Kann man das vereinfachen? Gibt es eine empfehlenswertere Herangehensweise als ich das gemacht habe? Einen schönen Rest-Sonntag! weilbaum


   Profil
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Informatik-Rentner
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 29.10.2015
Mitteilungen: 62
Wohnort: Essen
  Beitrag No.1, eingetragen 2021-03-21

Sind nur Vereinigung und Konkat. und Stern als Operatoren erlaubt? Mit not wäre es einfacher. Ich versuche das immer über die Konstruktion eines endlichen Automaten zu lösen, der diese Sprache erkennt. Skizze: Wenn der Automat ein a akzeptiert, wechselt er in einen Zustand, wo er als nächstes kein a, aber ein b oder c akzeptieren darf/kann. Wenn er ein b akzeptiert, wechselt er in einen Zustand, wo er als nächstes kein b akzeptieren darf/kann. Den Automaten kann man auf einen minimalen reduzieren, falls man unsicher ist und aus dem fertigen Automaten kann ich leicht die Sprache ableiten.


   Profil
piteo
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 12.09.2014
Mitteilungen: 26
  Beitrag No.2, eingetragen 2021-04-05

Hallo! Mir scheint der Fall abcab nicht abgedeckt zu sein, obwohl er die Bedingungen erfüllt. Gruß Pit.


   Profil

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]