Sprache einer Grammatik < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:44 Fr 23.09.2011 | | Autor: | Harris |
| Aufgabe | Die Grammatik $G$ sei definiert durch [mm] $G=(\{S,T\},\{a,b\},\Phi,S) [/mm] mit
[mm] $\Phi$ [/mm] als Menge der Regeln
[mm] $S\rightarrow [/mm] aT$
[mm] $S\rightarrow [/mm] aTbT$
[mm] $T\rightarrow [/mm] aT$
[mm] $T\rightarrow [/mm] aTbT$
[mm] $T\rightarrow \varepsilon$
[/mm]
Welche Sprache wird durch $G$ erzeugt? |
Hi!
Ich würde gerne wissen, was hier rauskommt.
Meiner Meinung nach werden alle Worte akzeptiert, welche ein führendes $a$ haben und die Anzahl der $b$ kleiner gleich der Anzahl der $a$ ist.
Stimmt das?
Gruß, Harris
|
|
| |
|
moin,
Ich bin der Meinung du kriegt abba nicht gebastelt.
Dieses Wort würde ja deinen Bedingungen entsprechen, aber man kann es nicht bauen:
Fall 1:
S -> aT
nun hast du entweder das Wort a (indem du $T [mm] \rightarrow \epsilon$ [/mm] machst) oder aber du kriegst zwei führende a; beides bringt uns nicht zu abba.
Fall 2:
S -> aTbT
Hier muss, damit an zweite Stelle ein b kommt, das erste T auf [mm] $\epsilon$ [/mm] gehen (denn sonst hätte man wieder zwei führende a).
Also ergibt sich:
S -> aTbT -> abT
Hier gleiches Problem wie in Fall 1, wir erhalten entweder das Wort "ab" oder ein Wort, das mit "aba" beginnt.
Somit lässt sich "abba" nicht darstellen und deine Bedingungen passen noch nicht ganz.
Wie genau die Bedingungen aussehen müssen weiß ich grad nicht so genau, aber du musst eine Aussage über die Reihenfolge treffen, irgendwas in der Form "vor n bs müssen unbedingt m as stehen" oder so. ;)
MfG
Schadowmaster
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:08 Fr 23.09.2011 | | Autor: | Harris |
Ich hab mir inzwischen ein kleines Javaproggy gebastelt.
Ich kann ja mal die Wörter bis zur Länge 6 posten:
a
Wörter der Länge 1 = 1 Stück; 1 haben mehr a's; 0 haben gleich viele a's
aa
ab
Wörter der Länge 2 = 2 Stück; 1 haben mehr a's; 1 haben gleich viele a's
aaa
aab
aba
Wörter der Länge 3 = 3 Stück; 3 haben mehr a's; 0 haben gleich viele a's
aaaa
aaab
aaba
aabb
abaa
abab
Wörter der Länge 4 = 6 Stück; 4 haben mehr a's; 2 haben gleich viele a's
aaaaa
aaaab
aaaba
aaabb
aabaa
aabab
aabba
abaaa
abaab
ababa
Wörter der Länge 5 = 10 Stück; 10 haben mehr a's; 0 haben gleich viele a's
aaaaaa
aaaaab
aaaaba
aaaabb
aaabaa
aaabab
aaabba
aaabbb
aabaaa
aabaab
aababa
aababb
aabbaa
aabbab
abaaaa
abaaab
abaaba
abaabb
ababaa
ababab
Wörter der Länge 6 = 20 Stück; 15 haben mehr a's; 5 haben gleich viele a's
Sieht irgendwer eine Beschreibungssystematik?
|
|
|
| |
|
Du kannst mittels $T [mm] \to [/mm] aT$ beliebig viele as erzeugen.
Deshalb muss nicht nur gelten, dass Anzahl as [mm] $\geq$ [/mm] Anzahl bs, sondern sogar:
Anzahl as [mm] $\geq$ [/mm] Anzahl bs, wenn man das Wort hinter dem letzten b abschneidet (also die "End-as" weglässt).
Also deine Wörter müssen mit a anfangen, können mit beliebig vielen a enden und wenn man das Wort hinter dem letzten b abschneidet so muss das verbleibende Wort mindestens so viele as wie bs enthalten.
Ob damit nun wirklich alle und genau alle Wörter charakterisiert werden kannst du ja nochmal ein wenig ausprobieren; ich glaube aber das passt so.
MfG
Schadowmaster
|
|
|
|
