Zusammenfassung

Einführung in die Theoretische Informatik - Zusammenfassung

0 mal verkauft

Hochschule
Technische Universität München

Ausführliche handschriftliche Zusammenfassung des Fachs "Einführung in die Theoretische Informatik" bei Prof. Estaun Esparza im Informatik-Bachelor an der TUM. Das Skript enthält die Kapitel: Grundbegriffe, Reguläre Sprachen, Kontextfreie Sprachen, Berechenbarkeit und Entscheidbarkeit, Komplexi...

[ Mehr anzeigen ]

vorschau 5 aus 16 Seiten

Zum Beispiel

Hochgeladen auf 24. august 2024
Anzahl der Seiten 16
geschrieben in 2024/2025
Typ Zusammenfassung

theoretische informatik
sprachen
reguläre sprachen
kontextfreie sprachen
automaten
berechenbarkeit
entscheidbarkeit
informatik
bachelor
zusammenfassung
reduktion
komplexität
turing
tum

Folgen

AdelinaB Mitglied seit 5 Jahren 50 dokumente verkauft

10,46 €

In den Einkaufswagen

Speichern

100% Zufriedenheitsgarantie
Sofort verfügbar nach Zahlung
Sowohl online als auch als PDF
Du bist an nichts gebunden

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

Alle Vorteile der Zusammenfassungen von Stuvia auf einen Blick:

Garantiert gute Qualität durch Reviews

Stuvia Verkäufer haben mehr als 700.000 Zusammenfassungen beurteilt. Deshalb weißt du dass du das beste Dokument kaufst.

Schnell und einfach kaufen

Man bezahlt schnell und einfach mit iDeal, Kreditkarte oder Stuvia-Kredit für die Zusammenfassungen. Man braucht keine Mitgliedschaft.

Konzentration auf den Kern der Sache

Deine Mitstudenten schreiben die Zusammenfassungen. Deshalb enthalten die Zusammenfassungen immer aktuelle, zuverlässige und up-to-date Informationen. Damit kommst du schnell zum Kern der Sache.

Häufig gestellte Fragen

Was bekomme ich, wenn ich dieses Dokument kaufe?

Du erhältst eine PDF-Datei, die sofort nach dem Kauf verfügbar ist. Das gekaufte Dokument ist jederzeit, überall und unbegrenzt über dein Profil zugänglich.

Zufriedenheitsgarantie: Wie funktioniert das?

Unsere Zufriedenheitsgarantie sorgt dafür, dass du immer eine Lernunterlage findest, die zu dir passt. Du füllst ein Formular aus und unser Kundendienstteam kümmert sich um den Rest.

Wem kaufe ich diese Zusammenfassung ab?

Stuvia ist ein Marktplatz, du kaufst dieses Dokument also nicht von uns, sondern vom Verkäufer AdelinaB. Stuvia erleichtert die Zahlung an den Verkäufer.

Werde ich an ein Abonnement gebunden sein?

Nein, du kaufst diese Zusammenfassung nur für 10,46 €. Du bist nach deinem Kauf an nichts gebunden.

Kann man Stuvia trauen?

4.6 Sterne auf Google & Trustpilot (+1000 reviews)

45.681 Zusammenfassungen wurden in den letzten 30 Tagen verkauft

Gegründet 2010, seit 15 Jahren die erste Adresse für Zusammenfassungen

Starte mit dem Verkauf

Zusammenfassung

Einführung in die Theoretische Informatik - Zusammenfassung

Dokument Information

Themen

Schule, Studium & Fach

Verkäufer

Deine Reviews

Inhaltsvorschau