Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Kontextfreie Grammatik angeben
Autor
Universität/Hochschule J Kontextfreie Grammatik angeben
PMueller123
Neu Letzter Besuch: im letzten Quartal
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 Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 1166
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 Letzter Besuch: im letzten Quartal
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 Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 1166
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 Letzter Besuch: im letzten Quartal
Dabei seit: 27.05.2022
Mitteilungen: 4
  Beitrag No.4, vom Themenstarter, eingetragen 2022-06-20

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.

Wechsel in ein anderes Forum:
 Suchen    
 
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]