טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentZeitlin Daniel
SubjectLook-Ahead Finite-Memory Automata
DepartmentDepartment of Computer Science
Supervisor Professor Michael Kaminski


Abstract

We introduce and study a new model of computation dealing with infinite alphabets. Our model is an extension of finite-memory automata (FMA) and is called look-ahead finite-memory automaton (LFMA). We show that LFMA languages possess all closure and decision properties of FMA languages and, in addition are closed under reversing.  Also we introduce a new notion of a regular expression and a regular grammar over an infinite alphabet and show their equivalence to LFMA.