Aufbau eines endlichen Transducers

  • Ich weiß, dass es möglich ist, einen Finite-State-Transducer zum Konvertieren von Zahlen von Basis 2 zu Basis 4 oder 8 oder einer anderen Potenz von 2 zu erstellen (das Übersetzen von Basis N in Basis N ^ M ist einfach). Ich habe jedoch noch nie eine FST gesehen, die Zahlen von Basis 1 in Basis 2 oder umgekehrt konvertieren kann. Kann eine FST dies auch tun? Wenn ja, können Sie bitte ein paar Hinweise zum Aufbau einer solchen FST geben?

    17 July 2012
    Kaveh
1 answer
  • Meines Erachtens gibt es solche Transducer nicht.

    Eine Konvertierung von Base 2 nach Base 1 ist seit der regulären Sprache $ \ {10 nicht möglich ^ n \ | \ n \ in \ mathbb {N} \} $ würde $ \ {1 ^ {2 ^ n} \ | \ n \ in \ mathbb {N} \} $ werden, was unregelmäßig ist. Allerdings werden reguläre Sprachen unter der Übersetzung durch den Finite-State-Transducer geschlossen.

    Andererseits konnte ich keinen so einfachen Beweis für den umgekehrten Fall finden bedeutet nicht, dass ein solcher Beweis nicht existiert). Aber ich neige dazu zu glauben, dass dies auch nicht möglich ist. Der Grund ist, dass der Wandler einige Übergänge haben würde, die $ \ varepsilon $ schreiben, und einige Übergänge, die Nicht - $ \ varepsilon - Wörter schreiben. Da jedoch die Länge des Bildes von $ w, | w | = n $ ist $ O (\ log n) $, die Übergänge, die Nicht - $ \ varepsilon - $ - Wörter schreiben, werden signifikant weniger (jedoch nicht konstante Anzahl von Malen) als die $ \ varepsilon $ - Übergänge an allen Eingängen verwendet. < / em> Für einen Finite-State-Transducer wird jedoch ein Übergang entweder konstant verwendet oder es gibt eine Eingabe, so dass die Anzahl der Verwendungen dieses Übergangs mindestens $ \ frac {1} {m} n $ beträgt , wobei $ m $ die Anzahl der Übergänge und $ n $ die Länge der Eingabe ist (dies ist nicht so schwer zu beweisen). Darüber hinaus existiert eine solche Eingabe natürlich für beliebig große $ n $. Daher bekommen wir einen Widerspruch.

    15 July 2012
    042