Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 1 Minuspunkt
65 Aufrufe
Der RA bei a) ist meiner Meinung nach doch immer noch falsch ? Beispielsweiße akzeptiert doch der Automat das wort 21120101 oder das wort 2; der RA aber nicht oder sehe ich das falsch?
 
in REC-AI von uafjv uafjv Tutor(in) (168k Punkte)  
Bearbeitet von uafjv uafjv
0 0
Hallo zusammen,

in der Musterlösung wird der reguläre Ausdruck:

RA({0; 1; 2}) : a1 = (2*12*(02*)*1)*

als mögliche Lösung angegeben. Mir ist aber leider nicht ganz ersichtlich, wie dieser Ausdruck das Wort w := 2 akzeptiert?

Könnte mir das bitte jemand erklären?

Danke und liebe Grüße

EDIT: Der RA war fehlerhaft und ist inzwischen korrigiert. Der Beitrag wurde nicht zensiert, weil er ein Lehrstück dafür ist, wie man uns auf Fehler hinweisen sollte - mit genauer Bezeichnung der Stelle und Gegenbeispiel (und natürlich freundlich :-) ).

7 Antworten

1 Pluspunkt 0 Minuspunkte
 
Beste Antwort

zu Automat a):

Dieser lässt sich doch vereinfachen oder? d.h. b und c sind äquivalent, wobei dann die 0 und die 2 von bc auf bc geführt werden.

Aufgrund dieser Annahme habe ich diesen RA aufgestellt:

(2+1(0+2)*1)*          EDIT: Diese Lösung wurde auch im Pool aufgenommen.

Deckt dieser RA alles ab oder ist er falsch? Wenn er falls ist, warum?

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
Ja, das stimmt auch.

Viele Grüße

Lukas König
0 Pluspunkte 0 Minuspunkte

Der Automat aus a akzeptiert das Wort 21120101 nicht.

nach der ersten 2 bin ich noch im Zustand a, nach den beiden Einsen bin ich ebenfalls wieder im Zustand a, nach der nächsten 2 ebenso, dann kommt die Null, mit der kann ich aber vom Zustand a nirgendwo hinlaufen...

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 Pluspunkte 0 Minuspunkte

ist

a1 = [2*1(2+00)*0(2+11)*1]*

auch richtig?

Gruß

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
-> so wie ich das sehe fehlen in deinem regulären Ausdruck Wörter, die vom Automaten akzeptiert werden.

Nimm zum Beispiel das Wort 2121

Dieses Wort ist aber nicht Teil deines Regulären Ausdrucks, dein RA erzeugt Wörter, die immer eine 0 enthalten!

Gruß Theresa (Tutorin)
0 Pluspunkte 0 Minuspunkte

Wie sieht es mit folgender Variante aus?

a1 = (2* + 12*1 + 12*02*1)*

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
Hallo,

mach dir mal noch Gedanken zu dem Wort 1001 ;) .

eine kleinigkeit fehlt also noch aber dann könnte es passen.

LG

Basti (Tutor)
0 0
also dann

a1 = (2* + 12*1 + 12*0(00)*2*1)* ?

soll heißen, dass mindestens eine 0 gelaufen werden muss oder eine ungerade Anzahl an 0.
0 0
Hallo,

ja schon besser aber schau dir mal weiter noch Wörter an wie: 120201

du hast das jetzt mit der Reihenfolge zu strikt vorgegeben- versuch das noch freier zu gestalten (mit + oder so ;) )

LG

Basti (Tutor)
0 Pluspunkte 0 Minuspunkte

Für a): Eine Müsterlösung ist a1=(2*(1(0+2)*1)*)*

Hallo,

Ist die Lösung a1=(2*(1(0+2)*1))* mit weniger "*" auch richtig?

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
zu a) ja das geht auch so da du 2* verwendest, musst du die  2 nicht schreiben und kanns dann das * der äußeren Klammer für die mittlere nehmen ;)
LG Basti (Tutor)
0 Pluspunkte 0 Minuspunkte

Hallo,

du hast Recht, eine 2 kann mit diesem Ausdruck nicht erzeugt werden. Ich nehme an, dass nach der ersten 2* ein '+' verschluckt wurde, dann sollte es nämlich passen.

Gruß,

Adam (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
Sie haben natürlich recht, da fehlt das '+'.

Danke für den Hinweis.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König
0 Pluspunkte 0 Minuspunkte

Zu a.):

1. Glaube ich, dass in der Automatendefiniton ein ganz kleiner Fehler ist, der Startzustand müsste doch s0 (nicht a) und die Endzustandsmenge {s0} (nich{a}) lauten, oder? EDIT: Ist inzwischen korrigiert.

2. Ist RA(L(A1))=2*(2*1(0+2)*1)*2* eine gültige Antwort?

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
Hi,

zu a):
1. Ja, du hast Recht. Wird demnächst geändert.
2. ist auch eine gültige Antwort, die 2* am Anfang und am Ende wären aber eigentlich überflüssig, da man 2* auch mit dem Klammerausdruck erzeugen kann.
Gruß,
Jonas (Tutor)
...