100% satisfaction guarantee Immediately available after payment Both online and in PDF No strings attached
logo-home
Einführung in die Theoretische Informatik - Zusammenfassung $11.05
Add to cart

Summary

Einführung in die Theoretische Informatik - Zusammenfassung

 2 views  0 purchase
  • Course
  • Institution

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...

[Show more]

Preview 5 out of 16  pages

  • August 24, 2024
  • 16
  • 2024/2025
  • Summary
avatar-seller
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

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

Guaranteed quality through customer reviews

Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.

Quick and easy check-out

Quick and easy check-out

You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.

Focus on what matters

Focus on what matters

Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!

Frequently asked questions

What do I get when I buy this document?

You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.

Satisfaction guarantee: how does it work?

Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.

Who am I buying these notes from?

Stuvia is a marketplace, so you are not buying this document from us, but from seller AdelinaB. Stuvia facilitates payment to the seller.

Will I be stuck with a subscription?

No, you only buy these notes for $11.05. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

51036 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 15 years now

Start selling
$11.05
  • (0)
Add to cart
Added