TY - GEN
T1 - Deterministic regular languages
AU - Brüggemann-Klein, Anne
AU - Wood, Derick
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1992.
PY - 1992
Y1 - 1992
N2 - The ISO standard for Standard Generalized Markup Language (SGML) provides a syntactic meta-language for the definition of textual markup systems. In the standard the right hand sides of productions are called content models and they are based on regular expressions. The allowable regular expressions are those that are “unambiguous” as defined by the standard. Unfortunately, the standard's use of the term “unambiguous” does not correspond to the two well known notions, since not all regular languages are denoted by “unambiguous” expressions. Furthermore, the standard's definition of “unambiguous” is somewhat vague. Therefore, we provide a precise definition of “unambiguous expressions” and rename them deterministic regular expressions to avoid any confusion. A regular expression E is deterministic if the canonical ε-free finite automaton ME recognizing L(E) is deterministic. A regular language is deterministic if there is a deterministic expression that denotes it. We give a Kleene-like theorem for deterministic regular languages and we characterize them in terms of the structural properties of the minimal deterministic automata recognizing them. The latter result enables us to decide if a given regular expression denotes a deterministic regular language and, if so, to construct an equivalent deterministic expression.
AB - The ISO standard for Standard Generalized Markup Language (SGML) provides a syntactic meta-language for the definition of textual markup systems. In the standard the right hand sides of productions are called content models and they are based on regular expressions. The allowable regular expressions are those that are “unambiguous” as defined by the standard. Unfortunately, the standard's use of the term “unambiguous” does not correspond to the two well known notions, since not all regular languages are denoted by “unambiguous” expressions. Furthermore, the standard's definition of “unambiguous” is somewhat vague. Therefore, we provide a precise definition of “unambiguous expressions” and rename them deterministic regular expressions to avoid any confusion. A regular expression E is deterministic if the canonical ε-free finite automaton ME recognizing L(E) is deterministic. A regular language is deterministic if there is a deterministic expression that denotes it. We give a Kleene-like theorem for deterministic regular languages and we characterize them in terms of the structural properties of the minimal deterministic automata recognizing them. The latter result enables us to decide if a given regular expression denotes a deterministic regular language and, if so, to construct an equivalent deterministic expression.
UR - http://www.scopus.com/inward/record.url?scp=85029666979&partnerID=8YFLogxK
U2 - 10.1007/3-540-55210-3_182
DO - 10.1007/3-540-55210-3_182
M3 - Conference contribution
AN - SCOPUS:85029666979
SN - 9783540552109
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 173
EP - 184
BT - STACS 1992 - 9th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
A2 - Finkel, Alain
A2 - Jantzen, Matthias
PB - Springer Verlag
T2 - 9th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1992
Y2 - 13 February 1992 through 15 February 1992
ER -