An Infinite Proper Subset of Regular Languages as a State Change Based Coupling of Finite Automata

ÇEVİK A., Kilic H.

World Congress on Engineering and Computer Science, San-Francisco, Costa Rica, 21 - 23 October 2015, pp.55-58 identifier

  • Publication Type: Conference Paper / Full Text
  • City: San-Francisco
  • Country: Costa Rica
  • Page Numbers: pp.55-58
  • Middle East Technical University Affiliated: Yes


We introduce an infinite proper subset of regular languages (RL), so called the state change couple of finite automata (FA). The execution time state change behavior of FA is shown to be modelled as state automata (SA). For our purpose, we define a unary operator whose domain is FA and range is SA. The new language class obtained by applying the operator on FA is called state change languages (SCL). We show that SCL is closed under union, but not under complementation, homomorphism and inverse homomorphism. We also investigate the properties of SA with empty string transitions. The work given here can be considered as a basis for analyzing the language class properties of the runtime attributes of basic computational models.