On the recognition of context-free languages using accepting hybrid networks of evolutionary processors

Abstract

In this paper we approach the problem of constructing an accepting device for the class of context-free languages, based on a newly defined computational model: Accepting Hybrid Network of Evolutionary Processors (AHNEPs). Although it is known that AHNEPs are Turing complete, and, consequently, for every context-free language, seen as a recursively enumerable language, we can construct an AHNEP that simulates the Turing machine accepting it, we choose a direct approach: the AHNEPs we design simulate the computation done by a non-deterministic push-down automata accepting the language. This approach leads to a more economic AHNEP since the number of processors we use depends linearly on the number of states and the number of working symbols of the automaton, while for the network obtained in the general case of recursively enumerable languages, the number of processors is linear in the number of states, but quadratic in the number of working symbols of a Turing machine accepting the given language. Finally, we particularize the AHNEP architecture we proposed in order to recognize regular languages. We obtain an upper bound for the number of processors needed close to that known for generating hybrid networks of evolutionary processors.

Keywords:

• Context-free language
• Evolutionary processor
• Finite automaton
• Push-down automaton
• Regular language

Acknowledgements

I would like to thank the anonymous referees for their comments and suggestions, which improved the presentation of this paper. This work is partially supported by Research Grant no. ET75/2005 of the Romanian National Authority for Scientific Research.

Additional information

Notes on contributors

Florin Manea

Email: [email protected]