org.metasyntactic.math.automata
Interface RegularExpression

All Superinterfaces:

FiniteAutomata, java.io.Serializable

All Known Implementing Classes:

AbstractRegularExpression

public interface RegularExpression

extends FiniteAutomata

FORMAL DEFINITION OF A REGULAR EXPRESSION

Say that R is a regular expression if R is

1. a for some a in the alphabet Σ,
2. ε,
3. ∅,
4. (R₁∪R₂), where R₁ and R₂ are regular expressions,
5. (R₁⋅R₂), where R₁ and R₂ are regular expressions, or
6. (R₁^*), where R₁ is a regular expression

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₁ and R₂, or the star of the language R₁, 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₁ and R₂ 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 N1 = (Q1, Σ, δ1, q1, F1) recognize A1, and N2, Σ, δ2, q2, F2) recognize A2.
boolean	equals(RegularExpression regexp)
boolean	equivalent(RegularExpression regexp)
int	hashCode()
RegularExpression	star() Let N1 = (Q1, Σ, δ1, q1, F1) recognize A1.
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 N1 = (Q1, Σ, δ1, q1, F1) recognize A1, and N2 = (Q2, Σ, δ2, q2, F2) recognize A2.

Methods inherited from interface org.metasyntactic.math.automata.FiniteAutomata

accept

Method Detail

concatenate

public RegularExpression concatenate(RegularExpression re)

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 ∈ Σ_ε,

Returns:

a new RegularExpression equal to N₁⋅N₂

union

public RegularExpression union(RegularExpression re)

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 ∈ Σ_ε,

Returns:

a new RegularExpression equal to A₁∪A₂

star

public RegularExpression star()

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 ∈ Σ_ε,

Returns:

a new RegularExpression equal to R^*

complement

public RegularExpression complement()

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

toNondeterministicFiniteAutomata

public NondeterministicFiniteAutomata toNondeterministicFiniteAutomata()

Returns an NFA that accepts the same regular language that this regular expression accepts.

Returns:

An NFA equivalent to this

hashCode

public int hashCode()

Overrides:

hashCode in class java.lang.Object

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

equals

public boolean equals(RegularExpression regexp)

equivalent

public boolean equivalent(RegularExpression regexp)