Formale Sprachen II at Duale Hochschule Baden-Württemberg

Ein Alphabet ist eine endliche, nicht leere Menge von Buchstaben:

∑  = {c1, ... , cn}

∑ = {0,1} binäres Alphabet

∑ = {a, ..., z, A, ..., Z} lat. Alphabet

∑ = {0, ..., 127} ASCII-Alphabet

Ist ∑ ein Alphabet, so ist ein String eine Liste von Buchstaben aus ∑.

c1c2c3...cn
Leeres Wort: ε := " " -> immer in ∑*

∑* := Liste aller Wörter

w1,w2 in ∑* mit w1=[c1,...,cn] und w2=[b1,...,bn] 

-> w1• w2 = w1w2 = c1,...,cn,b1,...,bn

-> Verbinden

Ist ∑ ein Alphabet so ist eine exakt definierte Teilmenge von ∑* eine formale Sprache.

Dabei gibt es 2 Klassen:

1. reguläre Sprachen

2. kontextfreie Sprachen

L1 und L2 Teilmenge von ∑* dann ist das Produkt von L1 • L2 definiert als:

L1 • L2 := {w1•w2 |  w1 in L1 UND w2 in L2}

Beispiel:

L1:= {ab,bc} L2:= {ac,cb}

L1•L2= {abac,abcb,bcac,bccb}

∑ ist ein Alphabet und L ⊆ ∑* ist formale Sprache mit n ϵ |N :

I.A. n= 0

L^0 := {ε}

I.S. n->n+1

L^n+1 = L^n *L

Beispiel:

∑ = {a,b} und L = {ab}

L^0 = ε 

L^1 = L

L^2 = abab

L^3 = ababab

1. ∅ ϵ RegExp∑  [ wenn '∅' nicht in ∑ ] LEERE SPRACHE

2. ε ϵ RegExp∑  [ wenn 'ε' nicht in ∑ ] LEERES WORT! NICHT LEERE SPRACHE

3. c ϵ ∑  ->c ϵ RegExp∑

4. r1,r2 ϵ RegExp∑  -> r1• r2 ϵ RegExp∑ [ wenn '• ' nicht in ∑ ]

5. r1,r2 ϵ RegExp∑  -> r1+r2 ϵ RegExp∑ [ wenn '+' nicht in ∑ ] 

6. r ϵ RegExp∑  -> r* ϵ RegExp∑ [ wenn '*' nicht in ∑ ] 

7. r ϵ RegExp∑  -> (r) ϵ RegExp∑ [ wenn '(' und ')' nicht in ∑ ]

1. Der Postfix-Operator * hat die höchste Priorität

2. Die Präzedenz von • ist höher als +, niedriger als *

3. + hat die niedrigste Präzedenz

Also  a+b•c* => a+(b•(c*))

L(r1) = L(r2)

. -> alles außer neue Zeile

a | b -> a bevorzugt b

^ -> Start eines Strings bzw. in Python alles außer [^abc]

$ -> Ende eines Strings

a* -> beliebig viele a's !INKLUSIVE 0*a)

a+ -> beliebig viele a's

a? -> non greedy 

{ }

[ ] ranges

( )

\X -> x zeichen

RegExp wird zu:

NFA -> non deterministic finite automation

DFA -> deterministic finite automation

FSM = Finite State Machine (ENDLICHE Menge an Zuständen)

5-Tupel

<Q, ∑, δ, q0, A>

1. Q ist eine endliche Menge an Zuständen 

2. ∑ ist ein Alphabet

3. δ: Q x ∑ -> Q oder Omega

4. q0 in Q ist Startzustand

5. A ⊆ Q ist Menge der akzeptierenden Zustände