Informatiker Board | Theoretische Informatik | kontextfrei regulär intensiv

Informatiker Board » Themengebiete » Theoretische Informatik » kontextfrei regulär intensiv

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

kontextfrei regulär intensiv

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

jassoba
Grünschnabel

Dabei seit: 04.06.2014
Beiträge: 1

kontextfrei regulär intensiv

Zitatantwort auf diesen Beitrag erstellen

Meine Frage:
Wie am beispiel (anhang) zu sehen haben wir ne sprache mit doppelt sovielen 1ern wie 0ern. Aber hängen die klassen nicht mit terminalzeichenzussammen oder so? Automat bauen is kein problem aber ich bin ein wengi verwirrt und weis nicht genau wie ich das belegen soll!

Meine Ideen:
ich weis nicht steh ein wenig auf der leitung...

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

04.06.2014 16:09

Nehmen Sie jassoba in Ihre Freundesliste auf

Joejoe
Grünschnabel

Dabei seit: 30.05.2014
Beiträge: 4

Hallo jassoba,

Eine Sprache ist regulaer (oder vom Typ 3) wenn du dazu einen NFA, DFA, regulaere Grammatik oder regulaeren Ausdruck angeben kannst.
Mit dem Pumping-Lemma fuer regulaere Sprachen oder mit dem Satz von Myhill Nerode, kannst du zeigen, dass L nicht regulaer ist.

Eine Sprache ist kontextfrei (oder vom Typ 2), wenn du eine LR(k)-Grammatik oder einen deterministischen Kellerautomaten angeben kannst.
Mit dem Pumping-Lemma fuer kontextfreie Sprachen kannst du zeigen, dass eine Grammatik nicht kontextfrei ist.

Eine Sprache ist kontextsensitiv (oder vom Typ 1) wenn du eine kontextsensitive Grammatik oder einen linear beschreankten Automaten angeben kannst.

Beachte dass folgendes gilt:

Wenn eine Sprache von Typ3 ist, so ist sie auch von Typ 2 und Typ 1.
Wenn eine Sprache von Typ 2 ist so ist sie auch von Typ 1 aber nicht von Typ 3.
Wenn eine Sprache von Typ 1 ist dann ist sie weder von Typ 2 noch von Typ 3.

Es wundert mich stark, dass du einen Automaten (DFA oder NFA), denn diese Sprache ist offensichtlich nicht regulaer! Bedenke, dass dein Automat fuer JEDES n der natuerlichen Zahlen funktionieren muss und nicht fuer ein bestimmtes! Dein Automat muesste ja wissen wieviele 0en du vorher produziert hast, d.h. er muesste die Anzahl irgendwie speichern, damit er doppelt so viele 1en erzeugen kann.

Ich hoffe ich konnte Dir helfen.

LG

13.09.2014 15:08

Nehmen Sie Joejoe in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hallo Joejoe,

danke für deinen Beitrag. Leider muss ich dich korrigieren:

Zitat:

Original von Joejoe
Beachte dass folgendes gilt:

Wenn eine Sprache von Typ3 ist, so ist sie auch von Typ 2 und Typ 1.
Wenn eine Sprache von Typ 2 ist so ist sie auch von Typ 1 aber nicht von Typ 3.
Wenn eine Sprache von Typ 1 ist dann ist sie weder von Typ 2 noch von Typ 3.

Diese Aussagen stimmen nich ganz, da Du bereits in der ersten Aussage sagst, dass jede Typ 3-Sprache auch Typ 2 und Typ 1 ist. In der zweiten Aussage widersprichst Du dem. Korrekt wäre, dass es Typ 2 Sprachen gibt, welche nicht Typ 3 sind. Analoges gilt für die dritte Aussagen und es gibt weiterhin Typ 0 Sprachen. Welchen von Turing-Maschinen akzeptiert werden können.

Kurzum, es gilt folgende Beziehung:
$[latex] Typ 3 \subset Typ 2 \subset Typ 1 \subset Typ 0 [/latex]$

Gruß,

Karlito

13.09.2014 16:20

Nehmen Sie Karlito in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » kontextfrei regulär intensiv