Die Mathe-Redaktion - 22.02.2018 11:32 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 664 Gäste und 25 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Beweis von Grammatiken durch Induktion
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Beweis von Grammatiken durch Induktion
jonjones
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 17.11.2017
Mitteilungen: 4
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-01-17


Guten Abend liebes Forum,

ich wusste jetzt nicht in welches Unterforum meine Frage passt, da es sich sowohl um die Beweistechnik Induktion als auch um Grammatiken und Sprachen handelt.

Ich beherrsche den Beweis per Induktion durchschnittlich würde ich sagen und Sprachen/Grammatiken ebenso - leider nicht genug um eine Aufgabe zu lösen, die mir Kopfschmerzen bereitet.

Es ist folgende Grammatik gegeben:

T = {a,b}
N = {S}
P = {  
          p1 = S::= aS
          p2 = S::= Sb
          p3 = S::= a
          p4 = S::= b
       }

Nun sollen wir beweisen, dass die Teilfolge "ba" niemals auftreten kann - mithilfe von Induktion.

Ich habe überhaupt keine Ahnung wie ich an die Sache rangehen soll. Induktionsanfang ist klar, kriege ich hin. Dann habe ich überlegt, dass ich über die Ableitungen gehe - sprich wenn man eine Produktionsregel anwendet (n) und dann halt die nächste (n+1), das so irgendwie zu beweisen. Aber ich habe nichts aufschreiben können, ich bin letztendlich total planlos.
Ein Beispiel dazu habe ich im Internet auch nicht finden können.

Ich wäre über jede Anregung und jeden Gedankengang SEHR dankbar.

Ich bedanke mich im Voraus für Zeit und Mühe jedes Users und verbleibe mit

freundlichsten Grüßen

jonjones



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 3858
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-01-18


Hallo jonjones,

2018-01-17 20:24 - jonjones im Themenstart schreibt:
ich lasse erstmal ab sie hier zu posten, da es mir um den allg. Weg geht, außer es geht nicht anders, dann füge ich sie natürlich gerne hinzu

Ich denke, es würde hier erst einmal helfen, wenn du das konkrete Beispiel postest. Ob es einen allgemeinen Lösungsweg gibt, kann man sich dann immer noch überlegen.

Gruß
StrgAltEntf



  Profil  Quote  Link auf diesen Beitrag Link
darkhelmet
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 05.03.2007
Mitteilungen: 2181
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2018-01-18


Hi,

wahrscheinlich wäre es doch besser, du postest ein konkretes Beispiel. Dann steigt die Bereitschaft zu antworten, weil man etwas hat, auf das man sich beziehen kann, und deshalb nicht so weit ausholen muss. Außerdem gibt es sicher Leute, die sich unter "kontextfreie Grammatik" nichts vorstellen können, aber viel Erfahrung mit Induktion haben und die Frage beantworten könnten, wenn du sie (für allgemeine Mathematiker) zugänglicher machen würdest.

[Die Antwort wurde vor Beitrag No.1 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
jonjones
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 17.11.2017
Mitteilungen: 4
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2018-01-19


Liebe/r StrgAltEntf, liebe/r darkhelmet,

zunächst einmal vielen Dank für Euren Hinweis. Jetzt wo ihr mich darauf aufmerksam gemacht habt, war es tatsächlich dämlich das konkrete Beispiel wegzulassen - ehrlichgesagt wollte ich damit nur vermeiden, dass es rüberkommt, als hätte ich mir keine Gedanken gemacht und es würde mich nur die Lösung zur Aufgabe interessieren. Es geht mir aber wirklich um den Weg und/oder die Idee dahinter, wie man die Aufgabe angehen könnte, weil ich total planlos bin :/...

also Danke nochmal für Eure Beiträge!



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 1865
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2018-01-19


Idee ungefähr, man macht Induktion über die Tiefe von Ableitungsbäumen (die hier unverzweigt sind.) In einem Schritt können aus S die Wörter a und b abgeleitet werden, sie enthalten nicht die Teilfolge ba. Sei w ein Wort, das in n+1 Schritten abgeleitet wurde, n >= 1. Falls die erste angewendete Produktion p1 = S -> aS war, so ist also w = av, wobei v ein Wort ist, dass aus S in n Schritten abgeleitet wurde. Es enthält daher nach Induktionsvoraussetzung nicht die Teilfolge ba, also enthält av auch nicht die Teilfolge ba. Die anderen Produktionen prüft man analog, wobei ja nur noch p2 in Frage kommt, da p3 und p4 rechts nur aus Terminalen bestehen.

Ich hab nicht darüber nachgedacht, ob das auch bei komplizierteren Grammatiken funktioniert.


-----------------
⊗ ⊗ ⊗



  Profil  Quote  Link auf diesen Beitrag Link
jonjones
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 17.11.2017
Mitteilungen: 4
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2018-01-19


2018-01-19 01:55 - ligning in Beitrag No. 4 schreibt:
Idee ungefähr, man macht Induktion über die Tiefe von Ableitungsbäumen (die hier unverzweigt sind.) In einem Schritt können aus S die Wörter a und b abgeleitet werden, sie enthalten nicht die Teilfolge ba. Sei w ein Wort, das in n+1 Schritten abgeleitet wurde, n >= 1. Falls die erste angewendete Produktion p1 = S -> aS war, so ist also w = av, wobei v ein Wort ist, dass aus S in n Schritten abgeleitet wurde. Es enthält daher nach Induktionsvoraussetzung nicht die Teilfolge ba, also enthält av auch nicht die Teilfolge ba. Die anderen Produktionen prüft man analog, wobei ja nur noch p2 in Frage kommt, da p3 und p4 rechts nur aus Terminalen bestehen.


wirklich vielen Dank für Deine Mühe und Antwort. Es ist mir um einiges klarer geworden, und wie sooft, wenn man die Lösung liest, denkt man sich "Ach na klar, das ist doch logisch"...Ich stand jedenfalls eine geschlagene Woche auf dem Schlauch, ich frage mich ob da jemals wieder Wasser durchfließt haha.

Für mich ist jetzt nur noch unklar: Was benutzt Du als Induktionsvorraussetzung - oder ist diese nicht immer zwingend erforderlich?
Ich dachte als IV müsste man sowas verwenden wie: Für alle w ist wba nicht Element ....oder sowas in der Art?!

Herzlichen Dank nochmal und weiterhin beste Grüße!



  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 982
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2018-01-19

\(\begingroup\) \(\newcommand{\sem}[1]{[\![#1]\!]}\)
Eine kontextfreie Grammatik über dem Terminalalphabet $\Sigma$ kann man selbst als induktive Definition einer Familie von Sprachen (also Teilmengen von $\Sigma^*$) auffassen. Für jedes Nichtterminalsymbol $M$ gibt es dann eine Sprache $L(M)$. Die Produktionen geben an, was jeweils mindestens an Worten enthalten ist, und die Tatsache, dass es sich um eine induktive Definition handeln soll, sagt, dass es sich um die kleinstmögliche Lösung handelt. Die Ausnutzung letzterer Eigenschaft ist auch eine Art Induktionsprinzip.

Beispiel: $\Sigma$ sei irgendein Alphabet, und $a\in\Sigma$. Mit den (suggestiv geschriebenen) Nichtterminalsymbolen $a^*$ und $a^+$ definiert die Grammatik
$$\begin{array}{rcl}
a^* &::=& \varepsilon \mid a^+\\
a^+ &::=& aa^*\\
\end{array}$$
zwei Sprachen, $L(a^*)$ und $L(a^+)$. Für die gilt:
  $\{\varepsilon\} \cup L(a^+) \subseteq L(a^*)$,
  $\{a\} \bullet L(a^*) \subseteq L(a^+)$,
und für alle Sprachen $X,Y$ über $\Sigma$ mit
  $\{\varepsilon\} \cup Y \subseteq X$,
  $\{a\} \bullet X \subseteq Y$
gilt außerdem
  $L(a^*) \subseteq X$,
  $L(a^+) \subseteq Y$.

Jedenfalls, wenn man das zugrundelegt, gilt für die durch die Grammatik aus dem Themenstart festgelegte Sprache:
$$\{a\}\bullet L(S) \cup L(S)\bullet\{b\} \cup \{a\} \cup \{b\} \subseteq L(S),$$
und für alle $X\subseteq \{a,b\}^*$ mit
$$\{a\}\bullet X \cup X\bullet\{b\} \cup \{a\} \cup \{b\} \subseteq X$$
ist $L(S)\subseteq X$.

Sei nun $G$ die Menge der "guten" Worte über $\{a,b\}$, also von jenen, die $ba$ nicht enthalten. Um zu zeigen, dass die Grammatik nur Worte aus $G$ erzeugt (also $L(S)\subseteq G$), reicht es dann aus,
$$\{a\}\bullet G \cup G\bullet\{b\} \cup \{a\} \cup \{b\} \subseteq G$$
zu zeigen. Das ist recht leicht -- dazu wird man aber vermutlich auch nicht umhin kommen, Induktion über Worte zu führen.

[Die Antwort wurde nach Beitrag No.4 begonnen.]
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
jonjones hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


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-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]