Java Language Recognizer

Question

I was given the assignment to "implement and test a language “recognizer” object, provided to you through a Java interface defined at the end of this document. A language recognizer accepts strings of characters and determines whether or not they are in the language."

The language is as follows:

L = {a*b} union {ab*}, or restated in English, L is the set of all strings of either (1) zero or more as (a*) followed by a b, or (2) an a followed by zero or more bs (b*).

I've made some progress, but I'm stuck.

Here's the interface:

/** The Recognizer interface provides a recognizer for the
* language L below.
*
* Let Sigma = {a,b} = the input character set.
*
* Let L = {ab*} union {a*b} be the language (set of
* legal strings) recognized by this recognizer.
*
* Let S = s1s2...sn be the string of n characters already
* input by this recognizer.
*
* Recognizer constructor must ensure: S' = < >
*/
interface Recognizer {
/**
* require: c in Sigma
*
* ensure: S' = S ^ c
*
* param c
*/
public void nextChar(char c);
/**
* Checks if input string S is in language L.
*
* return (S in L)
*/
public boolean isIn();
/**
* ensure: S' = < >
*/
public void reset();
}

Here's my structure:

import java.util.*;

public class LanguageVector implements Recognizer {

    int element = 0;
    int a = 0;
    int b = 0;

    Vector<Character> v = new Vector<Character>();

    public void nextChar(char c) {
            v.add(c);
        }

    public boolean isIn(){
            boolean isTrue = true;
            for(int i=0;i<v.size();i++) {
                if (v.size() == 1){
                    if (v.firstElement() == 'a' || v.firstElement() =='b'){
                        isTrue = true;
                        }
                    else
                        isTrue = false;
                }
                else if (v.firstElement() == 'a'){
                        if (v.lastElement() == 'a')
                            isTrue = false;
                        else if (v.lastElement() == 'b')
                            while (v.elementAt(element)== 'a' ){
                                a++;
                                element++;
                                System.out.println(element);
                            }
                            while (v.elementAt(element)== 'b'){
                                b++;
                                element++;
                                System.out.println(element);
                                }
                            if (v.elementAt(element)!= 'b'){
                                isTrue = false;
                            }
                            else if (a > 1 && b > 1){
                                isTrue = false;
                            }
                            else
                                isTrue = true;
                    }
                else if (v.firstElement() == 'b'){
                        isTrue = false;
                        }
                else
                    isTrue = false;
            }
            return isTrue;
            }


    public void reset(){
                v.clear();
            }

}

And here's my testing class:

import java.util.*;

public class LanguageTester {
    /**
     * @param args
     */
    public static void main(String[] args) {
        Recognizer r = new LanguageVector();

        r.nextChar('a');

        r.nextChar('a');

        r.nextChar('a');

        r.nextChar('b');

        if (r.isIn())
            System.out.println("string is in L");
        else
            System.out.println("string is not in L");
        System.out.println("End of test");
        r.reset();
    }
}

When I run, I get the following output:

1
2
3
Exception in thread "main" 4
java.lang.ArrayIndexOutOfBoundsException: 4 >= 4
    at java.util.Vector.elementAt(Unknown Source)
    at LanguageVector.isIn(LanguageVector.java:34)
    at LanguageTester.main(LanguageTester.java:18)

Why is this happening?

Also, how can I use user input, turn it into a vector, and use that within this structure now?

Forgive me if this question is too lengthy, I wasn't sure how to narrow it down without leaving important details out. Thanks

Answer 1

When it occurs?

Out of bounds exception is occurred when you try to access an array with index that exceeded its length. maximum index of a java array is (length -1) for example:

String [] stringArray = new String[10];
stringArray[10]
// the code above will produce an out of bounds exception, because the it bigger than length -1, which is 10 - 1 = 9.

If you don't know the size or length of an array, you can know it from stringArray.length.

How to handle it?

You should make sure that your program doesn't access an array with index bigger than length - 1. example:

for(int i=0;i<stringArray.lenght;i++) {
    //write your code here
}

the above code will guarantee that stringArray will never be accessed beyond its maximum index.

Your Case

In your case, 4 >= 4 itself says you are trying to access 5th element i.e. elementAt(4) however size of your Vector of 4.

Array is based on 0 index i.e. if your length is 4 you will have data at as Vector[0], Vector[1], Vector[2], Vector[3]. Also read this for more info...

Answer 2

The problem is in the isIn() method. You're not checking whether the element variable is still below v.size(). You just continue incrementing it so the next time that the application accesses v.elementAt(element); the variable element is bigger than the size of v, so it's an ArrayOutofBounds exception.