Re: classification of a language -- not ({ww}) (Torben AEgidius Mogensen)
29 Oct 1999 02:30:11 -0400

          From comp.compilers

Related articles
classification of a language -- not ({ww}) (Linlist Leo) (1999-10-27)
Re: classification of a language -- not ({ww}) (Rodrigo Augusto B. Ferreira) (1999-10-28)
Re: classification of a language -- not ({ww}) (1999-10-29)
| List of all articles for this month |

From: (Torben AEgidius Mogensen)
Newsgroups: comp.compilers,comp.theory
Date: 29 Oct 1999 02:30:11 -0400
Organization: Department of Computer Science, U of Copenhagen
Distribution: inet
References: 99-10-132
Keywords: parse, theory

Linlist Leo <> writes:

>BTW, is context sensitive language closed under 'complementation'?

Yes. The following language classes are closed under complementation:

  1) Regular languages.

  2) Deterministic context free languages (i.e. LR(k)).

  3) Context-sensitive languages.

  4) Recursive (i.e. decidable) languages.

The following are not:

  1) Finite languages.

  2) Context free languages.

  3) Recursively enumerable languages.

Torben Mogensen (

Post a followup to this message

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