Tut 1

Question 1

Was ist eine formale Grammatik?

Answer 1

• 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆)
• Symbolkette w, die ausschließlich aus Terminal- symbolen besteht, heißt Wort
• Eine Grammatik generiert Wörter einer Sprache
• Eine Grammatik vom Typ 𝑖 kann eine Sprache vom Typ 𝑗 mit 𝑗 ≥ 𝑖 erzeugen

Question 2

Was ist ein Endlicher Automat (EA)?

Answer 2

• 𝐴 = (𝐸, 𝑆, 𝛿, 𝑠0, 𝐹)
• Ein (endlicher) Automat erkennt Wörter einer Sprache
• Was ist endlich an einem EA? Arbeitsband
• End- und Nicht-Endzustände zu invertieren, um den komplementären Automaten
• „Senken-Zustand“
• Die Menge der Sprachen, die von endlichen Automaten erkannt werden können, ist genau dieselbe, wie die der Sprachen, die durch rechtslineare Grammatiken erzeugt werden können

Question 3

PPL

Answer 3

• Fehlen dieser Eigenschaft = Beweis, dass die Sprache nich von einem EA erkannt werden kann.
• Nur wenn es für eine Sprache nicht gilt, gibt es ganz sicher keinen EA für diese Sprache.

Question 4

PPL - Vorgehen

Answer 4

Question 5

EA-Minimierung

Answer 5

• Zwei Zustände sind äquivalent, wenn man von beiden ausgehend über dasselbe Wort immer im selben „Zustandstyp“ (Endzustand bzw. Nicht- Endzustand) landet.
• wobei die Zahl 0, 1, … für die minimale Wortlänge steht, für die die Zustände sich unterscheiden
• alle nicht als „nicht äquivalent“ (Xi) gekennzeichneten Zustände äquivalent.

1. Zustandsübergangsdiagramm

Question 6

Was ist ein „minimaler“ EA für eine Sprache?

Answer 6

Ein Automat, der

• die Sprache erkennt und
• höchstens so viele Zustände hat wie jeder andere Automat, der die Sprache erkennt.