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 N₁ = (Q₁, Σ, δ₁, q₁, F₁) recognize A₁, and N₂ = (Q₂, Σ, δ₂, q₂, F₂) recognize A₂.

Construct N = (Q, Σ, δ, q₀, F) to recognize A₁∪A₂.

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

Specified by:

union in interface RegularExpression

Returns:

a new RegularExpression equal to A₁∪A₂

concatenate

public RegularExpression concatenate(RegularExpression regexp)

Description copied from interface: RegularExpression

Let N₁ = (Q₁, Σ, δ₁, q₁, F₁) recognize A₁, and N₂, Σ, δ₂, q₂, F₂) recognize A₂.

Construct N = (Q, Σ, δ, q₁, F₂) to recognize A₁⋅A₂.

1. Q = Q₁∪Q₂. The states of N are all the states of N₁ and N₂.
2. The state q₁ is the same as the start state of N₁.
3. The accept states F₂ are the same as the accept states of N₂.
4. Define δ so that for any q ∈ Q and any a ∈ Σ_ε,

Specified by:

concatenate in interface RegularExpression

Returns:

a new RegularExpression equal to N₁⋅N₂

star

public RegularExpression star()

Description copied from interface: RegularExpression

Let N₁ = (Q₁, Σ, δ₁, q₁, F₁) recognize A₁. Construct N = (Q, Σ, δ, q₀, F) to recognize A₁*.

1. Q = {q₀}∪Q₁. The states of N are the states of N₁ plus a new start state.
2. The state q₀ is the new start state
3. F = {q₀}∪F₁. 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