Re: how to prove: let L be any subset of 0*. is L regular?

From: Barb Knox <see@xxxxxxxxx>
Date: Sat, 14 Oct 2006 16:04:38 +1300

In article <1160770360.786007.248970@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
yanlu06@xxxxxxxxx wrote:

let L be any subset of 0*. is L regular?
How to prove?

Here's a nonconstructive proof that L is not always regular:

The set of regular languages on a finite alphabet is countably infinite.
The set of subsets of 0* is uncountable.
Therefore almost all such subsets are not regular.
.

Follow-Ups:
- Re: how to prove: let L be any subset of 0*. is L regular?
  - From: kitty

References:
- how to prove: let L be any subset of 0*. is L regular?
  - From: yanlu06

Prev by Date: Re: Growth Rate of Level-k Goodstein Function
Next by Date: Re: K-colorable graphs
Previous by thread: Re: how to prove: let L be any subset of 0*. is L regular?
Next by thread: Re: how to prove: let L be any subset of 0*. is L regular?
Index(es):
- Date
- Thread

Relevant Pages

Re: searching for balanced expression
... In practice: XEmacs regular expressions can express regular languages, plus some context sensitive expressions that can be parsed with predetermined finite memory. ...
(comp.emacs.xemacs)
Re: x$y | #a(x) = #b(y)
... Louvino wrote: ... > Usually, I find but for this exercise, I don't understand. ... language is regular. ... lemma for regular languages will suffice for the proof. ...
(comp.theory)
Re: how to prove: let L be any subset of 0*. is L regular?
... Here's a nonconstructive proof that L is not always regular: ... The set of regular languages on a finite alphabet is countably infinite. ...
(comp.theory)