reguläre Sprache? < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:43 Di 20.11.2007 | | Autor: | GaLiun |
| Aufgabe | | $L = [mm] \{ x \in \{ a,b,c\}^{\*}$ : Die Anzahl der a in x ist gleich der Anzahl b in x $\}$ [/mm] Ist dieser Ausdruck regulär? |
Hallo
Wenn ich mich richtig erinnere, dann ist die Sprache wohl regulär. Aus Endlichkeit folgt reguläre Sprache. Anzahl a = Anzahl b deutet darauf hin, dass es endlich ist, aber das c könnte unendlich mal vorkommen.
Wie kann ich hier nachweisen, ob die Sprache regulär oder nicht regulär ist?
Danke schon mal für eure Hilfe
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo und ![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]") ,
> Wenn ich mich richtig erinnere, dann ist die Sprache wohl regulär. Aus Endlichkeit folgt reguläre Sprache. Anzahl a = Anzahl b deutet darauf hin, dass es endlich ist, aber das c könnte unendlich mal vorkommen.
Nein. Es ist gar nicht klar, um welche Endichkeit es sich handelt.
Ein Wort hat immer eine endliche Länge. Die Länge kann beliebig groß sein, aber endlich. Insofern funktioniert dein Argument hier nicht.
Das Problem hier ist die gleiche Häufigkeit. So etwas deutet auf (mindestens) kontextfreie Sprachen.
> Wie kann ich hier nachweisen, ob die Sprache regulär oder nicht regulär ist?
Wenn du nachweisen willst, dass die Sprache regulär ist, dann präsentiere einfach eine reguläre Grammatik, die diese Sprache erzeugt, oder einen endlichen Automaten, der Wörter dieser Sprache akzeptiert.
Zum Beweis des Gegenteils bedienst du dich am besten des unausweichlichen ![[]](/images/popup.gif) Pumping-Lemmas für reguläre Sprachen.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:34 Mi 21.11.2007 | | Autor: | GaLiun |
| Aufgabe | | $ L = [mm] \{ x \in \{ a,b,c\}^{*} $ : Die Anzahl der a in x ist gleich der Anzahl b in x $ \} [/mm] $ Ist dieser Ausdruck regulär? |
Hallo.Danke für das Willkommensschild und für dien Hinweis aufs Pumpinglemma,was ich vollkommen übersehen hab weil ich da mindestens ein Problem habe.Es kann folgende Fälle auftreten
aabb
abab
baba
bbaa
ab
ba
...
Jetzt ist beim Beispiel bei Wikipedia gegeben L = [mm] \{ a^mb^m | m \ge 1 \} [/mm]
Dann wird gleich aufgeschrieben x = uvw = [mm] a^nb^n.
[/mm]
Diese Formulierung [mm] a^nb^n [/mm] habe ich ja nicht und deswegen kriege ich nichts gebacken
(a*b*)*
muss ich damit arbeiten?Diese Formluierung hätte ich noch in keinem Beispiel gesehen.Deswegen weiß ich auch in diesem Fall nicht weiter.
Hilfst du mir noch mal bitte?
Gruß
> Hallo und ,
>
> > Wenn ich mich richtig erinnere, dann ist die Sprache wohl
> regulär. Aus Endlichkeit folgt reguläre Sprache. Anzahl a =
> Anzahl b deutet darauf hin, dass es endlich ist, aber das c
> könnte unendlich mal vorkommen.
> Nein. Es ist gar nicht klar, um welche Endichkeit es sich
> handelt.
> Ein Wort hat immer eine endliche Länge. Die Länge kann
> beliebig groß sein, aber endlich. Insofern funktioniert
> dein Argument hier nicht.
> Das Problem hier ist die gleiche Häufigkeit. So etwas
> deutet auf (mindestens) kontextfreie Sprachen.
>
> > Wie kann ich hier nachweisen, ob die Sprache regulär oder
> nicht regulär ist?
> Wenn du nachweisen willst, dass die Sprache regulär ist,
> dann präsentiere einfach eine reguläre Grammatik, die diese
> Sprache erzeugt, oder einen endlichen Automaten, der Wörter
> dieser Sprache akzeptiert.
> Zum Beweis des Gegenteils bedienst du dich am besten des
> unausweichlichen
> Pumping-Lemmas für reguläre Sprachen.
>
>
> Gruß
> Martin
|
|
|
| |
|
Hallo,
das ist nur ein bisschen verwirrender mit dem zusätzlichen c, aber nicht weiter tragisch. Man kann es eigentlich genauso machen (wenn die Sprache ohne das c schon nicht regulär ist, dann erst recht mit c).
Betrachten wir also für ein festes $n$ das Wor [mm] $a^ncb^n$.
[/mm]
Wir zerlegen es und stellen fest, dass nach 2. gilt: $uv = [mm] a^{n'}$ [/mm] mit $n' [mm] \le [/mm] n$. Also muss auch $v$ aus mindestens einem $a$ bestehen (nennen wir diese Zahl $n''$).
Nun müssten wir das Wort nach 3. in der Mitte beliebig mit $v$s vollpumpen (Pumping-Lemma!) können. Dann erhalten wir aber für beispielsweise $n$ zusätzliche $v$s:
$x' = [mm] uv^{n}w [/mm] = [mm] a^{n'-n''}a^{n''+n}a^{n-n'}cb^n [/mm] = [mm] a^{2n}cb^n \notin [/mm] L$
Ist klar, oder?
Gruß
Martin
|
|
|
|
