상태 머신에 사용 [닫기]

Question

프로그래밍의 어떤 영역에서 상태 머신을 사용합니까?왜 ?어떻게 구현할 수 있나요?

편집하다: 너무 많은 질문이 아니라면 실용적인 예를 들어주세요.

Answer 1

어떤 프로그래밍 영역에서 상태 기계를 사용합니까?

상태 머신을 사용하여 제한된 수의 조건에 존재할 수있는 (실제 또는 논리적) 객체를 나타냅니다 (”주") 고정 된 규칙 세트에 따라 한 주에서 다음 상태로 진행됩니다.

주 머신을 사용하는 이유는 무엇입니까?

상태 기계는 종종 a 매우 복잡한 규칙과 조건 세트를 나타내고 다양한 입력을 처리하는 소형 방법. 메모리가 제한된 임베디드 장치에 상태 머신이 표시됩니다. 잘 구현 된 상태 머신은 각 논리적 상태가 신체 상태를 나타 내기 때문에 자체 문서화입니다. 상태 기계는 a 매우 작은 절차 적 동등성과 비교하여 코드의 양과 매우 효율적으로 실행됩니다. 또한, 상태 변경을 관리하는 규칙은 종종 테이블에 데이터로 저장 될 수 있으며, 쉽게 유지할 수있는 컴팩트 한 표현을 제공합니다.

하나를 구현하려면 어떻게해야합니까?

사소한 예 :

enum states {      // Define the states in the state machine.
  NO_PIZZA,        // Exit state machine.
  COUNT_PEOPLE,    // Ask user for # of people.
  COUNT_SLICES,    // Ask user for # slices.
  SERVE_PIZZA,     // Validate and serve.
  EAT_PIZZA        // Task is complete.
} STATE;

STATE state = COUNT_PEOPLE;
int nPeople, nSlices, nSlicesPerPerson;

// Serve slices of pizza to people, so that each person gets
/// the same number of slices.   
while (state != NO_PIZZA)  {
   switch (state)  {
   case COUNT_PEOPLE:  
       if (promptForPeople(&nPeople))  // If input is valid..
           state = COUNT_SLICES;       // .. go to next state..
       break;                          // .. else remain in this state.
   case COUNT_SLICES:  
       if (promptForSlices(&nSlices))
          state = SERVE_PIZZA;
        break;
   case SERVE_PIZZA:
       if (nSlices % nPeople != 0)    // Can't divide the pizza evenly.
       {                             
           getMorePizzaOrFriends();   // Do something about it.
           state = COUNT_PEOPLE;      // Start over.
       }
       else
       {
           nSlicesPerPerson = nSlices/nPeople;
           state = EAT_PIZZA;
       }
       break;
   case EAT_PIZZA:
       // etc...
       state = NO_PIZZA;  // Exit the state machine.
       break;
   } // switch
} // while

메모:

• 예제는 a를 사용합니다 switch() 명시 적으로 case/break 단순성을위한 상태. 실제로, a case 종종 다음 상태로 "넘어 질 것"입니다.

• 대형 상태 기계를 쉽게 유지할 수 있도록 각에서 수행 된 작업 case "작업자"기능으로 캡슐화 될 수 있습니다. 상단에 입력을 얻으십시오 while(),이를 작업자 기능으로 전달하고 다음 상태를 계산할 작업자의 반환 값을 확인하십시오.

• 소형을 위해 전체 switch() 기능 포인터 배열로 교체 할 수 있습니다. 각 상태는 리턴 값이 다음 상태에 대한 포인터 인 함수로 구현됩니다. 경고: 이렇게하면 상태 머신을 단순화하거나 완전히 인재 할 수 없으므로 구현을주의 깊게 고려하십시오!

• 임베디드 장치는 치명적인 오류 만 종료하는 상태 머신으로 구현 될 수 있으며, 그 후에는 하드 리셋을 수행하고 상태 머신을 다시 입력합니다.

Answer 2

이미 몇 가지 훌륭한 답변. 약간 다른 관점에서는 더 큰 문자열로 텍스트를 검색하는 것을 고려하십시오. 누군가는 이미 정규 표현을 언급했으며 이것은 중요한 사례 일뿐입니다.

다음 방법 호출을 고려하십시오.

very_long_text = "Bereshit bara Elohim et hashamayim ve'et ha'arets." …
word = "Elohim"
position = find_in_string(very_long_text, word)

어떻게 구현하겠습니까? find_in_string? 쉬운 접근 방식은 다음과 같은 중첩 루프를 사용합니다.

for i in 0 … length(very_long_text) - length(word):
    found = true
    for j in 0 … length(word):
        if (very_long_text[i] != word[j]):
            found = false
            break
    if found: return i
return -1

이것이 비효율적이라는 사실 외에도 상태 기계를 형성합니다! 여기의 주들은 다소 숨겨져 있습니다. 코드를 약간 다시 작성하여 더 눈에 띄게하겠습니다.

state = 0
for i in 0 … length(very_long_text) - length(word):
    if very_long_text[i] == word[state]:
        state += 1
        if state == length(word) + 1: return i
    else:
        state = 0
return -1

여기서 다른 상태는 우리가 검색하는 단어의 모든 다른 위치를 직접 나타냅니다. 그래프에는 각 노드에 대해 두 가지 전환이 있습니다. 문자가 일치하면 다음 상태로 이동하십시오. 다른 모든 입력에 대해 (즉, 현재 위치의 다른 모든 문자), 0으로 돌아갑니다.

이 약간의 개혁은 큰 이점이 있습니다. 이제 일부 기본 기술을 사용하여 더 나은 성능을 제공하도록 조정할 수 있습니다. 실제로, 모든 고급 문자열 검색 알고리즘 (현재 인덱스 데이터 구조 할인) 은이 상태 머신 위에 구축되어 일부 측면을 향상시킵니다.

Answer 3

어떤 종류의 작업?

내가 본 것만으로도 모든 종류의 구문 분석은 종종 상태 기계로 구현됩니다.

왜요?

문법을 구문 분석하는 것은 일반적으로 간단한 작업이 아닙니다. 설계 단계에서는 구문 분석 알고리즘을 테스트하기 위해 상태 다이어그램이 그려지는 것이 일반적입니다. 이를 주 머신 구현으로 번역하는 것은 상당히 간단한 작업입니다.

어떻게?

글쎄, 당신은 당신의 상상력에 의해서만 제한됩니다.

나는 그것을 봤다 사례 진술 및 루프.

나는 그것을 봤다 라벨과 고토 진술

나는 심지어 현재 상태를 나타내는 기능 포인터의 구조로 그것을 보았습니다. 상태가 바뀌면 하나 이상 기능 포인터 업데이트됩니다.

상태 변경은 단순히 코드의 다른 섹션에서 실행되고 있음을 의미하는 코드에서만 수행 한 것을 보았습니다. (상태 변수가없고 필요한 경우 중복 코드가 없습니다. 이것은 매우 간단한 정렬로 입증 될 수 있으며, 이는 매우 작은 데이터 세트에만 유용합니다.

int a[10] = {some unsorted integers};

not_sorted_state:;
    z = -1;
    while (z < (sizeof(a) / sizeof(a[0]) - 1)
    {
        z = z + 1
        if (a[z] > a[z + 1])
        {
            // ASSERT The array is not in order
            swap(a[z], a[z + 1];        // make the array more sorted
            goto not_sorted_state;      // change state to sort the array
        }
    }
    // ASSERT the array is in order

상태 변수는 없지만 코드 자체는 상태를 나타냅니다.

Answer 4

그만큼 상태 설계 패턴은 유한 상태 기계를 통해 물체의 상태를 나타내는 객체 지향적 인 방법입니다. 일반적으로 해당 객체의 구현의 논리적 복잡성을 줄이는 데 도움이됩니다 (중첩 if, 많은 깃발 등).

Answer 5

대부분의 워크 플로는 상태 기계로 구현 될 수 있습니다. 예를 들어, 처리 신청 또는 주문을 처리합니다.

.NET을 사용하는 경우 Windows Workflow Foundation을 사용해보십시오. 상태 머신 워크 플로를 매우 빠르게 구현할 수 있습니다.

Answer 6

C#을 사용하는 경우 반복기 블록을 작성할 때마다 컴파일러에게 상태 머신을 구축하도록 요청하게 됩니다(반복기에서 현재 위치를 추적하는 등).

Answer 7

다음은 상태 기계의 테스트 및 작업 예입니다. 직렬 스트림 (직렬 포트, TCP/IP 데이터 또는 파일이 일반적인 예)에 있다고 가정 해 봅시다. 이 경우 동기화, 길이 및 페이로드의 세 부분으로 나눌 수있는 특정 패킷 구조를 찾고 있습니다. 나는 3 개의 상태가 있고, 하나는 유휴 상태이며, 동기화를 기다리고, 두 번째는 다음 바이트가 길이가되어야하고 세 번째 상태는 페이로드를 축적하는 것입니다.

이 예제는 하나의 버퍼만으로 순전히 일련의 직렬이며, 여기에 작성된 바이트 나 패킷에서 복구되어 패킷을 버릴 수 있지만 결국 복구하면 슬라이딩 창과 같은 다른 일을 할 수 있습니다. 이것은 새로운 완전한 패킷이 시작될 때 짧게 절단되는 부분 패킷을 말하는 곳이 될 것입니다. 아래 코드는 이것을 감지하지 않으며 부분 및 전체 패킷을 버리고 다음에 복구합니다. 전체 패킷을 모두 처리 해야하는 경우 슬라이딩 윈도우가 저장됩니다.

직렬 데이터 스트림, TCP/IP, 파일 I/O 인 경우 항상 이런 종류의 상태 머신을 사용합니다. 또는 TCP/IP 프로토콜 스스로 자체적으로 이메일을 보내고, 포트를 열고, 서버가 응답을 보내기를 기다리고, Helo를 보내고, 서버가 패킷을 보내기를 기다리고, 패킷을 보내고, 답장을 기다리십시오. 기본적 으로이 경우뿐만 아니라 아래의 경우에도 다음 바이트/패킷이 들어 오기를 기다리고있을 수 있습니다. 기다리고 있던 것을 기억하고 사용할 수있는 것을 기다리는 코드를 재사용하려면 상태 변수. 상태 머신이 논리에 사용되는 것과 같은 방식 (다음 시계를 기다리고있는 것, 내가 기다리고있는 것은 무엇입니까).

로직에서와 마찬가지로, 각 상태마다 다른 일을 할 수 있습니다.이 경우 오프셋을 저장소에 재설정하고 체크섬 축적기를 재설정 할 수 있습니다. 패킷 길이 상태는 정상 제어 경로에서 중단하려는 경우를 보여줍니다. 전부는 실제로 많은 상태 기계가 정상적인 경로 내에서 뛰어 다니거나 반복 될 수있는 것은 아닙니다. 아래는 거의 선형입니다.

이것이 유용하기를 바랍니다. 상태 기계가 소프트웨어에 더 많이 사용되기를 바랍니다.

테스트 데이터는 상태 기계가 회복하는 의도적 인 문제가 있습니다. 첫 번째 좋은 패킷 후에는 일부 쓰레기 데이터, 체크섬이없는 패킷 및 길이가 잘못된 패킷이 있습니다. 내 출력은 다음과 같습니다.

좋은 패킷 : FA0712345678EB 유효하지 않은 동기화 패턴 0x12 유효하지 않은 동기화 패턴 0x34 무효 동기화 패턴 0x56 체크섬 오류 0xBF 유효하지 않은 패킷 길이 0 유효하지 않은 동기화 패턴 0x12 Invalid Sync Pattern 0x34 Invalid Sync Pattern 0x56 NOCOP 44 NOC0264 NOVEB COREEB 56 FORTION COR PANCTER 032 데이터

스트림의 두 가지 좋은 패킷은 잘못된 데이터에도 불구하고 추출되었습니다. 그리고 나쁜 데이터가 감지되어 처리되었습니다.

 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>

unsigned char testdata[] =
{
    0xFA,0x07,0x12,0x34,0x56,0x78,0xEB,  
    0x12,0x34,0x56,  
    0xFA,0x07,0x12,0x34,0x56,0x78,0xAA,  
    0xFA,0x00,0x12,0x34,0x56,0x78,0xEB,  
    0xFA,0x08,0x12,0x34,0x56,0x78,0x00,0xEA  
};

unsigned int testoff=0;

//packet structure  
// [0] packet header 0xFA  
// [1] bytes in packet (n)  
// [2] payload  
// ... payload  
// [n-1] checksum  
//  

unsigned int state;

unsigned int packlen;  
unsigned int packoff;  
unsigned char packet[256];  
unsigned int checksum;  

int process_packet( unsigned char *data, unsigned int len )  
{  
    unsigned int ra;  

    printf("good packet:");
    for(ra=0;ra<len;ra++) printf("%02X",data[ra]);
    printf("\n");
}  
int getbyte ( unsigned char *d )  
{  
    //check peripheral for a new byte  
    //or serialize a packet or file  

    if(testoff<sizeof(testdata))
    {
        *d=testdata[testoff++];
        return(1);
    }
    else
    {
        printf("no more test data\n");
        exit(0);
    }
    return(0);
}

int main ( void )  
{  
    unsigned char b;

    state=0; //idle

    while(1)
    {
        if(getbyte(&b))
        {
            switch(state)
            {
                case 0: //idle
                    if(b!=0xFA)
                    {
                        printf("Invalid sync pattern 0x%02X\n",b);
                        break;
                    }
                    packoff=0;
                    checksum=b;
                    packet[packoff++]=b;

                    state++;
                    break;
                case 1: //packet length
                    checksum+=b;
                    packet[packoff++]=b;

                    packlen=b;
                    if(packlen<3)
                    {
                        printf("Invalid packet length %u\n",packlen);
                        state=0;
                        break;
                    }

                    state++;
                    break;
                case 2: //payload
                    checksum+=b;
                    packet[packoff++]=b;

                    if(packoff>=packlen)
                    {
                        state=0;
                        checksum=checksum&0xFF;
                        if(checksum)
                        {
                            printf("Checksum error 0x%02X\n",checksum);
                        }
                        else
                        {
                            process_packet(packet,packlen);
                        }
                    }
                    break;
            }
        }

        //do other stuff, handle other devices/interfaces

    }
}

Answer 8

상태 기계는 어디에나 있습니다. 상태 머신은 메시지를 수신 할 때 구문 분석 해야하는 통신 인터페이스의 핵심입니다. 또한 엄격한 타이밍 제약으로 인해 작업을 여러 작업으로 분리 해야하는 임베디드 시스템 개발에는 여러 번 발생했습니다.

Answer 9

스크린 스크레이핑 또는 테스트 중인 프로세스를 통해 실행하기 위한 QA 인프라입니다.(이것은 나의 특별한 경험 영역입니다.저는 현재 상태를 스택에 푸시하고 모든 TTY 기반 스크린 스크레이퍼에서 사용할 수 있는 다양한 상태 핸들러 선택 방법을 사용하는 지원을 포함하여 마지막 고용주를 위해 Python으로 상태 머신 프레임워크를 구축했습니다.개념적 모델은 TTY 애플리케이션을 통해 실행되므로 제한된 수의 알려진 상태를 거치며 이전 상태로 다시 이동할 수 있으므로 잘 맞습니다(중첩 메뉴 사용을 고려).이 내용은 공개되었습니다(해당 고용주의 허가를 받아).사용 바자 확인하기 http://web.dyfis.net/bzr/isg_state_machine_framework/ 코드를 보고 싶다면.

티켓, 프로세스 관리 및 워크플로 시스템 - 티켓에 NEW, TRIAGED, IN-PROGRESS, NEEDS-QA, FAILED-QA 및 VERIFIED 간 이동을 결정하는 일련의 규칙이 있는 경우 간단한 상태 머신.

작고 쉽게 입증 가능한 임베디드 시스템 구축 - 신호등 신호는 가능한 모든 상태 목록이 표시되는 주요 예입니다. 가지다 완전히 열거되고 알려져야 합니다.

파서와 어휘 분석기는 상태 머신을 기반으로 합니다. 스트리밍되는 항목이 결정되는 방식은 당시 사용자의 위치에 따라 결정되기 때문입니다.

Answer 10

많은 디지털 하드웨어 설계에는 회로의 동작을 지정하기 위해 상태 머신을 만드는 것이 포함됩니다. VHDL을 작성하는 경우 상당히 나타납니다.

Answer 11

FSM은 여러 상태가있는 곳마다 사용되며 자극에 따라 다른 상태로 전환해야합니다.

(이것은 적어도 이론적으로 대부분의 문제를 포함한다는 것이 밝혀졌습니다)

Answer 12

정규 표현 유한 상태 머신 (또는 "유한 상태 automata")이 수행되는 곳의 또 다른 예입니다.

컴파일 된 Regexp는 유한 상태 기계이며, 정규 표현식이 일치 할 수있는 문자열 세트는 유한 상태 Automata가 허용 할 수있는 언어 ( "일반 언어")입니다.

Answer 13

나는 여기에서 내가 사용한 이유를 실제로 설명하는 것이 여기에서 보지 못했습니다.

실제적인 목적을 위해 프로그래머는 일반적으로 작업 중에 스레드/종료를 반환해야 할 때 하나를 추가해야합니다.

예를 들어, 다중 상태의 HTTP 요청이있는 경우 다음과 같은 서버 코드가있을 수 있습니다.

Show form 1
process form 1
show form 2
process form 2

문제는 양식을 표시 할 때마다 코드가 모두 함께 흐르고 동일한 변수를 사용하더라도 서버의 전체 스레드 (대부분의 언어로)를 종료해야합니다.

코드를 중단하고 스레드를 반환하는 행위는 일반적으로 스위치 명령문으로 수행되며 상태 머신 (매우 기본적인 버전)을 만듭니다.

더 복잡해지면 어떤 주가 유효한 지 파악하기가 어려울 수 있습니다. 사람들은 보통 "상태 전환 테이블"모든 국가 전환을 설명하기 위해.

나는 a 상태 머신 라이브러리, 주요 개념은 실제로 상태 전환 테이블을 직접 구현할 수 있다는 것입니다. 정말 깔끔한 운동이었습니다. 그래도 얼마나 잘 진행 될지 확실하지 않습니다 ...

Answer 14

유한 상태 기계는 모든 자연어로 형태 학적 구문 분석에 사용될 수 있습니다.

이론적으로 이것은 형태와 구문이 계산 수준으로 나뉘어져 있고, 하나는 대부분의 유한 상태이며, 다른 하나는 가장 약간 온화한 맥락에 민감하다는 것을 의미합니다 (따라서 다른 이론적 모델이 다른 이론적 모델이 필요하지 않습니다. 형태소 대 분열 관계).

이것은 기계 번역 및 단어 광택 영역에서 유용 할 수 있습니다. 표면적으로, 그들은 구문 또는 의존성 구문 분석과 같은 NLP에서 덜 사소한 기계 학습 애플리케이션을 위해 추출 할 수있는 저렴한 기능입니다.

더 배우고 싶다면 체크 아웃 할 수 있습니다. 유한 상태의 형태 Beesley와 Karttunen, Xerox 유한 상태 툴킷은 PARC에서 설계했습니다.

Answer 15

현재 진행중인 현재 시스템의 예제가 있습니다. 저는 주식 거래 시스템을 구축하는 중입니다. 주문 상태를 추적하는 프로세스는 복잡 할 수 있지만 주문 수명주기에 대한 상태 다이어그램을 구축하면 기존 주문에 새로운 트랜잭션을 적용하는 것이 훨씬 간단합니다. 현재 상태에서 새로운 거래가 20 가지 중 하나가 아닌 세 가지 중 하나 일 수 있다는 것을 알고 있다면 해당 거래를 적용하는 데 필요한 비교가 필요합니다. 코드를 훨씬 더 효율적으로 만듭니다.

Answer 16

State driven code is a good way to implement certain types of logic (parsers being an example). It can be done in several ways, for example:

• State driving which bit of code is actually being executed at a given point (i.e. the state is implicit in the piece of code you are writing). Recursive descent parsers are a good example of this type of code.

• State driving what to do in a conditional such as a switch statement.

• Explicit state machines such as those generated by parser generating tools such as Lex and Yacc.

Not all state driven code is used for parsing. A general state machine generator is smc. It inhales a definition of a state machine (in its language) and it will spit out code for the state machine in a variety of languages.

Answer 17

좋은 대답. 여기 내 2 센트가 있습니다. 유한 상태 머신은 테이블과 같은 여러 가지 다른 방식으로 구현할 수있는 이론적 아이디어입니다. 공포). 모든 FSM이 정규 표현에 해당하고 그 반대도 마찬가지입니다. 정규 표현식은 구조화 된 프로그램에 해당하기 때문에 때때로 FSM을 구현하기 위해 구조화 된 프로그램을 작성하십시오. 예를 들어, 숫자의 간단한 구문 분석기는 다음과 같은 선을 따라 쓸 수 있습니다.

/* implement dd*[.d*] */
if (isdigit(*p)){
    while(isdigit(*p)) p++;
    if (*p=='.'){
        p++;
        while(isdigit(*p)) p++;
    }
    /* got it! */
}

당신은 아이디어를 얻습니다. 그리고 더 빨리 달리는 방법이 있다면 그것이 무엇인지 모르겠습니다.

Answer 18

일반적인 사용 사례는 신호등입니다.

구현 참고 : Java 5의 열거는 추상적 인 방법을 가질 수 있으며, 이는 상태 의존적 행동을 캡슐화하는 훌륭한 방법입니다.