Re: Between Regular and Context Free Languages

Welf Loewe <loewe@ipd.info.uni-karlsruhe.de> writes:


>Are there classes of languages R* with


>Regular Languages \subset R* \subset context free languages


>such that


>L, L' \in R* ==> L \subset L' is decidable?
>L, L' \in R* ==> L \subset L' is efficiently computable?


The question is undecidable for the most commonly quoted language
class that is strictly between regular and CFLs: the deterministic
context-free languages. Deterministic CFLs are those that can be
recognized by deterministic one-way pushdown automata (DPDA). So your
class can not contain the DCFLs.


You can, of course, add a finite number of non-regular languages to
the class of regular languages and get a class where subset is
decidable. This is, however, not very interesting; you would really
like R*\R to be infinite.


I can construct such a class. I'm not sure it is very interesting,
though. The class is those languages that can be recognized by
deterministic finite automata with the following extension: Each
transition is labelled by 1 or 2 in addition to the alphabet symbol. A
transition labelled 1 is valid in the first half of the input string
and a transition labelled 2 is valid in the second half of the input
string. A state can have two transitions on the same input symbol if
they are labelled by different numbers. This class is obviosuly closed
under intersection, union and complement, and it is decidable whether
the language is empty. You basically use the same methods that are
used for deterministic automata with trivial modifications. Hence,
subset is decidable.


The class is also a subset of the CFLs, as such an automaton can be
simulated by a nondeterministic PDA: You start with a stack just
containing the symbol $. You can take a transition labelled 1 if there
is a 1 or $ on the stack top. If you do so, push a 1 on the stack. You
can take a transition labelled 2 if there is a 1 or 2 on the stack
top. If there is a 1, pop it and push a 2. If there is a 2, pop that
and fail if the stack symbol under that is a $. Otherwise, pop the 1
(as it must be) and push a 2. If the stack top is $ at then end of the
input, you accept.


Hence, if you have a 1 on the stack top, you can nondeterministically
take either a 1-labelled or a 2-labelled transition. But if you are
not at the halfway point when you chose the 2-labelled transition, you
will fail later on.


The class also contains non-regular languages. It can e.g. recognize
the language {a^n b^n | n \in N}. More precisely, it contains all
languages of the form {vw | v \in L1, w \in L2, |v|=|w|} where L1 and
L2 are regular languages. To make it a strict superset of the regular
languages, odd-length strings must be handled as well. This is a
trivial modification.


Torben Mogensen (torbenm@diku.dk)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.