Informatiker Board | Suchergebnis

Informatiker Board » Suche » Suchergebnis

» Hallo Gast [Anmelden|Registrieren]

Zeige Beiträge 1 bis 1 von 1 Treffern

Autor

Beitrag

Thema: Zeige, dass eine Sprache nicht regulär ist.

Lisa.Neust

Antworten:	0
Hits:	2.455

Zeige, dass eine Sprache nicht regulär ist. 18.01.2019 11:26

Forum: Theoretische Informatik

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

Zeige Beiträge 1 bis 1 von 1 Treffern