Informatiker Board | Druckvorschau: Zeige, dass eine Sprache nicht regulär ist.

Geschrieben von Lisa.Neust am 18.01.2019 um 11:26:

Zeige, dass eine Sprache nicht regulär ist.

Hallo, ich soll zeigen, dass eine Sprache nicht regulär ist, natürlich mit Hilfe des Pumping Lemmas.

Könnte mein Beweis so funktionieren? Ein Antwort wäre sehr sehr nett, ich verzweifle hier langsam an diesem Thema und bekomme es einfach nicht hin.
Aufgabe:
Zeigen Sie mit Hilfe des Pumping Lemmas, dass $[latex]M = \left\{ a^ma^lcb^{m+l}\mid m,l \in N \right\} [/latex]$ mit $[latex] \sum =\left\{ a,b,c \right\}[/latex]$ keine reguläre Sprache ist.

Mein Versuch:
Als erste würde ich gerne das $[latex]M = \left\{ a^ma^lcb^{m+l}\mid m,l \in N \right\} [/latex]$ ändern zu $[latex] M = \left\{ { a }^{ 2n }c{ b }^{ 2n }\mid n \in N \right\}[/latex]$ sollte ja äquivalent sein?

Beweis:
Sei $[latex] n \in N beliebig. [/latex]$ Wähle das Wort $[latex]w = { a }^{ 2n }c{ b }^{ 2n }\in M [/latex]$ mit $[latex] |w|\ge n [/latex]$ . Sei [latex] w=xyz[/latex]

eine Zerlegung mit $[latex]y\neq \lambda [/latex]$ und $[latex] |xy|\le n[/latex]$ . Dann haben wir $[latex]x={ a }^{ 2i } [/latex]$ , $[latex]y={ a }^{ 2j }[/latex]$ und $[latex] z={ a }^{ 2n-2i-2j }c{ b }^{ 2n }[/latex]$ für $[latex] j\neq 0[/latex]$ und $[latex] 2(i+j)\le 2n[/latex]$
Nun wählen wir [latex] k=0[/latex]

. Damit folgt $[latex]x{ y }^{ 0 }z = { a }^{ 2n-2i }c{ b }^{ 2n } [/latex]$ und somit $[latex]x{ y }^{ 0 }z = { a }^{ 2n-2i }c{ b }^{ 2n } [/latex]$ weil $[latex]2n-2i\neq 2n [/latex]$ für $[latex] j\neq 0[/latex]$ . Smit ist M nicht regulär.

Vielen Dank im Voraus