home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / de / comp / gnu / 327 < prev    next >
Encoding:
Internet Message Format  |  1992-12-30  |  1.2 KB
  1. Path: sparky!uunet!math.fu-berlin.de!ira.uka.de!rz.uni-karlsruhe.de!ma2s2!haible
  2. From: haible@ma2s2.uucp (Bruno Haible)
  3. Newsgroups: de.comp.gnu
  4. Subject: Re: flex && regular expressions
  5. Date: 30 Dec 1992 20:28:57 GMT
  6. Organization: University of Karlsruhe, Germany
  7. Lines: 17
  8. Sender: <haible@ma2s2.mathematik.uni-karlsruhe.de>
  9. Message-ID: <1ht0q9INNfoi@nz12.rz.uni-karlsruhe.de>
  10. References: <1992Dec30.184056.12792@cs.tu-berlin.de>
  11. NNTP-Posting-Host: ma2s2.mathematik.uni-karlsruhe.de
  12. Summary: regulaere Ausdruecke bilden eine Boolesche Algebra
  13. Keywords: regular expressions, boolean algebra, finite automata
  14.  
  15. Thipor Kong fragt:
  16.  
  17. > Ist es moeglich, zwei regulaere Ausdruecke re1 und re2 so zu einem regulaeren
  18. > Ausdruck r3 zu kombinieren, dass r3 genau dann matcht, wenn re1 matcht und
  19. > re2 nicht?
  20.  
  21. Ja, die regulaeren Ausdruecke bilden eine "Boolesche Algebra".
  22. Der *konstruktive* Beweis, dass mit re2 auch (NOT re2) ein regulaerer
  23. Ausdruck ist, ist allerdings laenglich. Er benutzt wesentlich, dass man
  24. ueber einem endlichen Alphabet arbeitet.
  25.  
  26. Dass mit re1 und re2 auch (AND re1 re2) ein regulaerer Ausdruck ist, steht
  27. in jedem Buch ueber Automatentheorie.
  28.  
  29. Bruno Haible
  30. <haible@ma2s2.mathematik.uni-karlsruhe.de>
  31.  
  32.