Konečný automat je rozpoznávací funkcí, která určí, zda-li zadaný vstup patří do daného regulárního jazyka (výstup: true, false). Občas je ale zapotřebí navíc získat určitý komplexní výstup, který není binární (např. překlad vstupního řetězce nebo výpočet na jeho základě). Proto je zapotřebí konečný automat obohatit na přechodových hranách o funkce, které se při průchodu automatem provedou. Tímto způsobem vznikne konečný překladový automat.
Příklad
Vytvořte konečný překladový automat přijímající řetězce reprezentující decimální (19875), hexadecimální (0x1FA570) a oktalová (01764) čísla, vracející jejich decimální hodnotu.
Popis
Začínáme v uzlu S (start), pokud nám přijde číslo 1-9, pak se jedná o desítkové číslo a přejdeme do stavu D, při přechodu provedeme akci, která nám dané číslo uloží do paměti (A1). V uzlu D zpracováváme přicházející číslo (A1), dokud nám přichází vstup. Uzel D je koncový.
Pokud nám ovšem v uzlu S přijde nula, tak nevíme, jestli se jedná o hexadecimální nebo oktalové číslo, to se dozvíme až podle dalšího vstupu. Každopádně 0 je korektní číslo, proto je uzel H/O koncový.
Když přijde za nulou nějaké číslo, tak je zřejmé, že se jedná o oktalové číslo, které budeme převádět akcí A2, pokud přijde x, tak se jedná o hexadecimální číslo, zpracovávané akcí A3. U hexadecimálního čísla musíme ještě projít právě přes uzel x, který není koncový, protože číslo 0x není v korektním formátu.
Kód
001.
/**
002.
* konecny prekladovy automat
003.
* @author Pavel Micka
004.
*/
005.
public
class
TranslationFiniteStateMachine {
006.
/**
007.
* index, na kterem se pri prekladu nachazime
008.
*/
009.
private
int
index =
0
;
010.
/**
011.
* prekladany retezec
012.
*/
013.
private
String s;
014.
/**
015.
* hodnota, kterou to vrati
016.
*/
017.
private
int
hodnota =
0
;
018.
019.
public
TranslationFiniteStateMachine(String s) {
020.
this
.s = s;
021.
}
022.
/**
023.
* prelozi vstup automatu ve tvaru
024.
* 124689 - decimalni cislo
025.
* 02345 - oktalove cislo
026.
* 0x56AF5 - hexadecimalni cislo
027.
* na decimalni cislo
028.
* @return decimalni reprezentace
029.
*/
030.
public
int
translate() {
031.
final
String ERROR =
"spatny vstup"
;
032.
final
String EMPTY =
"spatny vstup / retezec je prazdny"
;
033.
char
in = readNext();
034.
if
(in >=
'1'
&& in <=
'9'
) {
//cislice, nezacina nulou, pujde o dekadicke cislo
035.
do
{
036.
hodnota = hodnota *
10
+ (in -
48
);
//48 == znak 0 v ascii, akce A1
037.
}
while
((in = readNext()) !=
0
&& in -
48
>=
0
038.
&& in -
48
<=
9
);
//dokud nejsme na konci vstupu
039.
//nebo neprisel nesmysl
040.
if
(in ==
0
) {
041.
return
hodnota;
042.
}
else
{
043.
throw
new
IllegalArgumentException(ERROR +
" "
+ in);
044.
}
045.
}
else
if
(in ==
'0'
) {
//oct or hexa
046.
in = readNext();
047.
if
(in ==
'x'
) {
//hexa
048.
boolean
readed =
false
;
//jesli byl uz precten alespon jeden
049.
//znak samotneho cisla - 0x nebereme
050.
while
(((in = readNext()) !=
0
) && (in >=
'0'
&& in <=
'9'
)
051.
|| (in >=
'A'
&& in <=
'F'
)) {
052.
readed =
true
;
053.
if
(in >=
'0'
&& in <=
'9'
) {
//cislo
054.
hodnota = hodnota *
16
+ (in -
48
);
//48 == znak 0 v ascii, akce A3
055.
}
else
{
//cislo nad 9...cili A - F
056.
hodnota = hodnota *
16
+ (in -
65
+
10
);
057.
//65 == znak A v ascii, +10 protoze A == 10 v hexa
058.
}
059.
}
060.
//dokud nejsme na konci vstupu
061.
//nebo neprisla blbost
062.
if
(in ==
0
&& readed) {
063.
return
hodnota;
064.
}
else
{
065.
throw
new
IllegalArgumentException(ERROR +
" "
+ in);
066.
}
067.
}
else
if
(in >=
'0'
&& in <=
'7'
) {
//octa
068.
do
{
069.
hodnota = hodnota *
8
+ (in -
48
);
//48 == znak 0 v ascii, akce A2
070.
}
while
((in = readNext()) !=
0
&& in >=
'0'
&& in <=
'7'
);
071.
//dokud nejsme na konci vstupu
072.
//nebo neprisel nesmysl
073.
if
(in ==
0
) {
074.
return
hodnota;
075.
}
else
{
076.
throw
new
IllegalArgumentException(ERROR +
" "
+ in);
077.
}
078.
}
else
if
(in ==
0
){
//na vstupu byla jenom nula, ted uz tam nic neni
079.
return
0
;
080.
}
081.
}
else
if
(in ==
0
) {
082.
throw
new
IllegalArgumentException(EMPTY);
083.
}
084.
throw
new
IllegalArgumentException(ERROR +
" "
+ in);
085.
}
086.
087.
/**
088.
* vrati dalsi znak na vstupu
089.
* @return znak na vstupu nebo 0 v pripade konce retezce
090.
*/
091.
private
char
readNext() {
092.
if
(index >= s.length()) {
093.
return
0
;
094.
}
095.
char
ret = s.charAt(index);
096.
index++;
097.
return
ret;
098.
}
099.
}