Graduate Thesis Or Dissertation

 

The equivalence of regular expressions Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/0k225f758

Descriptions

Attribute NameValues
Creator
Abstract
  • The use of Regular Expressions to represent the conditions of operations of a finite automaton is becoming popular. A finite automaton can be represented by several regular expressions which are entirely different in out-looks and in structures. It is the primary purpose of this paper to develop several approaches to prove the equivalence of regular expressions, in a unified manner, pointing out the similarities and differences in the various treatments. The first technique of proving the equivalence is by converting each regular expression into a state graph representing an automaton, then by testing the isomorphism of the resulting automata will show whether the given regular expressions are equivalent. The second technique of proving the equivalence is by converting each regular expression into a graph and then one of the graphs is converted into another graph which is different in appearance, but still representing the same regular expression. This process goes on until the graphs representing two regular expressions become identical, thus the equivalence of the regular expressions is proved. Otherwise they are not equivalent. Axiomic approach is presented in the last chapter of this paper, so that there are formal systems for the algebraic transformation of regular expressions. Equivalence of regular expressions can be clearly checked out within these systems.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0 on a Canon DR-9050C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2014-01-09T15:19:38Z (GMT) No. of bitstreams: 1 YuTingKwong1973.pdf: 1332760 bytes, checksum: 0d3c150642873fb1a0569879524cc641 (MD5)
  • description.provenance : Submitted by Georgeann Booth (gbscannerosu@gmail.com) on 2014-01-09T01:26:25Z No. of bitstreams: 1 YuTingKwong1973.pdf: 1332760 bytes, checksum: 0d3c150642873fb1a0569879524cc641 (MD5)
  • description.provenance : Approved for entry into archive by Katy Davis(kdscannerosu@gmail.com) on 2014-01-23T17:40:37Z (GMT) No. of bitstreams: 1 YuTingKwong1973.pdf: 1332760 bytes, checksum: 0d3c150642873fb1a0569879524cc641 (MD5)
  • description.provenance : Made available in DSpace on 2014-01-23T17:40:37Z (GMT). No. of bitstreams: 1 YuTingKwong1973.pdf: 1332760 bytes, checksum: 0d3c150642873fb1a0569879524cc641 (MD5) Previous issue date: 1973-02-23

Relationships

Parents:

This work has no parents.

In Collection:

Items