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 nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

0 Pluspunkte 1 Minuspunkt
43 Aufrufe

Dieser Post wurde der Übersichtlichkeit halber erstellt, um die alternativen Lösungsvorschläge aus dem alten ILIAS-Forum nicht überzubetonen. Wenn Sie neue alternative Lösungsvorschläge diskutieren wollen, sollten Sie eine neue Frage erstellen - und NICHT hier posten!

 

in 2010-N-01 von uafjv uafjv Tutor(in) (168k Punkte)  

2 Antworten

0 Pluspunkte 0 Minuspunkte

Ich bin für a) auf folgende etwas andere Lösung gekommen und würde gerne wissen, ob das auch so geht:

Annahme: L wird von einem EA A erkannt und ist damit regulär.

A habe n Zustände. Wähle nun w = (^n)^n mit w element L und |w| >=n

Seit w = xyz dann gilt laut PPL:
(1) |xy| <= n

(2) |y| >= 1

(3) Für alle i element No: xy^iz element L

Da (1) |xy <= 0 folgt xy = (^j

und da (2) |y| >= 1 folgt y = (^k und x = (^(j-k) mit j > 0 und k <= n.    z = (^(n-j) )^n

Wähle i = 0, dann gilt xy^0z = xz = (^(j-k) (^(n-j) )^n = (^(n-k) )^n ist nicht element L.

Nicht element L bildet einen Widerspruch zu (3) wodurch obige Annhame falsch ist und L ist damit keine reguläre Sprache.

 

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

das passt weitestgehend, was bei dir fehlt ist allerdings die Angabe k >= 1, da man sonst nicht auf den Widerspruch unten kommt.

Viele Grüße

Philippe (Tutor)
0 Pluspunkte 0 Minuspunkte

Zur b)

Geht als Produktion auch:

S > SAB / lambda

AB > BA

BA > AB

A > (

B > )

?

Gruß Lars

 

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

so geht das leider nicht. Zum einen ist deine Grammatik nicht kontextfrei. Bei einer kontextfreien Grammatik dürfen nur Regeln der Form  N x (N U T)* angewendet werden. Deine Regeln

AB --> BA  und

BA --> AB

sind somit nicht erlaubt.

Zum anderen bewirken aber eben diese beiden Regeln auch, dass du Wörter produzieren kannst, die gar nicht in der Sprache enthalten sind, weil du offene und geschlossene Klammern (in Form von A oder B) beliebig vertauschen kannst mit deiner Grammatik.

Viele Grüße

Lukas (Tutor)
...