|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc050313,
author = {Sempere, Jos\'{e} M.},
title = {On a Class of Regular-like Expressions for Linear Languages},
journal = jalc,
year = 2000,
volume = 5,
number = 3,
pages = {343--354},
keywords = {formal languages, linear languages, regular expressions,
representation theorems},
abstract = {Regular expressions define regular languages, so, there
exist algorithms that can solve some important problems
concerning regular languages such as finite automata
synthesis or analysis by using regular expressions. In this
work, we propose an extension of regular expressions to
characterize a larger language class, linear languages.
Linear languages form a class which is properly included in
the context-free language class and which also properly
includes the regular language class. From the definition
proposed in this paper, an algorithm which obtains linear
grammars from linear expressions (and vice versa) is
formulated in a way similar to the one for regular
expressions. We also review some problems concerning linear
grammars such as the equivalence and the structural
equivalence problem.}
}