| |
| Autor |
  Kontextfreie Grammatik angeben |
|
PMueller123
Neu 
Dabei seit: 27.05.2022
Mitteilungen: 4
 |  Themenstart: 2022-05-27
|
Hallo zusammen,
ich verzweifle an dieser Aufgabe, in der aus der Sprache S eine kontextfreie Grammatik angegeben werden soll. Vielleicht ist jemand so freundlich und kann mir Lösungsansätze mitteilen. Vielen Dank im Voraus!
https://matheplanet.com/matheplanet/nuke/html/uploads/b/55618_Bildschirmfoto_2022-05-27_um_15.44.00.png
|
 Profil
|
thureduehrsen
Senior 
Dabei seit: 13.11.2007
Mitteilungen: 1154
Wohnort: Kiel, Deutschland
 |  Beitrag No.1, eingetragen 2022-05-27
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
Hallo Pmueller123,
die Sprache \(S\) besteht aus allen Wörtern über \(\{a,\,b,\,c\}\), die mit einem beliebigen Wort \(v\in\{a,\,b\}^{+}\) beginnen und danach genau ein Vorkommen weniger von \(c\) enthalten als die Länge des Wortes \(v\) beträgt.
Ein Ansatz (mit dem Startsymbol \(\mathrm{S'}\)) kann also darin bestehen, ein Nichtterminal \(\mathrm{T}\) für das Wort \(v\) und ein Nichtterminal \(\mathrm{U}\) für den nur aus \(c\) bestehenden hinteren Teil von \(w\) vorzusehen:
\[\begin{align}
\mathrm{S'} &\to \mathrm{T\,U}\\[1mm]
\mathrm{T} &\to\ ???\\[1mm]
\mathrm{U} &\to\ ???
\end{align}
\]
Ich gebe jetzt einmal eine beispielhafte Ableitung für das Wort \(\mathrm{a\,b\,a\,c\,c}\) an, aus der du die noch fehlenden Regeln leicht ergänzen können solltest:
\[
\mathrm{S' \to T\,U \to a\,T\,c\,U \to a\,b\,T\,c\,c\,U \to a\,b\,a\,c\,c\,U \to a\,b\,a\,c\,c}
\]
mfg
thureduehrsen\(\endgroup\)
|
Profil
|
PMueller123
Neu
Dabei seit: 27.05.2022
Mitteilungen: 4
| Beitrag No.2, vom Themenstarter, eingetragen 2022-05-28
|
Hallo thureduehrsen,
vielen, lieben Dank! Sehr gut erklärt.
Was ich noch nicht verstanden habe:
Das Nichtterminal T ist unter anderem T -> aTc|bTc etc., also für den ersten Teil (v) des Wortes zuständig. v ist aber ∈ {a,b}+.
Warum darf ich auf der rechten Seite das c benutzen?
(aTc darf man, aber cTa anscheinend nicht?)
Und U kann nur folgendes sein U -> c|e ?
Vielen Dank für die (weitere) Aufklärung.
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1154
Wohnort: Kiel, Deutschland
| Beitrag No.3, eingetragen 2022-05-28
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
\quoteon(2022-05-28 14:04 - PMueller123 in Beitrag No. 2)
Was ich noch nicht verstanden habe:
Das Nichtterminal T ist unter anderem T -> aTc|bTc etc., also für den ersten Teil (v) des Wortes zuständig. v ist aber ∈ {a,b}+.
Warum darf ich auf der rechten Seite das c benutzen?
(aTc darf man, aber cTa anscheinend nicht?)
\quoteoff
In dem Satz
\quoteon Warum darf ich auf der rechten Seite das c benutzen?
\quoteoff
willst du offenbar ausdrücken, dass in der Satzform \(\mathrm{a\,T\,c}\) das Terminalsymbol \(\mathrm{c}\) rechts vom Nichtterminalsymbol \(\mathrm{T}\) steht.
Das ist ohne Weiteres zulässig, genauso wie die Regel
\[
\mathrm{T} \to \mathrm{c\,T\,a}
\]
zulässig ist.
In einer kontextfreien Grammatik, und eine solche basteln wir ja gerade, steht auf der rechten Seite jeder Regel eine beliebig lange Folge von Nichtterminal- und Terminalsymbolen. Dass im Wort \(v\) nur die Terminalsymbole \(\mathrm{a}\) und \(\mathrm{b}\) vorkommen, ist hier unerheblich; die Terminalsymbole auf der rechten Seite einer Regel dürfen aus der gesamten Menge der Terminalsymbole der Grammatik stammen.
Siehe auch hier, Karte 59.
\quoteon(2022-05-28 14:04 - PMueller123 in Beitrag No. 2)
Und U kann nur folgendes sein U -> c|e ?
\quoteoff
Sieht ganz so aus.
Mein Vorschlag gestern war zugegebenermaßen mit heißer Nadel gestrickt, und die Beschreibung, dass das Nichtterminalsymbol \(\mathrm{U}\) für den gesamten aus \(\mathrm{c}\) bestehenden Teil des erzeugten Wortes zuständig ist, ist falsch.
Vielleicht kann man auf \(\mathrm{U}\) auch ganz verzichten? Probiere einfach mal ein bisschen herum, wie weit du mit dem Regelsatz
\[\begin{align}
\mathrm{S'} &\to \mathrm{T\,U}\\[1mm]
\mathrm{T} &\to\ \mathrm{a\,T\,c}\\[1mm]
\mathrm{T} &\to\ \mathrm{b\,T\,c}\\[1mm]
\mathrm{U} &\to\ \mathrm{c}\\[1mm]
\mathrm{U} &\to\ \mathrm{\varepsilon}\\[1mm]
\end{align}
\]
kommst, und füge sonst noch nötige Regeln hinzu.
mfg
thureduehrsen\(\endgroup\)
|
Profil
|
PMueller123
Neu
Dabei seit: 27.05.2022
Mitteilungen: 4
| Beitrag No.4, vom Themenstarter, eingetragen 2022-06-20 18:26
|
Danke nochmal thureduehrsen.
Man kann U weglassen.
Die korrekte Lösung ist:
S'-> aS'c
S'-> bS'c
S'-> a
S'-> b
|
Profil
|
PMueller123 hat die Antworten auf ihre/seine Frage gesehen.
PMueller123 hat selbst das Ok-Häkchen gesetzt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
