Monotonní deterministické RL-automaty nepotřebují pomocné symboly.

Abstrakt

Již dříve bylo ukázáno, že deterministickým pravě-monotonním jednocestným restartovacím automatům pomocné symboly nezvyšují jejich rozpoznávací sílu. Zde je dokázáno totéž pro dvoucestné pravo- monotonní, levo-monotonní a pravo-levě monotonní restartovací automaty. Navíc je ukázána ekvivalnce výše zmíněných levě monotonních automatů se sériovým spojením deterministických zásobníkových a konečných převodníků.

Klíčová slova

• Monotone
• deterministic
• RL-automata
• don&apos
• t
• auxiliary
• symbols