0

正規表現とはまったく異なる検索という特別な目的で NFA を構築しようとしています。状態は次の形式です

class State implements List{
//GLOBAL DATA

static int depth;

//STATE VALUES
String stateName;
ArrayList<String> label = new ArrayList<>(); //Label for states

//LINKS TO OTHER STATES
boolean finalState;
ArrayList<State> nextState ; // Link with multiple next states

State preState;             // previous state

public State()
{

    stateName = "";
    finalState = true;
    nextState = new ArrayList<>();

}
public void addlabel(String lbl)
{
    if(!this.label.contains(lbl))
        this.label.add(lbl);
}
public State(String state, String lbl)
{
    this.stateName = state;
    if(!this.label.contains(lbl))
       this.label.add(lbl);
    depth++;

}

public State(String state, String lbl, boolean fstate)
{

    this.stateName = state;
    this.label.add(lbl);
    this.finalState = fstate;

    this.nextState = new ArrayList<>();
}
void displayState()
{

    System.out.print(this.stateName+" --> ");
    for(Iterator<String> it = label.iterator(); it.hasNext();)
    {
        System.out.print(it.next()+" , ");
    }
    System.out.println("\nNo of States : "+State.depth);
}

次に、NFA クラスは

public class NFA
{

static final String[] STATES= {"A","B","C","D","E","F","G","H","I","J","K","L","M"
                            ,"N","O","P","Q","R","S","T","U","V","W","X","Y","Z"};
State startState;
State currentState;
static int level;
public NFA()
{
    startState = new State();
    startState = null;
    currentState = new State();
    currentState = null;
    startState = currentState;
}

/**
 *
 * @param st
 */
NFA(State startstate)
{
    startState = new State();
    startState = startstate;
    currentState = new State();
    currentState = null;
    currentState = startState ; // To show that their is only one element in NFA
}

boolean insertState(State newState)
{

    newState.nextState = new ArrayList<>();
    if(currentState == null && startState == null ) //if empty NFA
    {
        newState.preState = null;
        startState = newState;
        currentState = newState;
        State.depth = 0;
        return true;
    }
    else 
    {
        if(!Exist(newState.stateName))//Exist is used to check for duplicates
        {

                newState.preState = currentState ;
                currentState.nextState.add(newState);
                currentState = newState;
                State.depth++;
                return true;
        }
    }
    return false;
}

boolean insertState(State newState, String label)
{
        newState.label.add(label);
        newState.nextState = null;
        newState.preState = null;

    if(currentState == null && startState == null)
    {
        startState = newState;
        currentState = newState;
        State.depth = 0;
       return true; 
    }
    else 
    {
        if(!Exist(newState.stateName))
        {

                newState.preState = currentState;
                currentState.nextState.add(newState);
                currentState = newState;
                State.depth++;
                return true;

        }
        else
        {
            ///code goes here

        }
    }
    return false;
}

void markFinal(State s)
{
    s.finalState = true;
}
void unmarkFinal(State s)
{
    s.finalState = false;
}

boolean Exist(String s)
{
    State temp = startState;
    if(startState.stateName.equals(s))
        return true;
    Iterator<State> it = temp.nextState.iterator();
    while(it.hasNext())
    {

        Iterator<State> i  = it ;//startState.nextState.iterator();

           {
            while(i.hasNext())
            {

                if(i.next().stateName.equals(s))
                    return true;

            }


        }
        //else
          //  return false;
    }
    return false;
}
void displayNfa()
{
    State st = startState;
    if(startState == null && currentState == null)
    {
        System.out.println("The NFA is empty");
    }
    else
    {

        while(st != null)
        {
            if(!st.nextState.isEmpty())
            {
                Iterator<State> it = st.nextState.iterator();

                do
                {
                    st.displayState();
                    st = it.next();
                }while(it.hasNext());
            }
            else
            {
                st = null;
            }
        }
    }
    System.out.println();
}


/**
 * @param args the command line arguments
 */

/**
 *
 * @param args the command line arguments
 */
public static void main(String[] args) 
{
    // TODO code application logic here
    NFA l = new NFA();
    State s = new State("A11", "a",false);

    NFA ll = new NFA(s);
    s = new State("A111", "a",false);
    ll.insertState(s);
    ll.insertState(new State("A1","0"));
    ll.insertState(new State("A1111","0"));

    ll.displayNfa();
    int j = 1;
    for(int i = 0 ; i < 2 ; i++)
    {

        int rand = (int) (Math.random()* 10);
        State st = new State(STATES[rand],String.valueOf(i), false);
        if(l.insertState(st))
        {
            System.out.println(j+" : " + STATES[rand]+" and "+String.valueOf(i)+ " inserted");
            j++;
        }
    }
        l.displayNfa();
        System.out.println("No of states inserted : "+ j--);
}

私は次のことをしたい

  1. このプログラムは、常に最後の状態を表示するためにスキップします。つまり、10 個の状態が挿入されている場合、9 個だけが表示されます。
  2. exist() メソッドでは、2 つのイテレータを使用しましたが、なぜ機能するのかわかりません
  3. イテレータを扱うときに、既存のクラス名を検索する方法がわかりません。
  4. どのように現在の状態を追跡し、nextState リスト、ラベル リストを深さ優先順で適切に反復処理する必要がありますか。
  5. 一意の状態を挿入する方法、つまり、状態「A」が一度挿入された場合、再度挿入するべきではありません (exist メソッドは機能しません)。

よろしくお願いします

4

1 に答える 1