close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

6. Theoretische Informatik_Übung 3_Musterlösungen

EinbettenHerunterladen
Hochschule
Bonn-Rhein-Sieg
University
of Applied Sciences
Director
b-it Applied Science Institute
Grantham-Allee 20
53757 Sankt Augustin
Prof. Dr. Kurt-Ulrich Witt
Fachbereich Informatik
Mathematische und
theoretische Grundlagen der Informatik
kurt-ulrich.witt@h-brs.de
¨
Theoretische Informatik – Ubung
3 – WS 14/15
– Musterl¨osungen –
Aufgabe 1
Gegeben sei der nichtdeterministische endliche Automat
A = ({a}, {0, 1, 2, 3, 4, 5}, δ, 0, {0, 2, 5})
mit
δ
0
a {1, 3}
1
{2}
2
{1, 3}
3
{4}
4
{5}
5
{1, 3}
a) Zeichnen Sie das Zustandsdiagramm f¨ur A.
b) Konstruieren Sie mit dem in der Vorlesung vorgestellten Verfahren zu A einen a¨ quivalenten deterministischen Automaten Ad . Zeichnen Sie das Zustandsdiagramm von Ad .
c) Geben Sie L(A) formal an.
Musterl¨osung:
a) . . .
b) Die schrittweise Konstruktion liefert
δd
{0}
{1, 3}
{2, 4}
{1, 3, 5}
{1, 2, 3, 4}
{1, 2, 3, 4, 5}
a
{1, 3}
{2, 4}
{1, 3, 5}
{1, 2, 3, 4, }
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5}
und damit
Ad
=
({a}, {{0}, {1, 3}, {2, 4}, {1, 3, 5}, {1, 2, 3, 4}, {1, 2, 3, 4, 5}}, {0}, δd ,
{{0}, {2, 4}, {1, 3, 5}, {1, 2, 3, 4}, {1, 2, 3, 4, 5}})
c) L(A) = {ak | k ∈ N0 − {1}}
Aufgabe 2
Gegeben ist der endliche nichtdeterministische Automat
A = ({0, 1}, {s0 , s1 , s2 , s3 }, δ, s0 , {s3 })
1
mit
δ
0
1
s0
{s1 , s2 , s3 }
−
s1
−
{s2 , s3 }
s2
−
{s1 , s3 }
s3
−
−
Konstruieren Sie mit dem Verfahren aus der Vorlesung zu A einen a¨ quivalenten deterministischen Automaten Ad . Geben Sie die Konstruktionsschritte sowie die Komponenten und das Zustandsdiagramm
von Ad an.
Musterl¨osung:
Es gilt
δ({s0 }, 0) = {s1 , s2 , s3 } und δ({s0 }, 1) = {}
sowie
δ({s1 , s2 , s3 }, 0) = {} und δ({s1 , s2 , s3 }, 1) = {s1 , s2 , s3 }
Daraus ergibt sich der a¨ quivalente deterministische Automat
Ad = ({0, 1}, {{s0 }, {s1 , s2 , s3 }}, δd , {s0 }, {{s1 , s2 , s3 }})
wobei δd durch das folgende Zustandsdiagramm gegeben ist.
1
0
{s0 }
{s1 , s2 , s3 }
Aufgabe 3
Gegeben sei der nicht deterministische endliche Automat
A = ({ a, b }, { s0 , s1 , s3 , s4 , s5 , s6 }, δ, s0 , { s1 , s2 , s5 , s6 })
wobei δ durch das folgende Zustandstabelle gegeben ist.
a
b
s0
{s1 }
{s2 }
s1
{s3 }
{s4 }
s2
{s3 }
{s4 }
s3
{s3 }
{s3 , s5 , s6 }
s4
{s4 , s5 , s6 }
{s4 }
s5 s6
{} {}
{} {}
a) Konstruieren Sie zu A mit dem in der Vorlesung vorgestellten Verfahren den deterministischen Automaten Ad !
b) Ist Ad vollst¨andig? Begr¨unden Sie Ihre Antwort! Falls Ad nicht vollst¨andig ist, dann vervollst¨andigen
Sie Ad !
Musterl¨osung:
a) Wir erhalten
δd
{ s0 }
{ s1 }
{ s2 }
{ s3 }
{ s4 }
{ s3 , s5 , s6 }
{ s4 , s5 , s6 }
a
{ s1 }
{ s3 }
{ s3 }
{ s3 }
{ s4 , s5 , s6 }
{ s3 }
{ s4 , s5 , s6 }
2
b
{ s2 }
{ s4 }
{ s4 }
{ s3 , s5 , s6 }
{ s4 }
{ s3 , s5 , s6 }
{ s4 }
und damit
Ad = ({ a, b }, { { s0 }, { s1 }, { s2 }, { s3 }, { s4 }, { s3 , s5 , s6 }, { s4 , s5 , s6 } },
δd , { s0 }, { { s1 }, { s2 }, { s3 , s5 , s6 }, { s4 , s5 , s6 } })
wobei δd durch die obige Zustandstabelle gegeben ist.
b) Ad ist vollst¨andig, denn δd ist total definiert.
Aufgabe 4
Sei A = (Σ, S, δ, s0 , F ) ein endlicher Automat.
a) Konstruieren Sie aus A einen endlichen Automaten B mit L(B) = L(A) ∪ {ε}.
b) Begr¨unden Sie, warum f¨ur folgende Konstruktionen nicht immer L(B) = L(A) ∪ {ε} gilt.
(1) B = (Σ, S, δ, s0 , F ∪ {s0 })
(2) B = (Σ, S, δB , s0 , F ) mit δB = δ ∪ {(s0 , ε, f )} f¨ur ein f ∈ F (dabei sei F 6= ∅).
Musterl¨osung:
a) B = (Σ, S ∪ {s, f }, δ 0 , s, {s, f }), s, f ∈
/ S mit
δ 0 = δ ∪ {(s, ε, s0 )} ∪ {(s, ε, f ) | s ∈ F }
b) (1) Gegenbeispiel: Sei A = (Σ, S, δ, s0 , {}) mit (s0 , a, s0 ) ∈ δ. Es gilt also L(A) = ∅. F¨ur B gilt auf
jeden Fall nicht nur ε ∈ L(B) sondern auch ak ∈ L(B), k ≥ 0, und somit L(B) 6= L(A) ∪ {ε}.
(2) Gegenbeispiel: Sei
A = ({a, b}, {s0 , s1 }, δ, s0 , {s1 })
mit δ = {(s0 , a, s0 ), (s0 , b, s1 )}. Es gilt also L(A) = {ak b | k ≥ 0}. Die Konstruktion ergibt dann
B = ({a, b}, {s0 , s1 }, δ 0 , s0 , {s0 , s1 })
mit δ 0 = {(s0 , a, s0 ), (s0 , b, s1 }, (s0 , ε, s1 )}. Es gilt also ak ∈ L(B), aber ak ∈
/ L(A) ∪ {ε}.
3
Autor
Document
Kategorie
Gesundheitswesen
Seitenansichten
10
Dateigröße
180 KB
Tags
1/--Seiten
melden