Re: classification of a language -- not ({ww})

torbenm@diku.dk (Torben AEgidius Mogensen)
29 Oct 1999 02:30:11 -0400

          From comp.compilers
Related articles
classification of a language -- not ({ww}) linlist@fudan.edu (Linlist Leo) (1999-10-27)
Re: classification of a language -- not ({ww}) raugfer@uol.com.br (Rodrigo Augusto B. Ferreira) (1999-10-28)
Re: classification of a language -- not ({ww}) torbenm@diku.dk (1999-10-29)
| List of all articles for this month |
From: torbenm@diku.dk (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 <linlist@fudan.edu> 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 (torbenm@diku.dk)

Post a followup to this message

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