포스트 캐논 시스템

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 보다 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2021년 4월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

에밀 포스트가 만든 포스트 프로덕션 시스템이라고도 하는 포스트 캐논 시스템(Post 표준 시스템)은 많은 문자열로 시작하여 일정한 형태의 특정 규칙의 유한 집합 j를 적용하여 반복적으로 변형하여 형식적인 언어를 생성하는 스트링 매니페레이션 시스템이다. 오늘날 그것들은 주로 역사적 관련성이 있다. 왜냐하면 모든 포스트 캐논 시스템은 보다 단순한 형식인 문자열 재작성 시스템(semi-Thue 시스템)으로 축소될 수 있기 때문이다. 두 형식 모두 튜링완료다.

정의

포스트 표준 시스템은 트리플트(A, I, R)로, 여기서

• A는 유한한 알파벳이며, A의 유한한(아마도 비어 있을 것 같은) 문자열을 단어라고 한다.
• 나는 한정된 초기 단어 집합이다.
• R은 문자열 변환 규칙(생산 규칙이라 함)의 유한 집합이며, 각 규칙은 다음과 같은 형식을 가진다.