Aufgabe 15
(Abgabe bis 9.1.2007, 12:00)
Aufgabenstellung
Welche der folgenden Sprachen über dem Alphabet A = {a, b} sind einseitig-linear, also vom
Chomsky-Typ 3?
1. L1 = A*
2. L2 = {ab, ba}
3. L3 = {bbam ∈ A* | n,m ∈ N0}
4. L4 = {(aba)n ∈ A* | n ∈ N}
5. L5 = {bnan+1 ∈ A* | n ∈ N0}
6. L6 = ∅
Gib jeweils eine rechtslineare Grammatik und den zugehörigen endlichen Automaten an
bzw. begründe, dass es eine solche Grammatik (und damit auch einen entsprechenden Automaten)
nicht geben kann.
Hinweis:
â?¢ N= {1, 2, 3, â?¦} bezeichnet in den oben angegebenen Ausdrücken die Menge der
natürlichen Zahlen ohne(!) die Null.
â?¢ N0 bezeichnet die Menge Ν ∪ {0} = {0, 1, 2, â?¦}.
gruß
der friese
öhem....
gruß
der friese
Neulich, im Wetterbericht:
"...gegen Abend wird es zunehmend dunkler...."
Dieser Beitrag wurde verfasst vom Benutzer: DerFriese
also theoretisch könnt ich mich mal dran versuchen mit wikipedia und etwas halbwissen aus der vergangenheit. compilerbau bzw formale sprachen hab ich vor ca. 10 jahren mal gehört (und es war most hated, weil so fürchterlich trocken und theoretisch - wieviel prozent der studenten werden heute noch zum compilerbau eingesetzt? erst recht nebenfachstudenten, was soll das denn????).
Was ich Dir dann als Lösung anbieten kann, ist wohl zu 90% falsch.
wo ist meister petz?
Was sind eigentlich die Kriterien, daß Du Deinen Schein kriegst??
Freddy Duckstein, GnomProfessor
Dieser Beitrag wurde verfasst vom Benutzer: FreddyDuckstein
ja, lustige geschichte das.....
mit hilfe eines informatiker im msn ist es gerade noch just in time fertig geworden.....
und die scheinkriterien sind, neben regelmäßiger teilnahme an der übung, die anfertigung der hausaufgaben und zwar so, dass der dozent zufrieden ist.....
was auch immer das heissen mag und bis jetzt hats immer hingehauen, was meister petz mir da präsentierte....
gruß
der friese
Neulich, im Wetterbericht:
"...gegen Abend wird es zunehmend dunkler...."
Dieser Beitrag wurde verfasst vom Benutzer: DerFriese
jupp....semester ist bald vorbei...irgendwann mitte februar....
dann ist´s aus mit diesem quark, suche dann ein seminar in informatik, welches absolut easy ist und nicht allzuviel wissen verlangt....quasi den letzten schein en passant machen....
gruß
der friese
Neulich, im Wetterbericht:
"...gegen Abend wird es zunehmend dunkler...."
Dieser Beitrag wurde verfasst vom Benutzer: DerFriese
Aufgabe 16
(Abgabe bis 16.01.2007, 12:00)
New Economy in Palermo Palermo (dpa): Eine kürzlich von dem bekannten Wirtschaftswissenschaftler
Dr. Alfredo erstellte Marktanalyse des in Palermo ansässigen Instituts
für Weltwirtschaft sagt für die kommenden Jahre drastische Umsatzeinbrüche
in den Marktsegmenten Drogenund
Menschenhandel sowie
Waffenschmuggel und Schutzgelderpressung voraus. Ausgehend von
Empfehlungen von Dr. Alfredo hat der Capo der sizilianischen Mafia, Don
Giovanni, daraufhin entschieden, sich künftig verstärkt im Bereich der
Pizzadienste zu engagieren. Erklärtes Ziel der Marketingstrategie ist, dass
jeder Kunde unabhängig vom Wohnort die bestellten Pizzen nach spätestens
30 Minuten geliefert bekommt. Wie der Pressereferent Don Giovannis
verlauten ließ, würde dieser sich persönlich bei jedem Kunden entschuldigen,
bei dem das Versprechen nicht eingehalten werden kann. Über
eventuelle drastische Konsequenzen einer verspäteten Lieferung für die
Auslieferfahrer wollte sich der Sprecher nicht äußern.
Aufgabenstellung
Dieses ehrgeizige Projekt lässt sich nur mit Unterstützung durch ein komplexes Datenbanksystem
realisieren, und eure Firma möchte sich um diesen äußerst lukrativen
Auftrag bewerben. Sie sieht sich in einer guten Position, weil sie schon seit langer
Zeit Erfahrungen mit dem Anwendungsgebiet Pizza sammeln konnte.
Ihr seid als Projektteam mit einer ersten Analyse des Anwendungsgebietes beauftragt
worden, damit ein fundiertes Angebot eingereicht werden kann. Es ist eure Aufgabe,
zu analysieren, welche Daten bei der Herstellung und Lieferung von Pizzen
anfallen. Das Ergebnis der Analyse soll in einer kleinen Studie zusammengefasst
werden. Diese Studie sollte vor allem enthalten:
1. Eine Zusammenstellung der wichtigsten Daten und Datensätze in Tabellenform
(mit Beispieldaten gefüllt).
Tabelle Kunde
In dieser Tabelle werden die Kunden des Pizzaservices verwaltet. ......
(Hier steht somit der Zweck der Tabelle)
Name Vorname Telefon
Braun Bastian 1234
Knaak Nicolas 5678
... ... ...
Das Feld Telefon wird in anderen Tabellen verwendet (anzuzeigen durch Unterstreichen
im Tabellenkopf). In der Tabelle, in der das Feld Telefon benutzt
wird, soll dies durch eine punktierte Unterstreichung passieren. (Hier steht somit
die Beschreibung der Abhängigkeiten zwischen den Tabellen).
Beispiel: Eine Tabelle Kunde mit Telefonnummer, Name, Lieferanschrift usw.
2. Verbale Beschreibung des Zwecks der Tabelle.
3. Verbale Beschreibung von Abhängigkeiten zwischen den Tabellen. Beispiel:
Jeder Bestellung ist ein Kunde zugeordnet.
Dabei müsst ihr die gesamte Produktionskette von der Lieferung der Zutaten über
den Bestellvorgang bis hin zur Lieferung und Bezahlung der fertigen Pizzen berücksichtigen.
Bei der Erstellung der Studie ist zu beachten, dass einerseits die Programmierer
eurer Firma darauf aufbauen können, andererseits aber auch der Einsatzkontext
mit den Anforderungen nicht aus dem Blick gerät. Eure Firma will doch
vermeiden, dass sich Don Giovanni bei seinen Kunden entschuldigen muss (mit den
möglichen Konsequenzen für das Projektteamâ?¦).
Neulich, im Wetterbericht:
"...gegen Abend wird es zunehmend dunkler...."
Dieser Beitrag wurde verfasst vom Benutzer: DerFriese
Bei der Erstellung der Studie ist zu beachten, dass einerseits die Programmierer
eurer Firma ...
Ist ja interessant, da es sich hierbei ja immerhin um Info für Geographiestudenten handelt (ist doch so oder;))? Bin ja mal gespannt, wieviele Diplomgeographen ich später mal als Chef einer IT-Firma (im weitesten Sinne) antreffen werde !
Für die letzte Aufgabe hatte ich leider keine Zeit mehr, aber wie ich sehe hats ja hingehauen. Nun ists zeittechnisch wieder etwas besser.
Dabei ist die Aufgabe ja fast schon BWL-Lastig ... was für Informationen brauche ich wenn ich nen Pizzadienst habe... super Aufgabe
Dieser Beitrag wurde verfasst vom Benutzer: Meister-Petz
Hier mal ein erster Versuch (Verbessungsvorschläge, Ergänzungen, usw. willkommen ) :
Kunde
(Die Tabelle speichert die Basisdaten der Kunden, ausreichend um die Auslieferung
durchzuführen. Durch die Telefonnummer werden sie mit anderen Tabellen verknüpft)
Name Vorname Strasse+Hausnummer Postleitzahl Stadt Telefon
Braun Bastian sonstwostr 33 12345 Sonstwo 1234
Knaak Nicolas anderswostr 12 98765 hier 5678
...
Auslieferer
(Die Tabelle enthält die Basisdaten der angestellten Pizzaauslieferer. Durch die ID werden
sie mit anderen Tabellen verknüpft)
ID Vorname Name Strasse+Hausnummer Postleitzahl Stadt
2 Hans Wurst blub 23 12345 sonstwo
3 Kai Tsung krass 12 28372 sonstwo
.......
Bestellungen
(Diese Tabelle enthält alle vergangenen, sowie noch aktuellen Bestellungen.
Dabei wird die Uhrzeit und das Datum der Bestellung eingetragen, sowie der zuständige
Auslieferer. Ein Extrawunsch kann pro Pizza
ebenfalls angegeben werden. Jede Bestellung ist durch die Telefonnummer einem Kunden zugeordnet)
Telefon ID Pizza Extrawunsch Bestelldatum Bestellzeit
1234 1232 3 7 12.01.07 19:00
1726 1233 2 10.01.07 12:15
.......
(Jeder Bestellung ist ein Kunde zugeordnet.
Jeder Bestellung ist eine Pizza zugeordnet.
Gehören zu einer Bestellung mehrere Pizzen, gibt es für die Bestellid mehrere Einträge)
Bestellabschluss
(Diese Tabelle enthält Informationen über die Auslieferung. Wann wurde ausgeliefert, wie lange hat es gedauert, wer hat ausgeliefert um ggf. den schuldigen zu finden, sowie die Zahlart.
ID Auslieferungszeit benötigte Zeit(min) Auslieferer Rechnungssumme Zahlungsart Telefon
1231 19:20 20 3 4,50 Bar 1234
.......
(Zu jedem Bestellabschluss gehört eine Bestellung.
Zu jedem Bestellabschluss gehört ein Kunde)
Pizzen
(Die Tabelle enthält alle angebotenen Pizzen. Sie werden eindeutig durch eine ID identifiziert, haben einen
Namen, einen Verkaufspreis, sowie die geschätzte Herstellungsdauer und bis zu 4 Zutaten. Tomaten,Käse
sind auf jeder Pizza, daher nicht extra erwähnenswert)
Pizza_id Name Preis Herstellungsdauer (min) Zutat1 Zutat2 Zutat3 Zutat4
2 Salami 4,50 8 3
3 Schinken 4,50 8 4
5 Hawaii 5,00 11 4 10
.....
Zutaten
(Diese Tabelle enthält alle vorhandenen Zutaten für die Pizzen. Dabei hat jede Zutat eine
eindeutige ID. Außerdem ist jede Zutat mit einem Einkaufspreis und der vorhandenen Menge gekennzeichnet.)
id name Kilo-/Stückreis Vorratsmenge(kg/stück)
1 Tomate 2,99 80
2 Käse 3,50 100
3 Salami 1,00 50
4 Schinken 2,00 50
7 Ei 0,1 50
10 Ananas(Dose) 1,99 30
....
Ok.. mehr fällt mir erstmal nicht ein .
Zitat:
Dabei müsst ihr die gesamte Produktionskette von der Lieferung der Zutaten über
den Bestellvorgang bis hin zur Lieferung und Bezahlung der fertigen Pizzen berücksichtigen.
Das klingt so wichtig Ka ob alles berücksichtigt ist.
EDIT: toll, hat meine Einrückungen nicht übernommen . Jetzt sind die Tabelleninhalte etwas zusammengestaucht.
Dieser Beitrag wurde verfasst vom Benutzer: Meister-Petz
brauche auf die schnelle hilfe, morgen soll es abgegeben werden....
Zitat:
Zeichne das Zustandsdiagramm eines deterministischen endlichen Automaten, der genau die Wörter
aus {a, b}∗ akzeptiert, die als vorletztes Symbol kein b haben. Begründe kurz die Korrektheit des
entwickelten Automaten.
Fertigt außerdem ein zu diesem Automat äquivalentes Syntaxdiagramm an, das keine Rekursion
enthält.
Hinweis: Verwende als Zustandsnamen im endlichen Automaten die zuletzt gelesenen zwei Symbole.
Es reichen vier Zustände! Auch das leere Wort soll akzeptiert werden.
und
Zitat:
Betrachte den rechts dargestellten deterministischen, endlichen Automaten. Umgangssprachlich
(d.h. mathematische Notation, z.B. mit Symbolen und Operatoren aus der Mengenlehre, ist nicht erforderlich, aber dennoch muss die Umschreibung klar und präzise sein) ist zu umschreiben: Welche Sprache wird durch diesen Automaten akzeptiert? Gib eine äquivalente rechts-lineare
Typ-3-Grammatik an!
das entsprechende diagramm hier:
sorry fürs belästigen...aber haut rein, ich brauchs....
gruß
der friese
Neulich, im Wetterbericht:
"...gegen Abend wird es zunehmend dunkler...."
Dieser Beitrag wurde verfasst vom Benutzer: DerFriese
nette erste aufgabe. Der Tip in der Bemerkung liefert sehr schnell die richtige Lösung:
Man soll für die Namen der 4 Zustände jeweils die beiden zuletzt gelesen Buchstaben nehmen.
Also haben wir die Zustände
AA, AB, BA, BB
Nun fehlen die Transitionen zwischen den Zuständen. Da der Automat deterministisch ist und das Alphabet aus 2 Zeichen besteht, die bis auf eine Ausnahme, belieb angeordnet werden können, besitzt jeder Zustand genau zwei ausgehende Transitionen, jeweils eine fürs a und eine fürs b.
hier keine Auflistung aller Transitionen
AA -- a --> AA
AA -- b --> AB
AB -- a --> BA
AB -- b --> BB
BA -- a --> AA
BA -- b --> AB
BB -- a --> BA
BB -- b --> BB
Nun stellt sich dir Frage nach dem initialen Zustand und den terminalen Zustäden.
Wir wissen, dass auf alle Fälle ein Ende der Form BA und BB (wegen keinem b an vorletzter Stelle) keine terminalen Zustände sind. AA und AB, erfüllen die Bedingung für gültige Wörter. Das vorletzte gelesene Zeichen ist kein b.
Was ist jetzt dar initiale Zustand?
Der Automat soll das leere Wort erkennen, also kann es nur eines der Terminalen Zustände sein, weil die Zustände BA und BB das Lesen eines Zeichens erfordern. Also bleiben nur noch AA und AB übrig.
AB kann es nicht sein, weil wir mit diesem Zustand keine Wörter der Länge 1 erzeugen können, keine Transition führt direkt zu einem terminalen Zustand. Dies ist ganz anders beim initialen Zustand AA, hier können die Wört a und b erzeugt werden.
ich weis nicht ob das weiter Hilft aber das habe ich bei google gefunden: klick
rofl...
danke....da ist genau unsere aufgabe und so wie ich die sache sehe, sie ist von gestern, gestellt von einem user, der seit gestern angemeldet ist....
werde ich wohl mal am donnerstag fragen müssen, wer von den füchsen sich da angemeldet hat....
@mapo
vielen dank für deine erklärenden ausführungen, mit ein wenig gehstützen erscheint das ganze halb so wild, nur das darauf kommen ist eine sache für sich....
gruß
der friese
Neulich, im Wetterbericht:
"...gegen Abend wird es zunehmend dunkler...."
Dieser Beitrag wurde verfasst vom Benutzer: DerFriese
Du kannst keine Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum nicht antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen.
!
... was für Informationen brauche ich wenn ich nen Pizzadienst habe... super Aufgabe 
(Verbessungsvorschläge, Ergänzungen, usw. willkommen 
