Turingmaschine erkannte Sprache

[VanessaM444]

Hi, ich hätte eine Frage, zu dem ich leider keine Antwort finden konnte im Internet. Vielleicht kann mir hier ja jemand helfen Und zwar wenn eine Turingmaschine
z.b ein Eingabealphabet hat welches \( \Sigma = \{0,1\} \) lautet, was wäre die erkannte Sprache? Hätte zwei Ideen, ich weis aber nicht ob die richtig sind. Meine Ideen wären
\( L(M) = \{0,1 ∣ M \:\text{akzeptiert}\: 0,1\} \) und \( L = \{0^n, 1^n ∣ n \geq 0\} \). Wäre echt nett wenn mir jemand helfen könnte

 

[lord_haffi]

Ich verstehe nicht so ganz, was du meinst. Von \( L(M) \) zu sprechen - die von einer Turingmaschine \( M \) akzeptierte Sprache - ergibt nur Sinn, wenn \( M \) komplett definiert ist. Du hast aber nur das Eingabealphabet \( \Sigma \) definiert.
Im allgemeinen kannst du aufbauend auf das Eingabealphabet alle möglichen Sprachen definieren. Z.B. alle binären Palindrome: \( L=\{w \in \Sigma^* | w = w^R \} \). (Diese wäre dann übrigens turingakzeptierbar, da es eine Turingmaschine gibt, die das für jede Eingabe in endlicher Zeit überprüfen kann.)
Der Begriff „erkannte Sprache“ sagt mir jedenfalls nix.

Kannst du vielleicht die Übungsaufgabe posten?