close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Blatt 1

EinbettenHerunterladen
Formale Systeme
WS 2014/15
TU Dresden
Fakultät Informatik
Institut für Theoretische Informatik
Lehrstuhl für Algebraische und Logische Grundlagen der Informatik
Christel Baier, Kirstin Peters, Walter Nauber,
Raphael Höps, Vincent Knyrim, Sebastian Manecke, Susanne Stimpert
1. Übungsblatt
Hinweise zur Vorlesung finden Sie unter
http://wwwtcs.inf.tu-dresden.de/ALGI/FS/
Besprechung : 20.10.2014 − 24.10.2014
1
Aufgabe 1.1 [Operationen über Sprachen]
(749)
Seien K, L1 , L2 ⊆ Σ∗ Sprachen.
Welche der folgenden Aussagen sind korrekt?
(a)
K(L1 ∩ L2 ) = KL1 ∩ KL2
(b)
(K \ L)∗ = K∗ \ L∗
(c)
(L1 \ L2 )K = L1 K \ L2 K
Aufgabe 1.2 [Kommutativität von Wörtern]
(727)
Man beweise folgenden Satz:
Für alle Wörter u, v ∈ Σ∗ gilt: wenn uv = vu, dann gibt es ein w ∈ Σ∗ , m, n ∈ IN, so daß
u = wn und v = wm .
Aufgabe 1.3 [reg. Sprachen, reg. Grammatiken, DFA]
Gegeben seien die Alphabete A1 = {a, b} und A2 = {a, b, c},
• die reguläre Sprache L1 = {wb | w ∈ A∗1 ∧ |w|a mod 3 = 1},
def
• die reguläre Grammatik G2 = ({A, B, C}, A2 , P, A) mit P:
A → aaA | bA | cB
B → bB | cC
C → ε | bC | cB
• und der DFA M3 = ({q0 , q1 , q2 , q3 }, A2 , δ, q0 , {q1 , q2 }) mit δ:
c
b
q1
q0
b
a
b
a, c
q3
q2
a, c
2
a, b, c
(799)
(a) Gib die Sprachen L2 = L(G2 ) und L3 = L(M3 ) an, ohne dabei auf Grammatiken oder
Automaten zu verweisen.
(b) Gib für die Sprachen L1 und L3 = L(M3 ) die passenden regulären Grammatiken G1 und
G3 an.
(c) Gib für die Sprachen L1 und L2 = L(G2 ) die passenden deterministischen endlichen Automaten M1 und M2 an.
3
Document
Kategorie
Seele and Geist
Seitenansichten
5
Dateigröße
82 KB
Tags
1/--Seiten
melden