Scanning Regular Languages by Dual Finite Automata

Pei Chi Wu; Feng-Jian Wang; Kai Ru Young

doi:10.1145/131080.131081

Scanning Regular Languages by Dual Finite Automata

Pei Chi Wu, Feng-Jian Wang, Kai Ru Young

Research output: Contribution to journal › Article › peer-review

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 1992: 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.

Original language	English
Pages (from-to)	12-16
Number of pages	5
Journal	ACM SIGPLAN Notices
Volume	27
Issue number	4
DOIs	https://doi.org/10.1145/131080.131081
State	Published - 4 Jan 1992

Access to Document

10.1145/131080.131081

Cite this

@article{1c03aed20242412fb8cb275503f75c05,

title = "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 1992: 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.",

author = "Wu, {Pei Chi} and Feng-Jian Wang and Young, {Kai Ru}",

year = "1992",

month = jan,

day = "4",

doi = "10.1145/131080.131081",

language = "English",

volume = "27",

pages = "12--16",

journal = "ACM SIGPLAN Notices",

issn = "0362-1340",

publisher = "Association for Computing Machinery (ACM)",

number = "4",

}

TY - JOUR

T1 - Scanning Regular Languages by Dual Finite Automata

AU - Wu, Pei Chi

AU - Wang, Feng-Jian

AU - Young, Kai Ru

PY - 1992/1/4

Y1 - 1992/1/4

N2 - 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 1992: 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.

AB - 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 1992: 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.

UR - http://www.scopus.com/inward/record.url?scp=84976702064&partnerID=8YFLogxK

U2 - 10.1145/131080.131081

DO - 10.1145/131080.131081

M3 - Article

AN - SCOPUS:84976702064

SN - 0362-1340

VL - 27

SP - 12

EP - 16

JO - ACM SIGPLAN Notices

JF - ACM SIGPLAN Notices

IS - 4

ER -

Scanning Regular Languages by Dual Finite Automata

Abstract

Access to Document

Other files and links

Fingerprint

Cite this