비 결정적 유한 변환기를 어떻게 시뮬레이트 할 수 있습니까?

Question

비 결정적 오토 마톤은 오토 마톤이있는 상태와 입력 스트링이 얼마나 멀리 있는지를 추적하여 입력 문자열에서 쉽게 시뮬레이션 할 수 있습니다. 그러나 비 결정적 변환기 (변환기는 물론 입력 기호를 출력 기호로 변환하고 부울 값이 아닌 문자열을 출력으로 제공 할 수 있습니다)를 시뮬레이션 할 수 있습니까? 비대칭 성 때문에 수 많은 출력 문자열을 어떻게 든 추적해야하기 때문에 더 복잡합니다.

Answer 1

기본적으로 NFA와 동일하지만 true 또는 false를 반환하는 대신 출력 세트에 출력을 추가합니다. 다음은 약간의 의사 코드입니다.

function rec(in, current_state, pos, out) 
if(current_state.isFinal && pos == in.length) out_set += out 

for(t <- lambda transition going out from current_state) 
    rec(in, t.destination, pos, out + t.output_symbol) 

for(t <- transition going out from current_state for symbol in(pos) 
    rec(in, t.destination, pos+1, out + t.output_symbol) 

Answer 2

우선, 일부 이론입니다. 다음은 별개의 대수 구조 :

• 발전기 (전환 시스템)

• 수용체 (자동 장치)

• 트랜스 듀서 (기계)

는 괄호 용어는 매우 일반적이다 문학에서 발견 된 것처럼, 아쉽게도 잘못 사용되는 경우가 많습니다. 이 대수적 구조는 서로 닮아있다. 많은 작은 변화를 통해 하나 또는 다른 것 또는 하이브리드로 전환 될 수있다. 그러나 그들은 근본적으로 다른 아칸소 사실로부터 방해하지 않아야

• 발전기 언어의 건설 표현, 즉 (유한 또는 무한) 단어의 집합이다. 당신은 비 결정 론적으로 생성자를 가로 지르고 그렇게함으로써 당신은 그 언어로 모든 단어를 생성합니다.

• 억 셉터는 다시 단어 세트 (언어)를 정의하기위한 구성이지만 각 가능한 단어 (유한 또는 무한)에 대한 표시 기능을 나타냅니다. 따라서 각 단어를 부울 값으로 매핑합니다 (트랜스 듀서와 비교하기 위해 유한 또는 무한 출력 단어로 적절히 확장 될 수 있음 - 구별되는 차이점 있음).

• 트랜스 듀서는 각각 허용 가능한 유한 입력 단어를에 매핑하는 기능을 나타냅니다 (). 셉터 관계없이 길이의 모든 유한 한 단어를 수락하거나 할 수 없기 때문에 제한된 언어의 맥락에서

이 수용체와 센서 사이의 차이는 덜 현저하게되고, 따라서, 각각의 워드에 대한 출력 워드를 생성 . 억 셉터로부터의 부울 출력의 연결에 의해, 각각의 유한 입력 단어에 대해 (즉, 주어진 입력 단어의 각 접두사로부터의 출력을 연결시킴으로써) 유한 출력 단어를 생성 할 수있다. 두 가지 개념을 연결하려는 시도는 기계적으로는 맞지만 그럼에도 불구하고 관련된 개념을 왜곡시킨다.

무한 언어로 된 문맥에서 구별이 명확합니다. infinite-word automaton은은 주어진 (무한) 입력 단어의 유한 접두어에 대한 출력을 생성 할 수 없습니다. 이 제한은 전체 (무한한) 단어에 대해 무한 단어 수락이 정의 된 결과입니다.결과적으로 수용자는 각 입력 단어를 부울 값에 매핑하거나 그러한 관점이 선호되는 경우 출력 단어를 매핑합니다. 반대로 변환기 (기계)는 입력 단어의 각 유한 접두어를 동일한 길이의 유한 출력 단어에 매핑합니다. 이러한 이유 때문에 그들은 기계라고 부릅니다. 왜냐하면 단계별로 반응하기 때문입니다.

• Mealy machines
• Moore machines

무어 기계가 반점이 기계에 의해 표현 될 수있다 : 트랜스 듀서의 두 가지 종류가

있습니다. 모든 Mealy 기계가 Moore 기계로 표현할 수있는 것은 아닙니다. 이 두 가지 유형의 트랜스 듀서를 정의하고 비교하는 데에는 일반적으로 잘못된 문법이 있습니다. 정확한 정의에 대해서는 원래의 출판물을 참조하십시오.

두 정의 모두 결정적입니다. 결정론에 대한 제한이있는 이유는 변환기가 시스템을 제어하는 ​​데 사용되므로 적용 할 다음 제어 작업을 결정적으로 파악해야합니다. 이로 인해 결정 론적 변환기가 문헌에서 표준이되었습니다.

그러나, 비 결정적 변환기는 또한, 예를 들어 다중 전략의 소형 표현으로 유용 할 수있다. 그러나 실행될 때 단일 경로를 따라 가면서 동시에 여러 개가 아닌 단일 출력 단어를 생성하는 것이 타당합니다 (실행 중에 생성 된 비 결정적 인수 자의 경우와 동일).

따라서 트랜스 듀서의 비 결정적 시뮬레이션은 의도 한 용도와 일치하지 않습니다. 이것은 대안 전략의 집합을 나타냅니다 (하나의 고정 된 방식으로 결정할 때마다 혼합 될 수도 있습니다).

그래서 실제로 빠르게 폭발 할 수있는 가능한 출력 단어의 트리를 만들어야합니다. 이 트리는 본질적으로 입력 주석의 변환기를 제거하여 얻을 수있는 생성기 (전환 시스템)의 전개입니다.