Deque Automata for All Classes of Formal Languages
Deque Automata for all classes of Formal languages
B. Asha latha1
Department of computers
SRKIT Engineering
Vijayawada Andhra Pradesh (India)
T.Vishnupriya2
Department of Electronics
SRKIT Vijayawada, Andhra Pradesh (India)
N.Himabindu3
Department of computers
KBN College of Vijayawada, Andhra Pradesh (India)
Abstract: The purpose of computation involves solving problems by communicating them to a computational model by means of a suitable language .A number of languages have been developed for this purpose. To recognize these languages some computational models has been developed and they are finite state machine, push down automata, queue automata and turing machines. But these machines are restricted to only one specific formal languages like regular, context free ,etc. In this paper we proposed a machine called a Dequeue automaton that is capable of recognizing different classes of automata. We also shown that the simulation results from the Deque automata.
Keywords: Formal languages, Finite automata, PDA ,TM.
I. Introduction
A finite automaton was the first abstract model as well as the mathematical model of digital computers. It is very powerful model of computation. It can recognize and accept regular languages. But finite automata have limited memory(states) which prevents them accepting Context free languages .Since memory is a limitation of finite automata ,a memory element is added as a stack, in order to made finite automata a powerful machine and to accept Context free languages. That new type of computational model is known as a Push down automata.PDA is similar to finite automata except that it has an extra memory unit stack. Stack is defined as a data structure where insertion and deletion of any element is possible only at one end called top of the stack.[1].
The automata with queue memory was constructed in a similar way as the PDA, however the new type of memory of QA is queue. The definition of queue automata is similar to that of
B. Asha latha1
Department of computers
SRKIT Engineering
Vijayawada Andhra Pradesh (India)
T.Vishnupriya2
Department of Electronics
SRKIT Vijayawada, Andhra Pradesh (India)
N.Himabindu3
Department of computers
KBN College of Vijayawada, Andhra Pradesh (India)
Abstract: The purpose of computation involves solving problems by communicating them to a computational model by means of a suitable language .A number of languages have been developed for this purpose. To recognize these languages some computational models has been developed and they are finite state machine, push down automata, queue automata and turing machines. But these machines are restricted to only one specific formal languages like regular, context free ,etc. In this paper we proposed a machine called a Dequeue automaton that is capable of recognizing different classes of automata. We also shown that the simulation results from the Deque automata.
Keywords: Formal languages, Finite automata, PDA ,TM.
I. Introduction
A finite automaton was the first abstract model as well as the mathematical model of digital computers. It is very powerful model of computation. It can recognize and accept regular languages. But finite automata have limited memory(states) which prevents them accepting Context free languages .Since memory is a limitation of finite automata ,a memory element is added as a stack, in order to made finite automata a powerful machine and to accept Context free languages. That new type of computational model is known as a Push down automata.PDA is similar to finite automata except that it has an extra memory unit stack. Stack is defined as a data structure where insertion and deletion of any element is possible only at one end called top of the stack.[1].
The automata with queue memory was constructed in a similar way as the PDA, however the new type of memory of QA is queue. The definition of queue automata is similar to that of
References: [1]. Introduction to automata theory languages and computation by ULLAMAN [2]. Bhattacharjee, A.,and Debnath, B.K.,”Queue Automata “.