Sprachverarbeitung in der Medizin - 7.UE

Deterministische endliche Automaten

1. Der Automat hat zwei Zustände A und B. A ist Start-, B Endzustand. Das Alphabet besteht aus den Zeichen a, b und c. Die Übergangsfunktion ist wie folgt gegeben:
   von A aus kann mit a sowohl A als auch B erreicht werden, b führt von A zu A, c führt von A zu B.
   Von B aus führt a zu B, b führt sowohl zu B als auch zu A, c führt zu B.

2. Der Automat hat drei Zustände 0, 1, 2 und 3, 0 ist Startzustand, 2 Endzustand. Das Alphabet besteht aus a, b und c.
   Von 0 aus führt a zu 1.
   Von 0 aus führt a zu 2. (Indeterminismus!)
   Von 0 aus führt b zu 3.
   Von 1 aus führt b zu 2.
   Von 1 aus führt b zu 3. (Indeterminismus!)
   Von 1 aus führt c zu 1.
   Von 2 aus führt b zu 1.
   Von 2 aus führt c zu 3.
   Von 3 aus führt a zu 1.
   Von 3 aus führt b zu 2.
   

Typ-3-Sprachen

• In der Vorlesung wurde gezeigt, dass die englische Sprache nicht vom Typ 3 ist. Die Beweisskizze ging so: Der Durchschnitt zweier Typ-3-Sprachen ist wieder vom Typ 3. Seien A Nominalphrasen, B transitive Verben. A*B*died ist regulär. Wenn Englisch regulär ist, muss auch der Durchschnitt von Englisch mit A*B*died regulär sein, dieser Durchschnitt ist aber die Sprache AⁿB^n-1died, die nicht regulär ist, wodurch sich ergibt, dass auch Englisch nicht regulär sein kann.

  Warum ist aber die Sprache AⁿB^n-1died nicht regulär? Beweisen Sie das mit Hilfe des Pumping Lemma!