Informatiker Board | Suchergebnis

Informatiker Board » Suche » Suchergebnis

» Hallo Gast [Anmelden|Registrieren]

Zeige Beiträge 1 bis 11 von 11 Treffern

Autor

Beitrag

Thema: 2 Klausuraufgaben (reguläre Sprachen)

margin

Antworten:	8
Hits:	10.907

08.10.2013 18:50

Forum: Theoretische Informatik

Zitat:

Original von Karlito
Wird dieser Zustand wieder mit einem anderen Element x aus Sigma verlassen, fliegt einem der Ansatz, die 'a' durch Epsilon zu ersetzen um die Ohren.

Da habe ich doch glatt was übersehen, Danke für die Korrektur.

Zitat:

Original von Karlito
Der ursprüngliche Finalzustand wird aus der Menge der Finalzustände gestrichen, wenn es keine reflexive Transition mit 'a' zu diesem Zustand gibt.

Und wenn der durch 'a' erreichte Finalzustand kein Zyklus besitzt, durch welchen er wieder mit Eingabe 'a' von einem beliebigem Vorgängerzustand erreicht werden kann.

Thema: Entscheidbarkeit von endlichen Mengen

margin

Antworten:	15
Hits:	12.932

04.10.2013 17:50

Forum: Theoretische Informatik

Entschuldige die lange Pause. Ich habe mich noch mal ausgiebigst bei meinem Mentor erkundigt.

Also $[latex]M=\{5 \in M \Longleftrightarrow [/latex]$ TM x hält bei Eingabe 5 $[latex] \}[/latex]$ kann man umformulieren in:

$[latex] y \in M [/latex]$ gdw. TM x hält bei Eingabe y und y = 5. Wir definieren die charakteristische Funktion von c_M(y) für M wie folgt:
[latex]c_M(y)=1[/latex]

, falls TM x bei Eingabe y und y=5 hält. Sonst [latex]c_M(y)=0, sonst[/latex]

.
Es können zwei Fälle können eintreten:
1.) TM x hält bei eingabe 5
2.) TM x hält nicht bei Eingabe 5

1.) [latex]c_M(y)=1[/latex]

, falls y=5
[latex]c_M(y)=0[/latex]

, sonst

2.)
[latex] c_M(y)=0[/latex]

für alle y

c_M ist in allen beiden Fällen berechenbar, entweder ist $[latex]M=\{5\}[/latex]$ oder $[latex]M=\{\}[/latex]$ . Somit ist M entscheidbar.

Thema: 2 Klausuraufgaben (reguläre Sprachen)

margin

Antworten:	8
Hits:	10.907

04.10.2013 16:29

Forum: Theoretische Informatik

Ich bezweifele, dass dort Nerode helfen wird, da es voraussetzt, was L/a für eine Sprache ist. Da L aber unbekannt ist, können wir L/a nicht genau bestimmen. Es reicht nicht zu wissen, das L regulär ist.
Back to topic. Ich würde nicht mehr L betrachten, sondern $[latex] L \cap \{wa: w \in \Sigma^*:a \in \Sigma\}[/latex]$ , was wieder ein regulärer Ausdruck ist, nennen wir ihn E. Die Endzustände des Automaten von E wären dann nur noch über a erreichbar. Durch Abändern dieser Transitionen, so dass nicht mehr über a, sondern nur noch über $[latex]\epsilon [/latex]$ in den Finalzustand gewechselt werden kann, resultiert zu dem, was verlangt wurde, L/a. Dieser Automat sollte daher auch wieder regulär sein.
Ein anderer Ansatz wäre, E genauer zu untersuchen. E=va, so dass [latex]va = L[/latex]

. Es ist bekannt, dass a regulär ist, jedoch gibt es keine Info darüber, ob v auch regulär ist. Denn es gibt Fälle, wo aus einer regulären und einer nicht-regulären Sprache eine reguläre entstehen kann. Nach meiner Meinung müsste aber durch die Konkatenation einer Typ-X Sprache und einer endlich regulären Sprache, a, wieder eine Typ-X Sprache entstehen. Folglich wäre das wieder eine reguläre Sprache, so nach der Behauptung. Ein Beweis dazu, ist mir leider nicht bekannt. Ich hoffe, ich konnte euch weiterhelfen, lasse mich jedoch gerne vom Gegenteil überzeugen.

Thema: Entscheidbarkeit von endlichen Mengen

margin

Antworten:	15
Hits:	12.932

24.07.2013 19:53

Forum: Theoretische Informatik

Zitat:

Original von Karlito
Wir haben die selbe Auffassung des Begriffs unendlich. Ich glaube wir haben nur aneinander vorbei geredet. Und dass es unendlich viele TM gibt, da sind wir uns doch einig, oder?

VG,

Karlito

Ja, sind wir. Trotzdem verwirrt mich das ganze ein bisschen. Also weil meine Menge M von einer unendlichen Menge abhängt, ist meine Menge M auch unendlich, obwohl keine TM Element meiner Menge M ist, oder?
Vielen Dank für deine Geduld.

Thema: Entscheidbarkeit von endlichen Mengen

margin

Antworten:	15
Hits:	12.932

23.07.2013 21:50

Forum: Theoretische Informatik

Zitat:

Original von Karlito
Da du das nicht weißt, führst du den Beweis ja für eine beliebige Turingmaschine x aus der Menge der Turingmaschinen. Also faktisch für alle Turingmaschinen.

Nur das die Menge aller Turingmaschinen eben nicht M selber ist, sondern die Menge des Eingabewortes oder halt leer.
Wir haben anscheinend unterschiedliche Vorstellungen von Unendlichkeit einer Menge. Für mich ist eine Menge M unendlich, falls sie unendlich viele Elemente besitzt:
$[latex] $|M|=\infty$[/latex]$
und endlich, falls:
$[latex]$|M|=n \quad n \in \mathbb{N}$[/latex]$
Meine Menge M ist doch endlich, da sie entweder das Element 5 oder kein Element besitzt.
Kannst du mir folgen?

Thema: Entscheidbarkeit von endlichen Mengen

margin

Antworten:	15
Hits:	12.932

23.07.2013 20:41

Forum: Theoretische Informatik

Ich merke gerade selber, dass ich eigentlich das spezielle Halteproblem auf mein Problem reduziert habe.
$[latex]$ K \le M \quad K \text{ ... spezielles Halteproblem} $[/latex]$ .
Rein faktisch ist ja die Menge M endlich, aber ich kann es nicht nachweisen, da die Prämisse unentscheidbar ist. Man kann also nicht sagen, ob $[latex] $M=\{\} \vee M=\{5\}$ [/latex]$
Ist diese Argumentation richtig?

Thema: Entscheidbarkeit von endlichen Mengen

margin

Antworten:	15
Hits:	12.932

23.07.2013 12:12

Forum: Theoretische Informatik

Nein, es handelt sich um eine fest vorgebene TM. Stell dir vor, du bekommst ein Code-ausschnitt zu sehen. Und man würde dich Fragen, ob dieses Programm bein Eingabe 5 hält. Damit ist die Eingabe und die Menge der TM endlich, da du nur konkret eine TM vorgegeben bekommst.

Thema: Entscheidbarkeit von endlichen Mengen

margin

Antworten:	15
Hits:	12.932

23.07.2013 11:54

Forum: Theoretische Informatik

Ne, die TM x soll fest sein, nicht variabel.. Stell dir vor, es wäre das Collatz Programm. Bei manchen Eingaben ist beim Collatz-Programm bis heut nicht feststellbar, ob es hält oder nicht.

Thema: Entscheidbarkeit von endlichen Mengen

margin

Antworten:	15
Hits:	12.932

23.07.2013 11:06

Forum: Theoretische Informatik

Danke für deine Antwort,
Naja, die Menge
$[latex] $M=\{5 | \text{TM x hält bei Eingabe 5}\} $ [/latex]$
ist offensichtlich endlich, aber ist sie entscheidbar?

Thema: Diagonalisierungsargument.

margin

Antworten:	1
Hits:	4.284

22.07.2013 21:07

Forum: Theoretische Informatik

Kannst du uns den Begriff Universalität bzw. n-universell näher erklären? Von den Begriffen habe ich noch nie was gehört.

Thema: Entscheidbarkeit von endlichen Mengen

margin

Antworten:	15
Hits:	12.932

Entscheidbarkeit von endlichen Mengen 22.07.2013 19:14

Forum: Theoretische Informatik

Endliche Mengen sind ja entscheidbar. Da man bei gegebenen Element die Menge nach diesem Elmenet durchsucht. Man terminiert, da endlich. Aber was ist mit dieser Menge:
M={5| TM x hält bei Eingabe 5}
X sei dabei eine feste TM.
Was mache ich falsch?
PS:
Gibt es hier Latex-Hervorhebungen?
Funktioniert der erweiterte Editor auch mit openjdk? Der erweiterte Editor scheint nur bei oracle jdk zu funktionieren.

Zeige Beiträge 1 bis 11 von 11 Treffern