Theoretische Informatik: Präfix, Suffix und Zeichenlänge

Question

Frage:

Sei \( \Sigma=\{0,1\} \). Die Sprache \( L \) enthält genau die Zeichenketten \( s \in \Sigma^{*} \), die gleichzeitig die folgenden Eigenschaften haben:
- \( |s| \leq 6 \) und \( s \) hat den Präfix 00 sowie den Suffix 00.

Beantworten Sie die folgenden Fragen und begründen Sie Ihre Antworten kurz:
(i) Gilt \( L^{\prime}=L \) für die Sprache \( L^{\prime}=\left\{00 \cdot u \cdot 00 \mid u \in \Sigma^{*}\right. \) und \( \left.|u| \leq 2\right\} \) ?
(ii) Wie viele Zeichenketten \( s \in \Sigma^{*} \) gehören zur gegebenen Sprache \( L \) ?
(iii) Wie viele Zeichenketten \( s \in \Sigma^{*} \) mit \( |s| \leq 4 \) gehören nicht zur gegebenen Sprache \( L \) ?

Ich komme bei der Aufgabe nicht weiter.. kann mir jemand helfen bitte.

Answer 1

Hier sind alle Wörter aus Σ^*, die aus höchstens 6 Zeichen bestehen:

ε,

0, 1,

00, 01, 10, 11,

000, 001, 010, 011, 100, 101, 110, 111,

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111,

00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111, 01000, 01001, 01010, 01011, 01100, 01101, 01110, 01111, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111,

000000, 000001, 000010, 000011, 000100, 000101, 000110, 000111, 001000, 001001, 001010, 001011, 001100, 001101, 001110, 001111, 010000, 010001, 010010, 010011, 010100, 010101, 010110, 010111, 011000, 011001, 011010, 011011, 011100, 011101, 011110, 011111, 100000, 100001, 100010, 100011, 100100, 100101, 100110, 100111, 101000, 101001, 101010, 101011, 101100, 101101, 101110, 101111, 110000, 110001, 110010, 110011, 110100, 110101, 110110, 110111, 111000, 111001, 111010, 111011, 111100, 111101, 111110, 111111