Theoretische Informatik Sprache Alphabet Wort

Question

Hilfe! Ich beschäftige mich schon einige Tage mit der Fragestellung und habe keine Ansätze.

(a) Sei Σ ein Alphabet.
Gilt λ ∈ Σ? Begründen Sie Ihre Antwort mit eigenen Worten.
(b) Sei Σ = {01,2} und w=01 ein Wort über Σ. Geben Sie ∥Σ∥ und |w| explizit an. Begründen Sie.
(c) Sei Σ = {†,¶,©} und L = {†©,¶†,†} eine Sprache über Σ. Geben Sie L0 und L2 explizit an. Geben Sie zudem ∥L3∥ an.
(d) Betrachten Sie Regeln der Form p→q mit p∈N+ und q∈NΣ∪ΣN.
Geben Sie für Σ = {Ð,t,Ó} und N = b,m,B eine Regel an, die diese Form erfüllt, und eine Regel, die sie nicht erfüllt. Begründen Sie Ihre Aussagen.

e) Negieren Sie folgende Aussage:

(∃n ≥ 1)(∀x : |x| ≥ n)(∃u, v, w ∈ Σ∗)[x = uvw ∧ |uv| ≤ n ∧ |v| ≥ 1 ∧ (∀i ≥ 0)[uviw ∈ L]]

Comments

Gilt λ ∈ Σ?

Was ist λ?

Sei Σ = {01,2}

Hast du hier ein Komma vergessen?

Geben Sie ∥Σ∥ und |w| explizit an.

Was ist ∥Σ∥?

Geben Sie L0 und L2 explizit an.

Was bedeuetet L0 und L2 , wenn die Sprache L gegeben ist?

p∈N+ und q∈NΣ∪ΣN.

Wie sind N+ und NΣ∪ΣN definiert.

N = b,m,B

Fehlen hier Mengenklammern?

Answer 1

Negieren Sie folgende Aussage:

(∃n ≥ 1)(∀x : |x| ≥ n)(∃u, v, w ∈ Σ∗)[x = uvw ∧ |uv| ≤ n ∧ |v| ≥ 1 ∧ (∀i ≥ 0)[uviw ∈ L]]

(∃n ≥ 1)[φ] ist eine Abkürzung für (∃n)[n ≥ 1 ∧ φ].

(∀x : |x| ≥ n)[φ] ist eine Abkürzung für (∀x)[|x| ≥ n → φ].

Negation von (∃v)[φ] ist (∀v)[¬φ].

Negation von (∀v)[φ] ist (∃v)[¬φ].