24
Views
0
CrossRef citations to date
0
Altmetric
Original Articles

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

Pages 273-285 | Received 16 Nov 2005, Accepted 21 Dec 2006, Published online: 17 May 2007
 

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.

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]

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.