package finiteAutomata;
import java.util.Vector;
/**
* A non-empty set of symbols. Alphabets are naturally associated
* with both finite automata (input symbols) and grammars (terminal
* symbols).
*
* @author Barbara Wahl
* @version Fall 2007
*/
public class Alphabet {
// ** DATA FIELDS **
/**
* alphabet symbols
*/
protected StringBuffer alpha;
// ** CONSTRUCTOR **
/**
* creates an Alphabet from the characters in a given string.
* @param inString String containing the desired alphabet characters
* in the desired lexicographic order
* @pre inString is a non-empty string
* @pre inString has no repeated characters
* @pre inString has no whitespace characters
* @post creates an Alphabet object whose symbols are the characters
* in inString
*/
public Alphabet(String inString)
{
Assert.pre(inString.length() > 0, "inString is a non-empty string");
Assert.pre(!Util.hasRepeat(inString),
"inString has no repeated characters");
Assert.pre(!Util.hasWhiteSpace(inString),
"inString has no whitespace characters");
alpha = new StringBuffer(inString);
}
// ** PUBLIC METHODS **
/**
* Returns number of symbols in this Alphabet.
* @return alpha.length()
*/
public int size()
{
return alpha.length();
}
/**
* Determines if a given character is a symbol in this Alphabet.
* @param c char to be located
* @return true iff the given character is in this Alphabet
*/
public boolean contains(char c)
{
// indexOf returns a non-negative result if the char
// is found in the String
return (alpha.toString().indexOf(c) >= 0);
}
/**
* Determines the position of a given character in this Alphabet.
* @param c char to be located
* @return non-negative integer position of c in this
* Alphabet, or -1 if c not found
*/
public int indexOf(char c)
{
return alpha.toString().indexOf(c);
}
/**
* Returns the i-th symbol in this Alphabet.
* @param i int position of interest
* @return char at position i in this Alphabet
* @pre 0 <= i < this.size()
*/
public char charAt(int i)
{
Assert.pre(0 <= i && i < this.size(),"0 <= i < alpha.size");
return alpha.charAt(i);
}
/**
* Converts this Alphabet to a String of symbols.
* @return a String version of this Alphabet with no punctuation
* or spaces
*/
public String toString()
// post: returns a String copy of alphabet symbols
{
return alpha.toString();
}
/**
* Converts this Alphabet to a String of symbols punctuated with braces
* and commas.
* @return a pretty String version of this Alphabet
*/
public String toPrettyString()
{
StringBuffer returnString = new StringBuffer();
returnString.append("{");
for(int i=0; i<alpha.length() - 1; i++)
returnString.append(alpha.charAt(i)+",");
returnString.append(alpha.charAt(alpha.length()-1) + "}");
return returnString.toString();
}
/**
* Converts each character in the given String to its position in this
* Alphabet.
* @param inString the String of characters to be converted
* @param array of integers for returning the list
* of positions
* @return true iff every character in inString is a symbol
* in this Alphabet
* @pre inString is not null, and array.length >= inString.length()
* @post if every character in inString is a symbol in this Alphabet,
* the initial segment of array will contain the position numbers
* of the corresponding characters in inString
*/
public boolean indexArray(String inString, int[] array)
{
Assert.pre(array.length >= inString.length(),
"array is at least as long as inString");
int index;
// for each character in inString ...
for(int i=0; i<inString.length(); i++)
{
// use String class methods to find position of the symbol
// in alpha
char c = inString.charAt(i);
index = alpha.toString().indexOf(c);
if(index < 0) // if symbol is not in this Alphabet...
return false; // failure!
array[i] = index; // else, record position in array
}
return true; // success!
}
/**
* Prints a given Vector of StringBuffer objects.
* @param v Vector of StringBuffer objects to be printed
* @pre v is not null and has no null elements
* @post prints the strings in v, one per line; if the empty string
* is encountered, prints "epsilon" instead of ""
*/
public static void printLanguage(Vector v)
{
String s;
for(int i=0; i < v.size(); i++)
{
s = ((StringBuffer)v.get(i)).toString();
Util.printString(s);
System.out.println();
}
}
/**
* Generates the language of all strings over this Alphabet up to
* a given length.
* @param n maximum string length
* @return Vector containing language alpha* (in lexicographic order)
* up through strings of length n; language strings are stored in the
* Vector as StringBuffer objects.
* @pre n >= 0
*/
public Vector getLanguage(int n)
{
Assert.pre(n >= 0, "n is non-negative");
Vector v = new Vector();
v.add(new StringBuffer("")); // first add the empty string
int finger = 0; // pointer for generating more strings
StringBuffer old = (StringBuffer) v.get(finger);
StringBuffer newString; // currently a null reference
while(old.length() < n)
// use old to generate more strings in language
{
// for each symbol in Alphabet...
for(int i=0; i<alpha.length(); i++)
{
newString = new StringBuffer(old.toString());
newString.append(alpha.charAt(i));
v.add(newString);
}
finger++; // advance finger
// update "old" reference
old = (StringBuffer) v.get(finger);
}
return v;
}
// ** TEST METHOD **
public static void main(String[] args) {
// create two different Alphabets, A1 and A2
Alphabet A1 = new Alphabet("x");
System.out.println("A1 = " + A1.toPrettyString());
Alphabet A2 = new Alphabet("01");
System.out.println("A2 = " + A2.toPrettyString());
// For n = 0, 1, 2, 3 call language on A1 & display
// the strings in A1* up through length n using printLanguage.
// Use System.out.println to print helpful headings!!
for(int n=0; n<4; n++)
{
System.out.println("Here is A1* " +
"up through length " + n + ":");
Alphabet.printLanguage(A1.getLanguage(n));
System.out.println();
}
// For n = 0, 1, 2, 3 call language on A2 & display
// the strings in A1* up through length n using printLanguage.
// Use System.out.println to print helpful headings!!
for(int n=0; n<4; n++)
{
System.out.println("Here is A2* " +
"up through length " + n + ":");
Alphabet.printLanguage(A2.getLanguage(n));
System.out.println();
}
}
}