Suche nach regulären Ausdrücken für anders beschriebene Sprachen

Question

Schreiben Sie einen regulären Ausdruck für {a b}, wobei {a b} die Alphabetmenge ist:

1) Die Sprache aller Wörter, in denen die Anzahl der a's und die Anzahl der b's beide ungerade sind;

2) Die Sprache aller Wörter, deren Länge ungerade ist und die die Teilfolge ab enthalten.

Bitte helfen Sie mir auch, wenn möglich, zwei verschiedene Ausdrücke für jede Aufgabe zu finden, damit ich besser verstehe, wie man solche Probleme lösen kann.

Answer 1

Für den ersten Fall gibt es ein einfaches 4-Zustände-DFA, das man konstruieren kann, um die Sprache zu erkennen. Dann kann man den Algorithmus aus dem Satz von Kleene verwenden (der Teil, in dem er sagt, dass alle Sprachen, die von einer FA erkannt werden, von einer RE erzeugt werden), um eine RE zu erhalten, die funktioniert... oder man kann es einfach aus dem Diagramm herausfinden.

Bei der zweiten wissen Sie, dass (ab) Teil der RE ist; jetzt müssen Sie sich alle Möglichkeiten überlegen, wie Sie eine ungerade Anzahl von Zeichen hinzufügen können (vorne oder hinten), und alle diese Möglichkeiten mit + verbinden, um eine einfache, korrekte RE zu erhalten.

Ich glaube nicht, dass irgendjemandem die Idee gefällt, Ihnen einfach eine Antwort zu geben.

EDIT:

Da nun einige Zeit vergangen ist, werde ich die Antwort auf die erste Frage durcharbeiten, um interessierten Lesern zu zeigen, wie es gemacht werden kann.

Unser erstes FA ist dieses:

   Q s f(Q, s)
  -- - -------
  EE a     OE
  EE b     EO
  OE a     EE
  OE b     OO
  EO a     OO
  EO b     EE
  OO a     EO
  OO b     OE

Wir werden Zustände daraus entfernen und s durch einen regulären Ausdruck ersetzen, der diesen Zustand abdeckt. Wir beginnen mit einem einfachen... wir entfernen OE. Hier ist die Tabelle dafür...

   Q                  regex f(Q, s)
  -- ---------------------- -------
  EE                     aa      EE
  EE                     ab      OO
  EE                      b      EO
  EO                      a      OO
  EO                      b      EE
  OO                      a      EO
  OO                     ba      EE
  OO                     bb      OO

Überzeugen Sie sich von der Richtigkeit dieser Angaben, bevor Sie fortfahren. Als nächstes werden wir EO los:

   Q                  regex f(Q, s)
  -- ---------------------- -------
  EE                  aa+bb      EE
  EE                  ab+ba      OO
  OO                  ab+ba      EE
  OO                  aa+bb      OO

Um den nächsten Schritt zu vereinfachen, führen wir eine neue Startmenge X und einen neuen akzeptierenden Zustand Y ein; OO ist nicht mehr akzeptierend. Wir machen OO überflüssig:

   Q                        regex f(Q, s)
  -- ---------------------------- -------
   X                        empty      EE
  EE aa+bb+(ab+ba)(aa+bb)*(ab+ba)      EE
  EE              (ab+ba)(aa+bb)*       Y

Die endgültige Regex lautet also

  (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*(ab+ba)(aa+bb)*

Wir können damit beginnen, die kleinsten Zeichenketten aufzulisten, die dabei entstehen, nur um die Richtigkeit zu überprüfen: {ab, ba, aaab, aaba, bbab, bbba, abaa, abbb, baaa, babb, ...} Sieht für mich gut aus!

Die Regeln für die Reduktion bei jedem Schritt können formalisiert werden, oder Sie können einfach durch sorgfältiges Nachdenken sicherstellen, dass Sie das Richtige bekommen. Eine sorgfältige Analyse finden Sie in einem Beweis des Satzes von Kleene. Auch in Martins Einführung in formale Sprachen oder ähnlichem finden sich gute Beispiele für die Anwendung dieses Algorithmus.