0 Daumen
965 Aufrufe

Aufgabe:

- \( A_{1}=\left\{w \mid M_{w}\right. \) hält auf \( w \) und hat mindestens 128 Zustände \( \} \)

\( -A_{2}=\left\{\left.w \in\{0,1,2\}^{*}|| w\right|_{0}=|w|_{2}\right\} \)
- \( A_{3}=\left\{w \mid M_{w}\right. \) hält nicht auf Eingabe \( \left.w\right\} \)
- \( A_{4}=\left\{\left.w \in\{0,1,2\}^{*}|| w_{0}|=| w\right|_{1}=|w|_{2}\right\} \)
- \( A_{5}=\left\{a^{n} b^{m} \mid n \not \equiv m(\bmod 42)\right\} \)
\( -A_{6}=\left\{w \in\{0,1\}^{*} \mid\right. \) enthält das Teilwort 111 und endet auf 11\( \} \)

Zu welcher Sprache der Chomsky Hierachie gehören diese Sprachen?



Problem/Ansatz:

A1 ist Typ0

A2 Typ 2

A3 Typ 0

A4 typ 2

A5 Typ 3

A6 Typ 1

STimmt das ?

Avatar von

Was ist \(M_w\)?

1 Antwort

0 Daumen

\(A_2\) und \(A_5\) hast du richtig eingeordnet. \(A_6\) ist Typ 3.

\(A_4\) ist nicht Typ 2. Das kann man mit dem Pumping-Lemma für kontextfreie Sprachen zeigen.

Avatar von 5,7 k

Mw ist eine Turingmaschine

Welche Turingmaschine ist \(M_w\)?

Irgendeine. Die wurde in den übungen auch nur als Mw bezeichent leider... Das kam in der Form immer mit den Halteproblemen in Verbindung

\(M_w\) ist mit Sicherheit nicht irgendeine Turingmaschine.

\(A_4\) ist nicht Typ 2. Das kann man mit dem Pumping-Lemma für kontextfreie Sprachen zeigen.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community