Token description and recognition are two important functions of a lexical analyser in compiler design. A token can be described using mathematical expression like notation called regular expression. The process of token recognition is carried out with the help of finite automata. A finite state automaton is a type of machine in which for each state and input symbol, a transition takes place. A finite automaton can be deterministic or non-deterministic depending on number of possible transitions for each state and input symbol. The design of automata for recognition of tokens is an important and challenging task. From the available transitions, a token recognizer can be designed using JFLAP tool which further help in token recognition. However, there is no standard algorithm or procedure for construction of transition table for token recognizer. Present paper proposes an algorithm for construction of a language recognizer using deterministic finite automata for all tokens having a given suffix. The algorithm is implemented and tested for various token strings and results are used and compared with JFLAP results.

Lexical Analysis, Token, Language Recognizer, Deterministic Finite Automata, Suffix

[1] Aho A. V., Ullman J. D., “Principles of Compiler Design”, Narosa Publishing House, 2002
[2] John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, “Automata Theory, Language, and Computation”, Delhi: Pearson, 2008.
[3] Aparna, Goyal G., “Application Review of Automata Theory” International Journal of Scientific Research in Computer Science, Engineering and Information Technology, Vol. 3, Issue 1, pp. 947-955, 2018.
[4] Parekh, R. G., Honavar, V. G., "Learning DFA from Simple Examples” Journal of Machine Learning, Vol. 44, Issue 1-2, pp. 9-35, 2001.
[5] Webber A. B., “Formal Language: A Practical Introduction”, Franklin, Beedle & Associates Inc., Wilsonville, pp. 35-43, 2008.
[6] Ullman, J. D. (1972), "Applications of language Theory to Compiler Design", Proceedings of the May 16-18, 1972, spring joint computer conference, pp. 235-242, 1972.
[7] BabuKaruppiah A., Rajaram S., “Deterministic Finite Automata for pattern matching in FPGA for intrusion detection” International Conference on Computer, Communication and Electrical Technology, pp. 167-170, 2011
[8] Ejendibia P., Baridam B. B., “String Searching with DFA-based Algorithm”, International Journal of Applied Information Systems, Vol. 9, No. 8, pp. 1-6, 2015
[9] Gribko E. “Applications of Deterministic Finite Automata” ECS 120 UC Davis, Spring 2013, pp. 1-9, 2013.
[10] Raj N., Dubey R., “Snakes and Stairs Game Design using Automata Theory”, International Journal of Computer Sciences and Engineering, Vol. 5, Issue 5, pp.58-62, 2017
[11] Shenoy V., Aparanji U., Sripradha K., Kumar V., “Generating DFA Construction Problems Automatically” International Journal of Computer Trends and Technology, Vol. 4, Issue 4, pp.32-37 ,2013
[12] Pant Y., “A Novel Approach to Minimize DFA State Machines Using Linked List”, International Journal of Scientific Research in Computer Science and Engineering, Vol. 6, Issue 4, pp. 41-45, 2018