java.util.set을 사용하여 Java에서 DFA의 상태 전환을 구현할 수 있습니까?

StackOverflow https://stackoverflow.com/questions/444889

문제

학습 운동 (및 블로깅 자료)으로서 공식적인 정의에 최대한 가까운 DFA를 구현하고 있습니다.

정의에 세트가 관련된 java.util.set를 사용할 계획이었습니다.

정의에는 법적 상태 전환을 정의하기위한 튜플 세트가 포함됩니다.

회원 상태, 기호 및 다음 상태와 전환 클래스가 있습니다. 나는 equals () 및 hashcode ()를 구현하여 상태와 기호에서 일치하면 두 개의 전환이 동일하다는 것을 나타냅니다. 그런 다음 java.util. 세트의 전환 인스턴스가 있습니다.

처리 알고리즘에서 다음 기호를 읽을 때 현재 상태가 있습니다. 이 두 가지를 사용하여 전환 객체를 구축하여 세트에서 일치하는 전환을 꺼내고 다음 상태를 알려줄 것으로 예상했습니다.

그러나 - 추가 사용을 위해 java.util.set의 멤버를 추출하는 방법이 보이지 않습니다. 제거 할 수 있지만 (Object O), 단지 부울을 반환합니다.

내가 뭘 잘못하고 있죠?

도움이 되었습니까?

해결책

세트는 아마도 이것에 사용하고 싶은 것이 아닐 것입니다. 내 권장 사항은 목록 <Transition> 또는 아마도지도 <state, list <antransition >>를 사용하는 것입니다. 나는 실제로 그것을 만들거나 벤치마킹을하지 않고 어느 쪽이 더 좋을지 잘 모르겠습니다.

다른 팁

원래 전환이 Equals ()에 따라 세트의 세트와 일치하기 때문에 Equals () 및 hashcode ()의 재정의 마치 마치 마치 모호한 것처럼 들립니다. 원본의.)

당신은 아마도 다른 속성이없는 상태와 기호의 조합 인 클래스를 원하고 그것을 맵에서 키로 사용합니다. 또는 당신은 a를 사용할 수 있습니다 Map<State, Map<Symbol, State>>

나는 Matthew Brubaker에 동의합니다 Set 아마도 당신이 필요로하는 것이 아닐 것입니다. 시도하고 싶을 수도 있습니다 enums 대신에; 참조 자바 용어집 예를 들어.

외부 상태 또는 전환 개체가 없으면 이것을 달성 할 수 없습니까? 주 계급이 다음과 같이 정의 된 경우

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...

네, 왜 컬렉션이 필요한지에 대해 혼란스러워합니다.

간단한 상태 머신의 경우 정적 정수와 사례 명령문을 사용하여 다음과 같이 상태 기계를 수행 할 수 있습니다. 

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;
      }
 }

그것은 'ABC'가 포함 된 모든 문자열을 찾는 기본 상태 머신입니다. AB*C 또는 원하는 것을 쉽게 확장 할 수 있습니다.

그렇다면 런타임에 구축 된 동적 상태 기계를 원한다면 어떻게해야합니까? 글쎄, 나도 이것도했다. 너무 어렵지 않습니다. 내가 한 일은 전환 목록이있는 상태 클래스를 만드는 것입니다. 각 전환에는 다음 상태에 대한 포인터가 있으며 연결 기준이 있습니다.

예를 들어, State1은 기준 'A'와 State2를 나타내는 일부 객체에 대한 포인터에 대한 전환을 가질 것입니다. 코드는 기준을 확인하고 (int를 매개 변수로 취하고 일치하는 경우 true 또는 false를 반환하는 객체 일 수 있음), 일치하는 기준이 일치하면 상태 포인터를 전환에 의해 지적한 상태로 이동합니다.

코드는 Ths와 같은 것처럼 보일 수 있습니다

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

패턴 일치 엔진을 구현하려면 패턴이 변경되지 않기 때문에 상태 설계 패턴이 불필요 할 수 있습니다. 차드가 지적했듯이 a switch 이러한 경우 전이 기능을 인코딩하는 것은 완전히 허용됩니다.

다음은 세트를 사용하는 비정상적인 패턴 일치 오토 마톤의 예입니다.

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*)", 즉“A”와 3 개 또는 3 개 중 배수의 배수가 뒤 따릅니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top