يمكنني تنفيذ التحولات الدولة لDFA في جافا باستخدام java.util.Set

Question

وأنا تنفيذ DFA أقرب ما بوسعي لتعريف رسمي كعملية تعلم (والمدونات المادية)

وخططت على استخدام java.util.Set حيث تشارك مجموعة في التعريف.

والتعريف ينطوي على مجموعة من الصفوف لتحديد التحولات الدولة القانونية: (الدولة، رمز) -> nextState

ولدي الطبقة الانتقالية مع دولة عضوا، رمز وnextState. لقد نفذت يساوي () وشفرة التجزئة () تشير إلى أن اثنين من التحولات متساوية إذا كانت المباراة على الدولة ورمز. وبعد ذلك يكون لها java.util.Set من الحالات الانتقالية.

في بلدي خوارزمية معالجة، أود أن الحالة الراهنة عندما قرأت رمز المقبل. كان متوقعا بناء كائن الانتقال باستخدام هذين لسحب الانتقال مطابقة من مجموعة المبادئ والقواعد التي من شأنها ثم تخبرني الدولة القادمة، وأنا لا يمكن تكرار.

ولكن - وأنا لا أرى أي وسيلة لاستخراج عضوا في java.util.Set لاستخدامها مرة أخرى. يمكنني إزالة (كائن س)، ولكن هذا مجرد العودة منطقية.

وماذا أفعل الخطأ؟

Answer 1

وتعيين ربما لا يكون ما تريد استخدامه لهذا الغرض. توصيتي سيكون لاستخدام قائمة <الانتقالي>، أو ربما خريطة <الدولة، قائمة <الانتقالية >>. لست متأكدا من شأنه أن يكون أفضل دون بناء الواقع والقيام ببعض المقارنة.

Answer 2

ويبدو كما لو الغلابة الخاص بك على قدم المساواة () وشفرة التجزئة () غير مشكوك فيها، لأن التحول الأصلي يطابق واحد في مجموعة وفقا لمتساوين () وبعد وهما يست قابلة للتبديل (وإلا كنت مجرد استخدام جديدة الانتقال في المكان الأصلي).

وربما كنت ترغب في الفئة التي ليست سوى مزيج من الدولة ورمز من دون غيرها من الصفات، وأنه نتيجة لاستخدام مفتاح في الخريطة. بدلا من ذلك يمكن استخدام Map<State, Map<Symbol, State>>

Answer 3

وأنا أتفق مع ماثيو بوراكير أن Set ربما لا ما تحتاجه. قد ترغب في محاولة enums بدلا من ذلك؛ انظر جافا مسرد على سبيل المثال.

Answer 4

لا يمكن أن ينجز ذلك دون وجود بعض جمع الخارجي للدول، أو حتى الكائنات Transistion؟ إذا تم تعريف الطبقة الخارجية مثل:

public class State
{
    private Map<Symbol, State> transitions = new HashMap<Symbol, State>();

    public State() { /* populate transitions somehow */ }

    public State nextState(Symbol symbol) { return transitions.get(symbol); }
}

وبعد ذلك، إذا كان لديك إشارة إلى الحالة الأولية، يمكنك نقل فقط من دولة إلى أخرى من هذا القبيل:

State initial = getInitialStateSomehow();
State second = initial.nextState(SYMBOL_1);
State third = initial.nextState(SYMBOL_2);  // etc...

Answer 5

ونعم انا من النوع الخلط حول لماذا تحتاج حتى مجموعة على الإطلاق.

لآلة الدولة بسيطة يمكنك فقط استخدام الأعداد الصحيحة الثابتة وبيان حالة للقيام جهاز الدولة الخاصة بك مثل هذا:

int STATE1 = 1; 
int STATE2 = 2;
int STATE3 = 3;
int STATE4 = 4;

int currentstate = STATE1 ;
int input = nextInput();


while(currentstate != STATE4 ){
   switch(input){
      case STATE1: 
          if(input == 'a') currentstate = STATE2; 
          break;
      case STATE2: 
          if(input == 'b') currentstate = STATE3;
          else currentstate = STATE1;
          break;
      case STATE3: 
          if(input == 'c')  currentstate = STATE4;
          else currentstate = STATE1;
      }
 }

هذا هو آلة الدولة الأساسية التي ستبحث عن أي سلسلة تحتوي على 'اي بي سي'. هل يمكن أن تمتد بسهولة أن ننظر للغاية بالنسبة أساسها * ج أو ما تريد.

وحتى ما إذا كنت ترغب في آلة الدولة الحيوية، التي بنيت في وقت التشغيل؟ حسنا، لقد فعلت ذلك أيضا. ليس من الصعب جدا. ما فعلته هو خلق مستوى الدولة مع قائمة من التحولات. كل انتقال لديه مؤشر للدولة المقبلة، ومعايير لربط جرا.

وهكذا على سبيل المثال، فإن STATE1 يكون الانتقال مع معايير "أ" ومؤشر إلى بعض الكائن الذي يمثل STATE2. سيكون رمز تبدو تحقق المعايير (والذي يمكن أن يكون الكائن الذي يأخذ الباحث كمعلمة وإرجاع صحيحة أو خاطئة إذا كان يتطابق) وإذا كانت معايير الملائمة، فإنه تحريك مؤشر الدولة على أشارت الدولة أيضا من خلال الانتقال.

والرمز يمكن أن ننظر بشيء من مثل تي إتش إس

و

public void move(int input){
   for(transition t : currentState.transitions){
      if(t.getCriteria().matches(input)){
         currentState = t.getNextState();
         break;
      }
   }
}

و

Answer 6

إذا كنت ترغب فقط في تطبيق محرك نمط مطابقة، قد يكون نمط تصميم الدولة لا لزوم له منذ طقطق غير المحتمل أن يتغير. كما أشار تشاد خارج، وذلك باستخدام switch لترميز وظيفة الانتقال غير مقبول تماما في مثل هذه الحالات.

وهنا مثال على نمط nondeterministic إنسان مطابقة يستخدم مجموعات:

public boolean validate() {
    Set<Integer> currentStates = new HashSet<Integer>();
    final Set<Integer> acceptingStates = new HashSet<Integer>();

    currentStates.add(0); // Initial state.
    acceptingStates.add(1);
    acceptingStates.add(3);
    acceptingStates.add(6);

    for (int i = 0; i < getInput().length(); i++) {
        char c = getInput().charAt(i);
        Set<Integer> newStates = new HashSet<Integer>();

        for (int state : currentStates) {
            switch (state) {
                case 0:
                    if (c == 'a')
                        newStates.add(1);
                    break;
                case 1:
                    if (c == 'b') {
                        newStates.add(2);
                        newStates.add(4);
                    }
                    break;
                case 2:
                    if (c == 'b')
                        newStates.add(3);
                    break;
                case 3:
                    if (c == 'b')
                        newStates.add(2);
                    break;
                case 4:
                    if (c == 'b')
                        newStates.add(5);
                    break;
                case 5:
                    if (c == 'b')
                        newStates.add(6);
                    break;
                case 6:
                    if (c == 'b')
                        newStates.add(4);
                    break;
            }
        }

        if (newStates.size() == 0)
            return false;
        currentStates = newStates;

        System.out.printf("Character read: %c\n", c);
        System.out.printf("Current states: ");
        printStates(currentStates);
    }

    for (int state : acceptingStates)
        if (currentStates.contains(state))
            return true;
    return false;
}

وهذا إنسان يعترف إدخال الكلمات من اللغة العادية التي وصفها "a(bb*|bbb*) نمط "، أي" أ "متبوعة إما مضاعفات اثنين أو مضاعفات الثلاثة عديدة" ب ق ".