org.metasyntactic.math.automata
Class AbstractRegularExpression

java.lang.Object
  |
  +--org.metasyntactic.math.automata.AbstractRegularExpression
All Implemented Interfaces:
FiniteAutomata, RegularExpression, java.io.Serializable
Direct Known Subclasses:
Concatenation, Empty, Null, Star, Symbol, Union

public abstract class AbstractRegularExpression
extends java.lang.Object
implements RegularExpression

Class implementing base funcitonality for a RegularExpression. Extendors must only implement equals(Object), toString() and hashCode().

See Also:
Serialized Form

Nested Class Summary
protected static class AbstractRegularExpression.NFAState
          Convenience class used in the implementations of toNondeterministicFiniteAutomata()
 
Field Summary
protected  boolean complement
           
 
Constructor Summary
AbstractRegularExpression()
           
 
Method Summary
 boolean accept(java.util.Iterator i)
           
 RegularExpression complement()
          Complements the language that this regular expression accepts.
 RegularExpression concatenate(RegularExpression regexp)
          Let N1 = (Q1, Σ, δ1, q1, F1) recognize A1, and N2, Σ, δ2, q2, F2) recognize A2.
 boolean equals(java.lang.Object o)
           
abstract  boolean equals(RegularExpression o)
           
 boolean equivalent(RegularExpression r2)
           
protected static java.lang.String escapedRegexpChars(java.lang.String unsafe)
          When we output a regular expression as a string we have to take care as to how it is formatted.
protected  RegularExpression internalConcatenate(RegularExpression regexp)
           
protected  RegularExpression internalStar()
           
protected  RegularExpression internalUnion(RegularExpression regexp)
           
protected static java.lang.String parenthesizedRegexp(java.lang.String unsafe)
           
protected static java.lang.String parenthesizedRegexp(java.lang.String unsafe, boolean parenSingleChars)
           
protected static boolean properlyParenthesized(java.lang.String string)
           
 RegularExpression star()
          Let N1 = (Q1, Σ, δ1, q1, F1) recognize A1.
 RegularExpression union(RegularExpression regexp)
          Let N1 = (Q1, Σ, δ1, q1, F1) recognize A1, and N2 = (Q2, Σ, δ2, q2, F2) recognize A2.
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface org.metasyntactic.math.automata.RegularExpression
hashCode, toNondeterministicFiniteAutomata, toString
 

Field Detail

complement

protected boolean complement
Constructor Detail

AbstractRegularExpression

public AbstractRegularExpression()
Method Detail

internalConcatenate

protected RegularExpression internalConcatenate(RegularExpression regexp)

internalUnion

protected RegularExpression internalUnion(RegularExpression regexp)

internalStar

protected RegularExpression internalStar()

accept

public boolean accept(java.util.Iterator i)
Specified by:
accept in interface FiniteAutomata
Parameters:
i - A string over some alphabet Σ
Returns:
true if this machine accepts w

union

public RegularExpression union(RegularExpression regexp)
Description copied from interface: RegularExpression
Let N1 = (Q1, Σ, δ1, q1, F1) recognize A1, and N2 = (Q2, Σ, δ2, q2, F2) recognize A2.

Construct N = (Q, Σ, δ, q0, F) to recognize A1∪A2.

  1. Q = {q0}∪Q1∪Q2. The states of N are all the states of N1 and N2, with the addition of a new start state q0
  2. The state q0 is the start state of N.
  3. The accept states F=F1∪F2. The accept states of N are all the accept states of N1 and N2. That way N accepts if either N1 or N2 accepts.
  4. Define δ so that for any q ∈ Q and and a ∈ Σε,

Specified by:
union in interface RegularExpression
Returns:
a new RegularExpression equal to A1∪A2

concatenate

public RegularExpression concatenate(RegularExpression regexp)
Description copied from interface: RegularExpression
Let N1 = (Q1, Σ, δ1, q1, F1) recognize A1, and N2, Σ, δ2, q2, F2) recognize A2.

Construct N = (Q, Σ, δ, q1, F2) to recognize A1⋅A2.

  1. Q = Q1∪Q2. The states of N are all the states of N1 and N2.
  2. The state q1 is the same as the start state of N1.
  3. The accept states F2 are the same as the accept states of N2.
  4. Define δ so that for any q ∈ Q and any a ∈ Σε,

Specified by:
concatenate in interface RegularExpression
Returns:
a new RegularExpression equal to N1⋅N2

star

public RegularExpression star()
Description copied from interface: RegularExpression
Let N1 = (Q1, Σ, δ1, q1, F1) recognize A1. Construct N = (Q, Σ, δ, q0, F) to recognize A1*.
  1. Q = {q0}∪Q1. The states of N are the states of N1 plus a new start state.
  2. The state q0 is the new start state
  3. F = {q0}∪F1. The accept states are the old accept states plus the new start state.
  4. Define δ so that for any q ∈ Q and any a ∈ Σε,

Specified by:
star in interface RegularExpression
Returns:
a new RegularExpression equal to R*

equals

public boolean equals(java.lang.Object o)
Overrides:
equals in class java.lang.Object

equals

public abstract boolean equals(RegularExpression o)
Specified by:
equals in interface RegularExpression

escapedRegexpChars

protected static final java.lang.String escapedRegexpChars(java.lang.String unsafe)
When we output a regular expression as a string we have to take care as to how it is formatted. Characters such as the open parenthesis '(' are control characters that have special meaning. In order to allow those special characters to be used inside a string NOT as control characters we escape them with a backslash '\'. Thus the string "(hello)" becomes "\(hello\)". The blackslash itself can be escaped with another backslash '\\' in order to escape itself


parenthesizedRegexp

protected static final java.lang.String parenthesizedRegexp(java.lang.String unsafe)

parenthesizedRegexp

protected static final java.lang.String parenthesizedRegexp(java.lang.String unsafe,
                                                            boolean parenSingleChars)

properlyParenthesized

protected static final boolean properlyParenthesized(java.lang.String string)

complement

public RegularExpression complement()
Description copied from interface: RegularExpression
Complements the language that this regular expression accepts. This method may or may not return a new RegularExpression. If it does not, then it must return a reference to the regexp complemented

Specified by:
complement in interface RegularExpression

equivalent

public boolean equivalent(RegularExpression r2)
Specified by:
equivalent in interface RegularExpression