kontextfrei regulär intensiv |
| 04.06.2014, 16:09 | Auf diesen Beitrag antworten » | ||
| jassoba | kontextfrei regulär intensiv 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... |
||
|
|
|||
| 13.09.2014, 15:08 | Auf diesen Beitrag antworten » | ||
| Joejoe | 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, 16:20 | Auf diesen Beitrag antworten » | ||
| Karlito | Hallo Joejoe, danke für deinen Beitrag. Leider muss ich dich korrigieren:
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: Gruß, Karlito |
||
|
|
