Equivalent language models that closely simulate one another and their illustration in terms of L systems

Abstract

In this paper, we discuss equivalent formal language models that yield their words in a similar way and conceptualize this similarity. More specifically, if for two models, there is a substitution by which we change each string of every yield sequence in one model so that the sequence of strings resulting from this change represents a yield sequence in the other equivalent model, these two models closely simulate one another; otherwise, they do not. First, we formalize this concept of close simulation in equivalent formal language models in general. Then, we illustrate this concept in terms of EIL systems.

Keywords:

• Close simulation
• Equivalence of language models
• Formal languages
• L systems

Acknowledgements

The authors thank both referees for their comments and suggestions. This work was supported by the GAČR 201/07/0005 grant.

Additional information

Notes on contributors

Martin švec

Email: [email protected]

Tomáš Kopeček

Email: [email protected]