Die Mathe-Redaktion - 23.11.2017 23:11 - Registrieren/Login
Auswahl
Schwarzes Brett
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 539 Gäste und 14 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Informatik » Theoretische Informatik » Algorithmus zum Entscheiden des Wortproblems
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Algorithmus zum Entscheiden des Wortproblems
FragenKostaNix
Neu Letzter Besuch: im letzten Monat
Dabei seit: 17.06.2016
Mitteilungen: 2
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2017-11-09 02:05


Hallo liebe Matroid'ler,
ich habe im Bereich der Formale Sprachen und Automatentheorie Schwierigkeiten beim Ansatz der Aufgabe und bei der formalen Darstellung einer Lösung.

Folgendes ist die Aufgabenstellung:

Folgender Algorithmus wird zum Entscheiden des Wortproblems für kontextsensitive Grammatiken genutzt. Geben Sie eine obere Schranke an die Anzahl der Elemente in den Mengen fed-Code einblenden an.
Die Schranke soll in geschlossener Form und in Bezug auf fed-Code einblenden fed-Code einblenden
und Eingabelänge n sein. Zeigen Sie, dass dieser Algorithmus Mengen fed-Code einblenden ,
mit fed-Code einblenden auf Eingaben der Länge n erzeugt.
Angenommen eine Rechenmaschine mit fed-Code einblenden Takten pro Sekunde benötigt für die Anweisung fed-Code einblenden fed-Code einblenden
nur fed-Code einblenden Takte. Welche Zeit benötigt dieser Algorithmus mindestens auf so einer Eingabe mit 100 Zeichen?



Hier muss ich noch sagen, dass man vorher die Definition der Grammatik in der Formalen Sprache kennen muss, wobei folgendes gilt:
Formal ist eine Grammatik ein Quadrupel:
G = (V, fed-Code einblenden , P, S)
fed-Code einblenden steht hier für das (Terminal-)Alphabet z.B. fed-Code einblenden und der Betrag bedeutet Anzahl der Mengenelemente in fed-Code einblenden , in diesem Beispiel = 2 in der Aufgabe jedoch keine Angabe.
fed-Code einblenden
(endlich), die Regelmenge (der Punkt soll ein * sein). Elemente von P heißen auch Produktionen.
V steht für eine eine endliche, nichtleere Variablenmenge z.B. fed-Code einblenden
fed-Code einblenden

D.h. die vorliegende Grammatik sei G = (V, fed-Code einblenden , P, S) und es gelte für alle fed-Code einblenden

Der Algorithmus:

INPUT sei x mit |x| = n
T := {S};
REPEAT T1 := T; T := fed-Code einblenden
UNTIL (x fed-Code einblenden T) OR (T = T1);
IF x fed-Code einblenden T THEN OUTPUT(1) ELSE OUTPUT(0);

fed-Code einblenden
(der Punkt soll ein * sein)



Nun ist mein Ansatz folgender:
Ich habe ein Beispiel genommen und n beliebig gewählt.
fed-Code einblenden

Was mich aber jetzt zum Denken bringt wie ich beweisen soll, dass der Algorithmus fed-Code einblenden

Was habe ich übersehen oder woran habe ich nicht gedacht?
Eventuell habe ich irgendetwas in Bezug zur Vereinigung übersehen bei der Definition von fed-Code einblenden


Ich würde mich über jede Hilfe freuen.

Mit freundlichen Grüßen



  Profil  Quote  Link auf diesen Beitrag Link
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-2017 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]