Informatiker Board | formale Sprachen | Welche Sprache wird erkannt?

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Welche Sprache wird erkannt?

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

Welche Sprache wird erkannt?

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

bandchef
Mitglied

Dabei seit: 06.10.2009
Beiträge: 28

Welche Sprache wird erkannt?

Zitatantwort auf diesen Beitrag erstellen

Aufgabe: Welche Sprache erkennt M? -> Bild zum Automaten seht ihr unten!

Hi Leute!

Wie die Aufgabe ja bedeutet, soll ich die Sprache angeben, die den Automaten wie im Bild beschreibt. Ich hab mir dazu natürlich auch schon Gedanken gemacht und dabei auf das hier gekommen:

$[latex]L=\{ u1?? | u\in \Sigma^{\star} \} [/latex]$ mit $[latex]\Sigma=\{0,1\}[/latex]$

Das u in meiner Sprache soll übrigens für ein Teilwort stehen und das wiederum für die Eigeschleife am ersten Zustand q. Dann MUSS eine 1 kommenn und dann gehts weiter zu den Fragezeichen; hier beginnen dann meine Probleme.

Wenn man den Automaten anschaut, kann man erkennen, dass nach Zustand 2 noch die Zustände 1 und 0 kommen, die jeweils mit einer 0 ODER einer 1 zu erreichen sind, also quasi jeweils ein Element aus $[latex]\Sigma[/latex]$ .
Mein Problem ist nun, dass ich nicht weiß wie ich das in der formaler Mathematik ausdrücken soll...

Ich hoffe ihr könnt mir weiterhelfen!

bandchef hat dieses Bild (verkleinerte Version) angehängt:

Dieser Beitrag wurde 5 mal editiert, zum letzten Mal von bandchef: 06.05.2012 16:01.

06.05.2012 15:59

Nehmen Sie bandchef in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Das einfachste wäre wohl eine Mengenschreibweise.

Also $[latex]\{0,1\}^*\cdot\{1\}\cdot\{0,1\}\cdot\{0,1\}[/latex]$ .

Sonst gibt es noch reguläre Ausdrücke. Die sind aber je nach Definiton etwas anders. Bei mir galt das + als oder und der $[latex]\cdot[/latex]$ als Konkatenation.

Sähe also so aus:
$[latex] (0+1)^*\cdot1\cdot(0+1)\cdot(0+1)[/latex]$ .

Einfach mal bei Wikipedia schlau machen...

VG,

Karlito

06.05.2012 22:14

Nehmen Sie Karlito in Ihre Freundesliste auf

bandchef
Mitglied

Dabei seit: 06.10.2009
Beiträge: 28

Die Sache mit dem regulären Ausdruck hab ich mir auch schon gedacht. Da wir in der Vorlesung aber noch keine regulären Ausdrücke gemacht haben, kann es das als Lösung wohl eher nicht sein.

Die Mengeschreibweise wahrscheinlich schon eher. Aber wie kommt man dann von der Mengenschreibweise auf so eine Art mathematische Definition?

07.05.2012 18:06

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Achso, falsch verstanden:

Ich bin mir nicht sicher aber ich würde das so definieren:

$[latex]L = \{ u1v | u \in \Sigma^* \text{ und } v \in \Sigma^2 \} [/latex]$

VG,

Karlito

07.05.2012 21:00

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Welche Sprache wird erkannt?