Zeige, dass eine Sprache nicht regulär ist.

18.01.2019, 11:26	Auf diesen Beitrag antworten »
Lisa.Neust	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 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 . 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

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »