(프로그래밍) 언어 수락 자로 유한 상태 오토 마톤

Question

FSA가 'nice'문자열을 허용하는 방법을 알고 있지만 (FSA가 허용하는 언어는 프로그래밍 언어 일 수 있습니까?

이 같은가요?; 내가 알파벳 A = {1,2, +, -} 및 언어 L = {1 + 1,1 + 2,1-1,1-2}라고 말하면 내 FSA는 이렇게 보입니다.

-->[1]--1-->[2]--+-->[3]--1-->[[5]] 
      |  | 
      -  2-->[[6]] 
      | 
      v 
      [4]--1-->[[7]] 
      | 
      2-->[[8]] 

수용 상태가 5, 6, 7, 8에 도달하면 가치가 있어야하며 따라서 프로그래밍 언어를 정의 했습니까?

그리고 중첩 된 FSA를 포함하도록 확장하면 '1plus2'및 'sqrt (9)'와 같은 문자열을 계산할 수 있습니다.

이 생각이 맞습니까?

Answer 1

아니요, 그렇지 않습니다. FSA가 계산과 어떻게 관련되어 있는지 이해하려면 더 일반적인 계산보기를 채택해야합니다.

일반적으로 계산은 입력을 받아 출력을 생성하는 것입니다. 지금은 답을 계산할 수있는 문제 중 하나에 초점을 맞추어 보겠습니다. 결과가 "예"또는 "아니오"로 제한되는 의사 결정 문제. 입력이 문자열 인 의사 결정 문제 ("nice"와 같은)에 대해 우리가 말하는 문제의 종류를 더 제한하자. 이것은 정확하게 FSA가 대답하는 데 사용할 수있는 종류의 질문입니다 (그러나 모든 질문에 대답 할 수는 없습니다!).

그래서 FSA는 다음 형식의 질문에 대답 할 수 있습니다. 문자열 X가 속성 Y를 갖고 있습니까? 이것의 예는 "문자열이 알려진 유한 문자열 집합 중 하나입니까?", "문자열이 홀수의 이진 표현입니까?", "문자열에 'cat'이 하위 문자열로 있습니까?" 이것들은 모두 FSA가 대답 할 수 있습니다.

1 + 1과 같이 문제는 결정에 문제가 아닙니다. "x + y = z 형식의 문자열입니다. 여기서 x, y 및 z는 정수 X, Y 및 Z와 X + Y = Z의 10 진수 표현입니다. ? " 이 질문은 FSA를 사용하여 대답 할 수 없습니다.

더 강력한 종류의 상태 시스템이 존재합니다. 그들은 "유한"하지 않습니다. 예로는 푸시 다운 오토 마톤 (PDA), 선형 경계 오토 마타 (LBA) 및 튜링 기계 (TM)가 있습니다. "문자열 X는 속성 Y를 가집니까?"라는 형식의 결정 문제가 있습니다. 가장 강력하게 알려진 종류의 오토 마타 인 튜링 기계조차도 대답을 할 수 없습니다. "x '(y)'여기서 x는 프로그램이고 y는 프로그램에 대한 입력이고, X로 표시된 프로그램은 입력을 전달할 때 멈 춥니 다." 일반적인 경우에는이 질문에 답하기 위해 TM이 없다. 즉 알고리즘이 없다.

"문자열 x는 내가 정의한이 언어로 구문 상 유효한 문자열입니까?"라는 질문에 대답하는 FSA를 작성할 수 있습니까? 자연스럽게, 그것은 당신 언어의 규칙에 달려 있습니다. "Number + Number + ... + Number"형식의 문자열은 FSA에서 인식 할 수 있지만 FSA는 그 합이 무엇인지 말할 수 없습니다. 그러나 여기에 괄호를 추가 할 수 없거나 FSA가 더 이상 적합하지 않습니다. 다시 말해 문자열 인식과 컴퓨팅 결과의 차이는 FSA가 일반적으로 이전의 작업을 수행하는 것으로 간주됩니다.

추가 질문이 있으시면 언제든지 문의하십시오. 질문이 이러한 종류의에 관심이 있다면, 다음 사이트를 방문 투입하여 새로운 컴퓨터 과학 StackExchange에 대한 지원을 보여주십시오 :

http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=rpnXA1_2BNYzXN85c5ibxQ2