Kontextsensitive Grammatik < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:04 Di 21.05.2013 | | Autor: | bandchef |
| Aufgabe | | Konstruieren Sie für die folgende Sprache eine kontextsensitive Grammatik [mm] $G=\{V, \Sigma, P, S\}$ [/mm] mit $|V|=3$: [mm] $L_1 =\{a^n b^n c^n | n \in \mathbb N\}$ [/mm] |
Hi Leute!
Ich hab große Probleme diese, meiner Ansicht nach wirklich schwierige, Aufgabe zu lösen.
Ich hab bisher diese Produktionen erstellt, die zwar solche geforderten Wörter erstellen kann, aber leider auch andere Wörter erstellt:
$P = [mm] \{S \to \epsilon, S \to ABC, AB \to AAB, BC \to BBC, C \to CC, A \to a, B \to b, C \to c\}$
[/mm]
Bsp.: S -> ABC -> AABC -> AABBC -> AABBCC -> aabbcc :)
Aber: S -> ABC -> AABC -> AAABC -> aaabc :(
Wie muss ich nun meine Grammatik noch weiter einschränken, dass ich nur Wörter der Form [mm] $a^n b^n c^n$ [/mm] bekomme? Kann mir da jemand helfen?
|
|
| |
|
Hallo bandchef,
>
> [mm]P = \{S \to \epsilon, S \to ABC, AB \to AAB, BC \to BBC, C \to CC, A \to a, B \to b, C \to c\}[/mm]
Also auf den ersten Blick fällt mir keine weitere Einschränkung ein, um Deinen Ansatz korrekt werden zu lassen. Ich würde es anders probieren. Tipp:
Es muss ja jedes a - b - c immer gleich oft vorkommen, d.h. Dein S [mm] \to [/mm] ABC ist ja schon mal nicht so verkehrt. Nun überlege mal, ob es nicht möglich wäre, diese Regel so zu ändern, dass man durch Einfügen eines S in ABC nicht zu einer Lösung kommt. Weiterer Tipp: Danach muss u.a. noch eine Regel folgen, bei denen Du Nichtterminale vertauscht. Hilft Dir das als Ansatz zum nachgrübeln? 
Viele Grüße
Anna
|
|
|
|
