Beschreiben formaler Sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:07 Mo 05.11.2012 | | Autor: | apple314 |
| Aufgabe | Es sei A={a,b}. Beschreiben Sie unter Benutzung nur der Symbole {,},a,b, [mm] \in, \cup, [/mm] * und +, sowie runde Klammer auf, runde Klammer zu und Komma, die folgenden formalen Sprachen.
a) Die Menge aller Wörter über A, bei denen bb direkt vor jedem a steht;
b) Die Menge aller Wörter über A, die ungerade Länge haben;
c) Die Menge aller Wörter über A, die gleich viele Teilwörter ab und ba enthalten. |
Hi zusammen!
Für a) bin ich wie folgt vorgegangen:
A={a,b}
L = {w [mm] \in [/mm] A*| bb steht direkt vor jedem a}
also beliebig c & b, dann bb, dann a usw., dh. vor dem ersten ah steht ein bb.
[mm] \{c,b\}*\{bb\}\{a\}^{+} [/mm] , wenn nur ein a-Block existiert.
[mm] (\{c,b\}*\{bb\}\{a\}^{+})\* [/mm] für bel. viele a-Blöcke
außer, wenn das erste Zeichen ein a ist! Also
[mm] (\{c,b\}*\{bb\}\{a\}^{+})\* \cup \{a\}^{+} (\{c,b\}\*\{bb\}\{a\}^{+})\*
[/mm]
Ausklammern:
[mm] (\{a\}^{+} \cup \{\in\}) (\{c,b\}\*\{bb\}\{a\}^{+})\*
[/mm]
oder
[mm] \{a\}\*(\{c,b\}\*\{bb\}\{a\}^{+})\* [/mm] aber: die angegebene Sprache endet mit a, falls ein a vorkommt, also..
[mm] \{a\}\*(\{c,b\}\*\{bb\}\{a\}^{+})\*\{c,b\}\*
[/mm]
So, soweit komm ich schonmal. Stimmt das so?
Mit b) hab ich nun aber insofern ein Problem, dass es sich hierbei um die Länge der einzelnen Wörter über A handelt und nicht um die Reihenfolge der einzelnen Zeichen in dem Wort... wie schreib ich denn sowas? Jemand 'ne Idee?
Grüße,
apple314
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo apple314,
> Für a) bin ich wie folgt vorgegangen:
...
> [mm]\{a\}\*(\{c,b\}\*\{bb\}\{a\}^{+})\*\{c,b\}\*[/mm]
Wie kommst Du überhaupt auf c? Geht doch nur um a und b (A={a,b}), d.h. es geht um
L = ( w [mm] \in \{a,b\}^{\*} [/mm] | bb steht direkt vor jedem a)
> also beliebig c & b, dann bb, dann a usw., dh. vor dem ersten ah steht ein bb.
daher also auch:
beliebig b, dann bba usw - aber nicht nur vor dem ERSTEN a steht ein bb, sondern vor JEDEM a! (Dementsprechend fängt jedes Wort mit b und nie mit a an!)
Magst Du es nochmal mit diesen Hinweisen probieren?
> Mit b) hab ich nun aber insofern ein Problem, dass es sich
> hierbei um die Länge der einzelnen Wörter über A handelt
> und nicht um die Reihenfolge der einzelnen Zeichen in dem
> Wort... wie schreib ich denn sowas? Jemand 'ne Idee?
Versuche Dir doch dafür mal zu überlegen, was das für Wörter sind, die diese Bedingung erfüllen. Also mal ein paar Beispiele aufschreiben und versuchen so zu der Formalisierung zu kommen.
Viele Grüße
Anna
|
|
|
|
