Einführung in die
Theoretische Informatik
ZUSAMMENFASSUNG
,#. GRUND BEGRIFFE
DEFINITIONEN
Alphabet [ endliche
Menge (z B [ (0 13) leeres Wort E
· =
·
:
.
.
,
~
S :
Menge aller Wörter über E
·
leere Menge
Wort endliche Zeichen [mit Länge (w) (z B 101)
w
Folge
· :
vom aus .
.
·
Konkatenation UV :
über zwei Wörter
un mit wa =
ww
L [ *:
·
Formale Sprache =
Feilmenge aller Werter
>
-
AB =
(uv(u = Arv = B3 z .
B .
(ab b3/a , bb3
,
=
Laba , abbb , ba , bbb)
>
-
A =
&W ... Wmlwe ....
Wa E AS
Swe WneA3 Unew An 12
*
A Wn/m 10 13
*
>
-
= . - ·
= 0 - W .. . . .
=
z .
B .
4013 =
,
01 ,
0101 , 010101 .... 3 +
,
>
-
At =
A ** = Unze Am z .
B. [t :
Menge aller nicht leeren Wörter über [
IDENTITÄTEN LEMMA
· wo =
E
·
DA =
0 ·
Ax =
0 ·
A(BUC) =
ABvAC
·
A =
<23 ·
0t =
0 ·
(AUB)C =
AC vBC
· VA :
de **
·
0" =
(E)
A 123A A
*
· **** = ·
=
.1
2
. Grammatiken
Grammatik G = (V E , ,
P, S
V Nichtterminalen/Variablen B A B C
,
Menge
> : end aus z
-
.
.
.
, ,
. . .
E
Menge aus Terminalen/Alphabet
>
- :
end Z B a ,
b , c . . . und Sonderzeichen wie +,,...
,
. .
.
(vE) X (VvE)"
*
Pe (G B)EP
Menge Produktionen -B ,
>
B. wird
geschrieben
-
: vo n z .
als
,
-
und statt Bel ... Br
-
Br x +
pr : X +
(Vus)
. . .
z .
B. < , B ,
j e
>
-
SeV :
Startsymbol
Jede Grammatik VVE
induziert eine
Ableitungsrelation a auf Wörtern über
· - :
( +
ax)( =(B +
Bi = P 17m ,
a2 :
x =
2 Bd -1x
=
&Bd
Die Sequenz de Taxi-G Im ist die
Ableitung von an aus an
·
. . .
,
S [ *, G das Wurt
d h wenn In und In e dann
erzeugt an
=
. . .
Swe /S-W]
*
=> Eine
Sprache L(G) ist die aller Werter die G erzeugt
Menge werden
= von
,
.
~ ingenauan ,
mit Reflexive Transitive Hülle +* B :
EFR :
Lip and
(x + B : < = (n > 0 : d +
aß)
Typische Grammatik !
Finde die einer
gegebenen Sprache
Fragen
:
(nicht) !
Zeige das ein bestimmtes Wort einer
gegebenen Grammatik erzeugt werden kann
·
von
Ist L(G) ? G und we [
WORTPROBLEM wenn
gegeben
:
we .
·
2
. 2 .
Chomsky- Hierarchie ((Typ 3) <
L(Typ 2) <
L(Typ 1) <
<(TypO)
Typ O
Phasenstrukturgrammatik rekursiv aufzählbare Sprachen
: immer
Typ 1 Fontextsensitive Grammatik Kontextsensitive Sprachen wenn F(d +
B)eP1(S + E) :
kk/B/
Typ 2 : Kontextfreie Grammatik =Kontextfreie Sprachen wenn
Typ 1 und F(x + B) = P : EV
Typ 3 : Rechtslineare Grammatik =
Reguläre Sprachen wenn
Typ 2 und F(d +
p)zP((s + e) :
DeSuEV
,# REGULÄRE SPRACHEN
Automaten AG :
DFA-Deterministischer endl . Automat M =
(Q ,
E , 6 , 90 ,
F)
abstrakte
Beschreibung eines
Programms
Lösung wortproblems.
>
-
zur eines z B
Q endl
.
.
Menge Zustanden
·
:
.
von
·
[ : endl .
Eingabe alphabet
J QX[-Q totale
Übergangsfunktion ergänge
i Transitionen
·
: :
ausanne
·
qeQ :
Start zustand
F Q Menge Endzuständen
·
:
& von
18 (90 EF
*
-
von M akzeptierte Sprache
: w[ ,
w)
Ö (9 2)
-
*
mit Qx[ Q definiert durch
9
+ : =
:
,
* = (O(g a) w) für acS we
*
(q , aw) =
, , ,
mit
Eigenschaften :
(g , a) =
o(g ,
a)
= (g , wal = 0 ( (g w) , ,
a)
:
BEISPIELE
B
-
BEWEIS
- wELCN)
:
LEMMA El
<
(490] w)nF =
,
(4903 w)E Fr
,
·
Für
jede rechtslineare Grammatik G :
J DFAM mit ((M) =
L(G) ( we L(M)
W
für N =
(Q E
, ,
5 ,
90 , F)
rechtslineare Grammatik G JNFAN mit L(N) L(G) M (P(Q) 0 59 3 , FM)
=
E,
Für jede
=
2 : , ,
.
~
Für jeden NFAN : 7 DFAM mit ((M) =
L(N)
↳ für einem NFA mit n Zuständen DFA bis zu 2 Zustände
Für DFAM J rechts lineare Grammatik G mit L(G) L(M)
jede
· : =
↳
S
Q 2
3
· v =
T =
, S =
go
,
Beweis Für M =
(Q , 2 5 90 E) ·
(g) (d(qu a)
92
agz) P(
: , > =
=
L(M)
,
,
= ,
-
gibt es Grammatik G =
(V , T , P , S) :
(q + a) = P( G(q1 a) ,
= F
=>
L(G) =
#
·
(q >
-
E)[P( =
90
EF
NFA-Nicht deterministischer endl . Automat N = (Q ,
[ 5 90 , , ,
F)
- Zeichen
gleiche ein
untersche
·
Q ,
[ , go ,
F wie bei einem DFA z .
.
B
·
d :
Qxz -
P(Q) /
mit PCQ) :
Potenzmenge (Menge aller
Teilmengen von Q =
2Q)
2 von 5 :
Qx[ +
P(Q)
auf = :
P(a) x 2 +
P(Q) ~ (S a) ,
:= V o(g a) ,
ges
aller Zustände die sich von einem
(S w) Menge
,
P(Q)x[ -P(Q)
*
und :
,
:
Zustand ins aus mit w erreichen lassen
.
-
von Nakzeptierte Sprache /karh
: whnF 0) ,
+
, E-NFA-NFA mit
-Übergangen -
Z .
B
.
E-Übergänge
ausgeführtwerden eine
dürfen
,
ohn
ser
-
W wird)
=
NFA mit [ , so dass G : Qx([v(3) +
P(Q)
E)
LEMMA
B
Für -NFA N
jeden
·
:
=> NFA N' mit L(N) = L(N)
=>
Die Automatentypen & ) sind alle
leich mächtig
·
x +
aYX + Y
F
erkennen alle mit Produktionen Gestalt ·X-a X+
und
Sprachen folgender : .
Reguläre Ausdrücke -
altemative Definition von Sprachen über einen
gegebenen Alphabet &
Fac
D ist
regulärer Ausdruck a ist
regulärer Ausdruck
-
und
· · :
·
E ist
reguläre Ausdruck ·
Fx Bregex ,
: auch alß AB , ,
Sindet
~
bindet
Stärker Stärker
zu einem
regulären Ausdruck j
~>
Sprache (G) definiert durch : ·
((0) =
0 ((x B)
·
=
((x)((B) und :
((t)
·
=
(5) ((1p)
· =
(() r((p)k =
B2
= ((x) =
((B)
·
((a) =
4a] ((x )
·
2
=
L(x)
SATZ (Kleene) NFA mit
RE-Übergangen :
*
Eine Sprache LE ist dann durch
*
genau Ein wort we & wird von M
akzeptiert Et
S
regulären Ausdruck darstellbar Menthalt ...
einen , einen
Pfad/Lauf g in enthalt
wenn sie
regulär .
ist DFA der die sprache erzeugt. --
sodass we
L(01(z .
.
. .
Un)
r
Beneis .
B > >
M
z +
-
: . ~
L
von mithilfe von
Gleichungssystem :
Du mit
ARDElVS
x <X( = X =
*
B
L
=
LEMM A
·
+
Gauß 'schen Eliminierungsverfahren
( -
ineinander
auflosen
einsetzen und
bis :
(balab))
2
*
Z B
. .
X = (aalbbl Cab Iba) (aalbb)2
F) RE ((M) (()) I DENTITÄTEN RECHENREGELN
E
von -NFAM =
(Q 2
, ,
8 , 91 , zu
= : =
110
ga 2
((p)(j x((b(j)
= =
& transformation
·
Automaten =
in äquivalente
·
mit
al einem Endzustand
6
02 =
10 = 0 ·
(B)u =
x(By)
B
7
z
BIG
. .
+
=
alB
= =
b) et z
Anfangszustand
·
übergänge
·
ohne in
·
c) Endzustand E ·
xx = X
ohne
Übergänge aus
a(pij)
+
2xY
② 2 =
aBlxy
= ·
↳ ersetze mehrere
Übergange von
q
nach
p zu einem
21d2* = X
Anfang (x)piy
oder
xy/By
↳ entferne iterativ alle Zustände die nicht Ende sind 6
·
=
&
22 = XXY
27
*
Z .
B
.
⑳ (x ) *
=
Elk" (a(t)2
*
O = L ·
=
2
, Satz von Redko :
gültigen Äquivalenzen gültigen Äquivalenzen
Es
gibt keinen Satz von aus denen sich alle
herleiten lassen .
i
für
*
[ De
R Rz reguläre Sprachen Morgen
&
,
Re , ,
auch :
diese können auch die
sie
·
Ri Rz ·
Ren Ra ·
RY ·
RR sprachen
mit der
erzeugt
DFAS werden
ReIReoR( IR)
*
·
RURz ·
=
E PRODURTKONSTRUKTION
yEndzuständen ↳ MERRE L17( (n[z
.
=
0
wenn man DFA mit vertauschten
erzeu Komplement der
Sprache
das ...
baut ,
man
z .
B
&
FXFz
Produkt automat
=
-on DFAs (FXQ2)r(QxE)
↓
Für Me =
(Qe ,
E ,
En ,
Se , Fel und
&
Mz =
(Q2 ,
[ da , ,
Sa ,
Fal DFAS, mit Beweis :
weL(M) *
von NFAs :
G((q1 92) a) , ,
dann ist
= G((se w)e FixFz
Can al
( Sa)
, ,
anax de
↳ ( a))
= (S w) z(sa w))eFxFz ((x y)(x G(gu a)
y (Gz(q2
=
, , ,
, , , ,
al = (s ,
w) Fx(s ,
w)EFz
= weL(Mi) 1 weL(M2)
eine DFA der LCM)nL(Mz) . < >
L(M) eL(Mz)
erzeugt
we
=
,
Lemma
Pumping ~um zz ,
das eine
Sprache nicht regulär
ist ...
A
*
Sei R [
=
regulär Beweis :
Sei R L(A) mit DFA A (Q 2 0 F) :
=
90
=
, , , ,
= 7n > 0 : FZER mittzl = h : Sei n =
(Q) und z =
an .... Am ER mit man ,
pop,
> Zerlegung
-
z =
UVW so das sodass .... pm
go
=
,
= E
70j2n Pi
w
.
h
V =>
Pj d
: =
, .
·
Inv1 = n Z =
de di Rits---
Ajm ... d z
j
. . .
.
- - -
·
Fi20 : uviweR U
V W
erfüllt alle
genannten Bedingungen
.
=
notwendige ,
aber nicht hinreichende
Bedingung für reguläre Sprachen
#
↳ spielbasierte Formulierung R L(M) dann ist
wenn
regular
: =
,
1Qml für R
·
Spieler I wählt eine Zahl n> 0 eine
Pumping-Lemma-Zahl
·
Spieler #I wählt ein Wort zeR mit IzlIn
·
Spieler I wählt eine
Zerlegung uvw von n Beispiele :
Gabi lie N] nicht
ist
regulär
· =
In VZJzerlegung
-
d h
. .
Rregulär Spieler I hat
Gewinnstrategie ! ·
↳ =
40m2 /m= 0 3 ist nicht
regulär
Richt !
Spieler I hat Gewinnstrategie
=
regulär Sprache der arith Ausdrücke ist nicht
regular
·
.
Fr7z
Verlegungen
Entscheidungsprobleme für
reguläre Sprachen
entscheidbar
Ein EP ist ,
wenn es einen
Algorithmus gibt,
endlicher Zeit Antwort findet.
der bei
jeder Eingabe in die
richtige
rechtslineare
Für Dein DFA/NFA / RE/ Grammatike : M N
eine
·
WORTRROBLEM :
geg .
W , D : weL(D) ? >
-
für DFA/NFA entscheidbar in OCIwl + 1M1) / O(IQ1Iwl + IN)
OCIQI/EI)/O(IQK(21) imaxia
es
·
LEERHEITSPROBLEM :
D : L (D) =
0 ? ~
für DFA/NFA entscheidbar in
z
geg .
·
ENDLICHKEITSPROBLEM : D :
L(D) endlich ? - für DFA/NFA entscheidbar
geg .
OCIQlIQalIEK)/5(21911 1921
+
L(De) 2(Di) ? für DFA/NFA/RE entscheidbar
geg DrDn
~
·
AQUIVALENEPROBLEM : .
: =
in
