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

Question

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!

 

Answer 1

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.

 

Comments

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)

Answer 2

Zur b)

Geht als Produktion auch:

S > SAB / lambda

AB > BA

BA > AB

A > (

B > )

?

Gruß Lars

 

Comments

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)