Informatiker Board | Theoretische Informatik | Zeige, dass eine Sprache nicht regulär ist.

Informatiker Board » Themengebiete » Theoretische Informatik » Zeige, dass eine Sprache nicht regulär ist.

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Zeige, dass eine Sprache nicht regulär ist.

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Lisa.Neust
Grünschnabel

Dabei seit: 18.01.2019
Beiträge: 1

Zeige, dass eine Sprache nicht regulär ist.

Zitatantwort auf diesen Beitrag erstellen

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Lisa.Neust: 18.01.2019 12:05.

18.01.2019 11:26

Nehmen Sie Lisa.Neust in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Zeige, dass eine Sprache nicht regulär ist.