Sprachverarbeitung in der Medizin - 9.UE

Finite State Transducers (FSTs), Kaskadierung und Komposition

1. Der erste FST hat 3 Zustände, 0 (Startzustand, kein Endzustand), 1 (kein Endzustand), und 2 (Endzustand), er soll die Kleinbuchstaben a und b in die entprechenden Großbuchstaben A und B umwandeln. Beachten Sie, dass aber nicht jede beliebige Kombination von a und b akzeptiert wird, sondern nur wie angegeben:
   Von 0 aus führt a:A zu 1, b:B führt zu 2
   Von 1 aus führt a:A zu 1, b:B führt zu 2
   Von 2 aus führt b:B zu 2.
   Zeichnen Sie den FST.

   Welche Sprache akzeptiert dieser FST?

2. Der zweite FST hat ebenfalls 3 Zustände, 0 (Startzustand, kein Endzustand), 1 (kein Endzustand), und 2 (Endzustand), er soll die Großbuchstaben A und B in die Ziffern 1 und 2 umwandeln. Beachten Sie, dass wieder nicht jede beliebige Kombination von A und B akzeptiert wird, sondern nur wie angegeben:
   Von 0 aus führt A:1 zu 1, B:2 führt zu 2
   Von 1 aus führt A:1 zu 2, B:2 führt zu 1
   Von 2 aus führt A:1 zu 1, B:2 führt zu 2.
   Zeichnen Sie den FST.

   Welche Sprache akzeptiert dieser FST?

3. Entwerfen Sie nun einen einzigen FST durch Komposition der beiden FSTs, der unter den durch die beiden FSTs gegebenen Beschränkungen Kleinbuchstaben in Ziffern umwandelt. (Zeichnen Sie den FST oder geben Sie seine Übergangsfunktion durch eine Tabelle an).