25 Jan 1997 21:46:46 -0500

Related articles |
---|

Between Regular and Context Free Languages loewe@ipd.info.uni-karlsruhe.de (Welf Loewe) (1997-01-22) |

Re: Between Regular and Context Free Languages torbenm@diku.dk (1997-01-25) |

Re: Between Regular and Context Free Languages nixon@softlab.se (Leif Nixon) (1997-01-25) |

From: | torbenm@diku.dk (Torben AEgidius Mogensen) |

Newsgroups: | comp.compilers |

Date: | 25 Jan 1997 21:46:46 -0500 |

Organization: | Department of Computer Science, U of Copenhagen |

References: | 97-01-176 |

Keywords: | syntax, theory |

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)

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.