Scanning regular languages by dual finite automata

ABSTRACT

A regular language is generally accepted by a single finite automaton. An approach of dual finite automata is presented here. An input string is scanned by two deterministic finite automata (DFA's): reading from the string's head and tail respectively. One of them accepts the regular language itself; the other accepts the language's reversal. Whether a string is accepted depends on the states of both automata, when their reading heads meet. Dual finite automata can be applied in compiler generation and parallel computing.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Michael K. Donegan , Stuart W. Kartzke, Lexical analysis and parsing techniques for a vector machine, ACM SIGPLAN Notices, v.10 n.3, p.138-145, March 1975
• 3: John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
• 4: Dilip Sarkar , Narsingh Deo, Estimating the Speedup in Parallel Parsing, IEEE Transactions on Software Engineering, v.16 n.7, p.677-683, July 1990 [doi>10.1109/32.56094 ]
• 5: Pei-Chi Wu , Feng-Jian Wang, An object-oriented specification for compiler, ACM SIGPLAN Notices, v.27 n.1, p.85-94, Jan. 1992 [doi>10.1145/130722.130733]
• 6: Pei-Chi Wu , Feng-Jian Wang, Applying classification and inheritance into compiling, ACM SIGPLAN OOPS Messenger, v.4 n.4, p.33-43, Oct. 1993 [doi>10.1145/165593.165603]
• 7: 7. Wu, P.-C. and Wang, F.-J., "Message Passings on a Parse Tree," submitted to IEEE Computer Society 1992 Int'l Conf. on Computer Languages.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

General Terms:
Languages, Theory, Verification