IMPLEMENTATION OF UNRESTRICTED GRAMMAR IN TO THE RECURSIVELY ENUMERABLE LANGUAGE USING TURING MACHINE

Abstract

This project presents the implementation of the unrestricted grammar in to recursively enumerable language for JFLAP platform. Automata play a major role in compiler design and parsing. The class of formal languages that work for the most complex problems belongs to the set of Recursively Enumerable Language (REL).RELs are accepted by the type of automata as Turing Machine. Turing Machines are the most powerful computational machines and are the theoretical basis for modern computers. Turing Machine works for all classes of languages including regular language, CFL as well as Recursive Enumerable Languages. Unrestricted grammars are much more powerful than restricted forms like the regular and context free grammars. In facts, unrestricted grammars corresponds to the largest family of languages so we can hope to recognize by mechanical means; that is unrestricted grammars generates exactly the family of recursively enumerable languages. Turing Machine is used to implementation of unrestricted grammar & RELs for JFLAP platform. JFLAP is most successful and widely used tool for visualizing and simulating all types of automata. The Turing Machines differ from all other automata as it can work with Recursively Enumerable Languages and Unrestricted Grammar. Any language generated by an unrestricted grammar is recursively enumerable. The language anbncn is a recursively enumerable language which cannot be implemented using a Finite Automata or a PDA but can done using a Turing Machine. This requires more storage than for Context Free Languages and hence the Turing Machine with the infinite tapes, extendable in both directions is used for this.