

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
FORMAL DEFINITION OF A REGULAR EXPRESSION
Say that R is a regular expression if R is
In items 1 and 2, the regular expressions a and ε represent the languages {a} and {ε}, respectively. In item 3, the regular expression ∅ represents the empty language. In items 4, 5, and 6, the expressions represent the languages obtained by taking the union or concatenation of the languages R_{1} and R_{2}, or the star of the language R_{1}, respectively.
Don't confuse the regular expressions ε and ∅. The expression ε represents the language containing a single string, namely, the empty string, whereas ∅ represents the language that doesn't contain any strings.
Seemingly, we are in danger of defining the notion of regular expression in terms of itself. If true, we would have a circular definition, which would be invalid. However, R_{1} and R_{2} always are smaller than R. Thus we actually are defning regular expressions in terms of smaller regular expressions and thereby avoiding circularity. A definition of this type is called an inductive definition.
Parentheses in an expression may be omitted. If they are, evaluation is done in the precedence order: star, then concatenation, then union.
Note! While not enforceable by an interface, Regular Expressions should be immutable objects
Method Summary  
RegularExpression 
complement()
Complements the language that this regular expression accepts. 
RegularExpression 
concatenate(RegularExpression re)
Let N_{1} = (Q_{1}, Σ, δ_{1}, q_{1}, F_{1}) recognize A_{1}, and N_{2}, Σ, δ_{2}, q_{2}, F_{2}) recognize A_{2}. 
boolean 
equals(RegularExpression regexp)

boolean 
equivalent(RegularExpression regexp)

int 
hashCode()

RegularExpression 
star()
Let N_{1} = (Q_{1}, Σ, δ_{1}, q_{1}, F_{1}) recognize A_{1}. 
NondeterministicFiniteAutomata 
toNondeterministicFiniteAutomata()
Returns an NFA that accepts the same regular language that this regular expression accepts. 
java.lang.String 
toString()

RegularExpression 
union(RegularExpression re)
Let N_{1} = (Q_{1}, Σ, δ_{1}, q_{1}, F_{1}) recognize A_{1}, and N_{2} = (Q_{2}, Σ, δ_{2}, q_{2}, F_{2}) recognize A_{2}. 
Methods inherited from interface org.metasyntactic.math.automata.FiniteAutomata 
accept 
Method Detail 
public RegularExpression concatenate(RegularExpression re)
Construct N = (Q, Σ, δ, q_{1}, F_{2}) to recognize A_{1}⋅A_{2}.
public RegularExpression union(RegularExpression re)
Construct N = (Q, Σ, δ, q_{0}, F) to recognize A_{1}∪A_{2}.
public RegularExpression star()
public RegularExpression complement()
public NondeterministicFiniteAutomata toNondeterministicFiniteAutomata()
public int hashCode()
hashCode
in class java.lang.Object
public java.lang.String toString()
toString
in class java.lang.Object
public boolean equals(RegularExpression regexp)
public boolean equivalent(RegularExpression regexp)


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 