Re: separating context-free languages by regular languages
- From: markwh04@xxxxxxxxx
- Date: 20 Aug 2005 11:38:25 -0700
sasha wrote:
> Give two disjunct context-free languages L1, L2 so that there is no pair
> of disjunct regular languages (R1,R2) with Li subset Ri (i=1,2).
The Dyck language D(u;v), given by the grammar:
D(u;v) -> u D(u;v) v D(u;v)
D(u;v) -> empty word
and its complement D'(u;v) = (u|v)* - D(u;v), given by the (extended)
context-free grammar
D'(u;v) -> D(u;v) v (u|v)*
D'(u;v) -> (u|v)* u D(u;v)
> I would be glad for any references or ideas.
Find a non-regular context-free language whose complement is
context-free.
.
- Prev by Date: Re: Solving linear system of equalities AND disequalities
- Next by Date: A Bin Packing like problem
- Previous by thread: Re: separating context-free languages by regular languages
- Next by thread: Minimum Memory Requirements
- Index(es):
