Menge < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:36 Di 16.09.2008 | | Autor: | Boki87 |
| Aufgabe | Folgendes ist gegeben:
[mm] S_{0}\to S_{0}d|S_{1}d
[/mm]
[mm] S_{1}\to bS_{1}dd|S_{2}
[/mm]
[mm] S_{2}\to aS_{2}ddd|S_{3}
[/mm]
[mm] S_{3}\to cS_{3}|ccc
[/mm]
Man soll die Menge angeben! |
Ich habe folgende Lösung, stimmt diese:
[mm] L(A)={b^{m}a^{n}c^{l}d^{p}|b\ge0,n\ge0,l\ge3,p\ge1}
[/mm]
Es gibt ja auf jeden Fall ein d am Ende, es können aber natürlich auch mehrere sein. An vorletzter Stelle sind mindestens 3 c, aber es können natürlich auch mehr sein. An 2 Stelle können beliebig viele a kommen, aber auch keins. Mit den b siehts genauso aus.
Stimmt das so?
Danke schonmal im Voraus
|
|
| |
|
Hallo Boki87!
> Folgendes ist gegeben:
> [mm]S_{0}\to S_{0}d|S_{1}d[/mm]
> [mm]S_{1}\to bS_{1}dd|S_{2}[/mm]
> [mm]S_{2}\to aS_{2}ddd|S_{3}[/mm]
>
> [mm]S_{3}\to cS_{3}|ccc[/mm]
>
> Man soll die Menge angeben!
> Ich habe folgende Lösung, stimmt diese:
>
> [mm]L(A)={b^{m}a^{n}c^{l}d^{p}|b\ge0,n\ge0,l\ge3,p\ge1}[/mm]
>
> Es gibt ja auf jeden Fall ein d am Ende, es können aber
> natürlich auch mehrere sein. An vorletzter Stelle sind
> mindestens 3 c, aber es können natürlich auch mehr sein. An
> 2 Stelle können beliebig viele a kommen, aber auch keins.
> Mit den b siehts genauso aus.
>
> Stimmt das so?
Ich glaube nicht. Denn wie viele von welchen Buchstaben es gibt, hängt doch voneinander ab, nach deiner Beschreibung können es quasi beliebig viele sein, jedenfalls unabhängig voneinander. Also, was ich meine, wenn z. B. [mm] S_1 [/mm] kommt, dann kommt vorne ein b hin, und hinten zwei d's. Wenn aus dem dazwischen stehenden [mm] S_1 [/mm] nochmal dieselbe Regel angewandt wird, dann haben wir insgesamt zwei b's und schon vier d's. Und z. B. zwei b's und nur zwei d's ginge nicht, oder? Das hast du nicht beachtet.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:40 Di 16.09.2008 | | Autor: | Boki87 |
Also quasi so oder
[mm] L(A)=\{b^{m}a^{n}c^{l}d^{p+2m+3n}|m\ge 0, n\ge 0, l\ge 3, p\ge1\}
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:35 Di 16.09.2008 | | Autor: | bazzzty |
Sorry, diese Frage war noch nicht da, als ich die andere Frage aufgemacht habe und dann wurde ich unterbrochen. Diese Lösung stimmt. Und meine andere Antwort hilft Dir vielleicht noch bei der Begründung, falls sie Dir nicht schon ganz klar ist.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:20 Di 16.09.2008 | | Autor: | bazzzty |
> Folgendes ist gegeben:
> [mm]S_{0}\to S_{0}d|S_{1}d[/mm]
> [mm]S_{1}\to bS_{1}dd|S_{2}[/mm]
> [mm]S_{2}\to aS_{2}ddd|S_{3}[/mm]
>
> [mm]S_{3}\to cS_{3}|ccc[/mm]
>
> Man soll die Menge angeben!
> Ich habe folgende Lösung, stimmt diese:
>
> [mm]L(A)={b^{m}a^{n}c^{l}d^{p}|b\ge0,n\ge0,l\ge3,p\ge1}[/mm]
Nein, die Lösung stimmt nicht, Bastiane hat ja schon einen Hinweis gegeben.
Mein Tipp: Guck Dir mal an, wie die einzelnen Regeln aussehen, und wie zwischen den Regeln gewechselt werden kann. Wie oft kann jede Regel angewendet werden? Was weiß ich über das Wort, wenn ich weiß, wie oft jede Regel angewendet wurde?
NUR WEITERLESEN, WENN DAS NICHT REICHT!
Jede Regel kann beliebig oft mit der linken Alternative angewendet werden und dann einmal mit der rechten Möglichkeit. Die Anzahlen bestimmen das Wort eindeutig. Seien also [mm]k_i[/mm] die Anwendungen einer Ableitung von [mm]S_i[/mm]. Das entstehende Wort ist...
|
|
|
|
