의사 결정 트리를 오토 마톤으로 변환하는 방법은 무엇입니까?

Question

내가 아는 것에서,

• 문제는 예 / 아니오 답변으로 변형 될 수 있습니다. 의사 결정 트리에 의해 기술되어있다.
• 문제에 대한 해결책은 일련의 문자열 (언어)으로 표현 될 수 있습니다. 즉, 문제가 회원 문제로 간주 될 수 있음을 의미합니다.
• 이 문자열 세트는 할 수 있습니다 또한 오토 마톤으로 표현됩니다. 내 마음 속에 모호하다.

내 질문은 다음과 같습니다.

1. 의사 결정 트리와 오토 마톤 간의 관계는 무엇입니까?

2. 의사 결정 트리를 오토 톤으로 변환하는 방법은 무엇입니까?

나는 이것과 관련된 약간의 기사를 읽으려고 노력하고 있으며,이 개념들은 서로 관련되어 있지만, 나는 서로를 이해하지 못한다고 느낍니다.

Answer 1

의사 결정 트리는 일정 크기의 인스턴스에 대해 의미가있는 계산 모델입니다. 대조적으로 언어는 일반적으로 무한한 크기의 인스턴스 모음입니다. 이 컨텍스트에서 오토 톤 (이 컨텍스트)은 언어를 설명하는 계산 모델입니다.

모든이 모든 것이 대부분의 상황에서 의사 결정 트리를 오토 마톤으로 변환하는 것이 정말로 의미가 없습니다.

다음은 몇 가지 예입니다.

• 사람이 나이, 성별, 높이 및 무게를 감안할 때 과체중인지 여부를 결정합니다. 이것은 의사 결정 트리 또는 테이블로 해결할 수 있습니다.
• 64x64 이미지가 개 또는 고양이를 묘사하는지 여부를 결정합니다. 이것은 또한 의사 결정 트리에 의해 해결 될 수 있지만 권장되지는 않습니다.
• 주어진 정수가 프라임인지 여부를 결정합니다. 이 결정 문제는 프레임의 언어 인 언어를 정의합니다. Agrawal, Kayal 및 Saxena는 2002 년 에이 문제를 해결하기위한 효율적인 절차를 주었는데, 이는 계산 수업 이론 (DFA, NFA, PDA) 이론적으로 고려 된 자동차 종류에 의해 구현 될 수 없습니다.
• 주어진 문자열이 palindrome인지 여부를 결정합니다. 이 결정 문제는 언어를 정의하며 푸시 다운 오토 톤으로 해결할 수 있지만 DFA / NFA가 아닙니다.