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.)

Übersicht alternativer Lösungsvorschläge aus dem alten ILIAS-Forum

0 Pluspunkte 1 Minuspunkt
39 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!

 

Gefragt 25, Sep 2015 in 2010-N-01 von uafjv uafjv Tutor(in) (168,240 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.

 

Beantwortet 25, Sep 2015 von uafjv uafjv Tutor(in) (168,240 Punkte)  
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

 

Beantwortet 25, Sep 2015 von uafjv uafjv Tutor(in) (168,240 Punkte)  
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)
...