Ezhilarasu P et al.

/ International Journal of Computer Science & Engineering Technology (IJCSET)

Applications of Finite Automata in Lexical

Analysis and as a Ticket Vending Machine
– A Review
Ezhilarasu P
Associate Professor
Department of Computer Science and Engineering
Hindusthan College of Engineering and Technology Coimbatore, India.
[email protected]

Krishnaraj N
Head of the Department
Department of Information Technology
Sree Sastha Institute of Engineering and Technology, Chennai, India
[email protected]
Abstract: In this paper, we explain the two applications of finite automata. First is about the first phase of
a compiler design called as lexical analysis. The lexical analysis used to identify the token with its type.
Second is about the designing of vending machine to issue the tickets for the simple applications.
Keywords: Finite Automata, Lexical Analysis, Vending Machine.
I. INTRODUCTION
Automata theory defined as the study of abstract machines and automata, as well as the computational
problems that can be solved using them [1]. The important abstract machines are 1. Finite Automata 2. Pushdown
Automata 3.Turing Machine. In this, finite automata are the simpler machine, which initially proposed to model
brain function of the human. The simplest example for finite automata is the switch with two states "on" and "off"
[1].
The Finite Automata is the combination of five tuples focusing on states and transition through input symbols.
In figure 1, the starting state is OFF, ending state is ON and collection is ON and OFF. It is having only one input
PUSH for making the transition from the state ON to OFF, then OFF to ON. The switch is one of the simplest
practical applications of finite automata.

Fig. 1. A Finite Automaton for the switch with on/off states.

The finite automata concepts also used in various fields. In the design of a compiler, it used in the lexical
analysis to produce tokens in the form of identifiers, keywords and constants from the input program. In pattern
recognition, it used to search keywords by using string-matching algorithms, Ex. UNIX tools like awk, Procmail,
and egrep. In network, finite automata concepts used in the communication protocol.
II. RELATED WORK
Zvi Kohavi and Niraj K. Jha [2009] described the advanced topics in finite-state machine design and testing.
They also gave the behavior, limitations and structure of logic devices, [2].Hopcroft, Motwani and Ullman [2001]
listed the applications of finite automata. Finite automata are the useful model for many software and hardware.
They used in software for digital circuits, finding text pattern in web pages and verifying systems (Example
Communication protocol). In compiler design, the initial phase is lexical analysis for generating tokens. Finite
automata also used in the lexical analysis, [3].Ezhilarasu et al. [2014] classified finite automata based on single

ISSN : 2229-3345 Vol. 6 No. 05 May 2015 267

 Ezhilarasu P et al. / International Journal of Computer Science & Engineering Technology (IJCSET)

loop, double loop and more than double loop into many categories. Many applications may use this classification
as a base, [4], [5], [6].
III. FINITE AUTOMATA APPLICATIONS
Finite Automata concepts used in many applications. In this paper, we discuss the two namely
1.Lexical Analysis
2.Ticket Vending Machine
A. LEXICAL ANALYSIS
In the compiler, the source code converted into target code in six phases. The first phase is lexical analysis. In
this phase, source code converted into tokens. Example, for tokens are keywords, identifiers and constants as they
have the meaning as a unit. The white spaces and comments not considered during conversion. They cannot form
any category of tokens. The lexical analyzer gets the input character by character. Then by using pattern-matching
technique, it identifies the symbol. Symbol table manager and error handler also associated with the six phases of
a compiler. The methods used to implement lexical analyzers can also be applied to other areas such as query
languages and information retrieval systems [7]

Fig. 2. Lexical Analysis for the input SUM=NUMBER1+NUMBER2;.

LEXEME Token category

SUM "Identifier"
= "Assignment operator."
NUMBER1 "Identifier"
+ "Addition operator."
NUMBER2 "Identifier"
; "End of statement."
Table . 1. Lexeme with token type for the figure 1.

A lexeme is the unit derived from the source program with each group is related to anyone symbolic category.
The given source code "SUM=NUMBER1+NUMBER2; " is having six lexeme, as given in the table 1.
The lexical analyzer read the input character by character until finding the lexeme. First character ‘S’ is
obtained. Then character ‘U’ followed by ‘M’ and ‘=’. The last character ‘=’ omitted. The first three characters
combined to form the lexeme “SUM”. Then the character ‘=’ and ‘N’ scanned by the lexical analyzer. The last
character ‘N’ omitted to form the lexeme “=”. Then the remaining lexemes “NUMBER1”, “+”,”NUMBER2”,”;”
identified by the lexical analyzer. The pattern matching technique is used to match the lexeme with the token
type.
B. TICKET VENDING MACHINE
A vending machine defined as a machine that dispenses items. It includes snacks, beverages, alcohol,
cigarettes, lottery tickets, cologne, consumer products, and even gold and gems to customers automatically. The
customer need to insert inserts currency or credit into the machine [8]. We see many vending machines in real
life. The finite automata concepts used to design many vending machines.
1) COIN WEIGHING MACHINE
The simplest example is weighing machine. If weighing machine need a two-rupee coin as an input, then the
process involved are
1. The customer stands on the bottom of the weighing machine.
2. Insert the two-rupee coin.

ISSN : 2229-3345 Vol. 6 No. 05 May 2015 268

 Ezhilarasu P et al. / International Journal of Computer Science & Engineering Technology (IJCSET)

3. The weighing machine checks the coin by using sensors.

4. If the input is valid, reach step 6.
5. Return the coin and the process ends.
6. A blank ticket will reach the printing machine.
7. The noted weight with the randomized sentence like “today you will meet special person" will be printed.
8. The printed ticket disbursed to the customer, and the process ends.

Fig.3.A Mathematical Model of coin weighing machine using finite automata.

The ticket machine represented as a mathematical model as shown in the figure 3. It has q0 as a starting state,
qf as a final state and q0, q1, qf as a collection of states. The number ‘2' is used to represent the two-rupee coin as an
input character. The transition function implemented between the available states through input characters.
Input Character
States
Σ-2 2
q0 q1 q1
q1 q0 qf
*qf - -

Table. 2. State Transition Table for the figure 3.

The process involved in the finite automata is given in the table 2. Σ-2 represents all the coins except the two
rupee coin.
2) THEATRE TICKET VENDING MACHINE
The above concept used to design more complex vending machine. Example: vending machine designed to
provide cinema theatre ticket. The Cinema Theatre is having two classes namely silver and gold. The rate for the
silver class is Rupees 150, and for gold category is Rupees 250.

Fig.4.A Mathematical Model of theatre vending machine using finite automata.

The finite automata for the above condition represented by five tuples.
1.Starting state: q0
2.Final State(s) : q4, q5, q11, q12

ISSN : 2229-3345 Vol. 6 No. 05 May 2015 269

 Ezhilarasu P et al. / International Journal of Computer Science & Engineering Technology (IJCSET)

3.Group of States: q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12
4.Transition: As given above in the figure 4
5.Input characters: S,G,50,100
Input Character
States
S G 50 100
q0 q1 q6 - -
q1 - - q2 q3
q2 - - q3 q4
q3 - - q4 q5
*q4 - - - -
*q5 - - - -
q6 - - q7 q8
q7 - - q8 q9
q8 - - q9 q10
q9 - - q10 q11
q10 - - q11 q12
*q11 - - - -
*q12 - - - -

Table.3. State Transition Table for the figure 4.

The vending machine could process only two types of notes 1.50 rupees note 2.100 rupees note. The vending
machine has two buttons namely 'S','G'. The S represents the silver class, and G represents the gold category. The
customer should choose any one of the given buttons. Here we have four final states namely q4, q5, q11, q12. The
states q4, q5, used to print the ticket for the silver class as given in the table 3. If the state is q4, then the ticket
card printed for silver class. If the state is q5, then the ticket will be printed for silver class with gift voucher
worth rupees 50. If the state is q11, then the ticket card printed for the gold class. If the state is q12, then the ticket
will be printed for the golden class with gift voucher worth rupees 50. The gift voucher used to buy snacks in the
cinema theatre.
IV. CONCLUSION
This paper is useful for the students, those who are going to study the subject theory of computation. Students
will be able to implement the mathematical model for other simple applications. In Computer Science and
Engineering there are many subjects, each is having relation with others in some way. The theory of computation
is the base for studying the subject principles of compiler design.
V. REFERENCE
[1] http://en.wikipedia.org/wiki/Automata_theory.
[2] J.E. Hopcraft, R. Motwani, and J.D. Ullman, "Introduction to Automata Theory, Languages and Computation", Addison-Wesley,
Second edition, 2001.
[3] Zvi Kohavi and Niraj K. Jha , “Switching and Finite Automata Theory”, Cambridge University Press, Third edition, 2009.
[4] P. Ezhilarasu, J. Prakash, N. Krishnaraj, D. Satheesh Kumar, K. Sudhakar, and B. Dhiyanesh, “A Novel Approach to Classify
Nondeterministic Finite Automata Based on Single Loop and its Position”, International Journal of Advanced Research Trends in
Engineering and Technology (IJARTET), Volume 1, Issue 4, 2014, pp. 7-10.
[5] P Ezhilarasu, J. Prakash, N. Krishnaraj, D. Satheesh Kumar, K. Sudhakar, and C. Parthasarathy, "A Novel Approach to Classify
Nondeterministic Finite Automata Based on Dual Loop and its Position", International Journal of Engineering Trends and Technology
(IJETT), Volume 18, Issue 3,2014.pp. 147-150.
[6] P. Ezhilarasu, J. Prakash, N. Krishnaraj, D. Satheesh Kumar, K. Sudhakar, and C. Parthasarathy, “A Novel Approach to Classify
Nondeterministic Finite Automata Based on More than Two Loops and its Position”, SSRG International Journal of Computer
Science and Engineering (SSRG-IJCSE), Volume 1, Issue 10, 2014, pp. 46-49.
[7] A.V.Aho, R.Sethi, J.D.Ullman, " Compilers Principles, Techniques, and Tools",Pearson Education, 2007.
[8] http://en.wikipedia.org/wiki/Vending_machine

ISSN : 2229-3345 Vol. 6 No. 05 May 2015 270