오토마타 이론, 유한 오토마타
다양한 기계의 구조, 설계, 작동 원리는 주로 기능적 목적에 따라 결정됩니다. 기술, 운송, 컴퓨팅, 군사 및 기타 기계를 구별하십시오. 복잡한 기술 프로세스를 수행하도록 설계된 전체 자동 단지는 다양한 산업에 널리 도입됩니다. Automata는 다양한 논리적 기능(논리적 기계)을 수행하도록 설계 및 제작되었습니다.
오토마타 이론 — 사이버네틱스 섹션, 디지털 컴퓨터 및 제어 기계 기술 요구 사항의 영향으로 발생했습니다. 오토마타 이론에서 연구되는 이산 오토마타는 이산 시간 단계에서 이산(디지털) 정보를 처리하는 실제 시스템(기술 및 생물학적 모두)의 추상 모델입니다.
오토마타 이론은 오토마타의 기능(행동)과 그 구조(내부 구조)에 대한 직관적인 아이디어를 공식화하는 정밀한 수학적 개념을 기반으로 합니다.
이 경우 정보 변환이란 항상 입력 알파벳의 문자로 구성된 입력 시퀀스를 출력 알파벳의 문자로 구성된 출력 시퀀스로 변환하는 작업으로 이해됩니다.
수학 논리, 대수학, 확률 이론, 조합론 및 그래프 이론의 장치가 널리 사용됩니다.
일부 부분에서 오토마타 이론의 문제(오토마타의 구조 이론)가 커졌습니다. 릴레이 접점 회로 이론에서, 1930 년대 후반에 형태를 갖추기 시작했습니다. 포함한 논리적 대수학의 방법.
오토마타의 구조 이론에서는 시스템에 적절하게 연결된 단순한 구성 요소(요소)로부터 복잡한 오토마타가 어떻게 생성되는지 설명하기 위해 고안된 다양한 유형의 체계를 연구합니다.
오토마타의 추상 이론이라고 하는 또 다른 방향은 오토마타의 동작(즉, 오토마타가 수행하는 정보 변환의 특성)을 연구하면서 내부 구조의 특성을 추상화하고 1950년대에 발생했습니다.
오토마타의 추상 이론의 틀 내에서 "자동 장치" 및 "기계" 개념의 내용은 본질적으로 자동 장치에 의해 수행되는 정보 변환에 대한 표준 설명에 의해 소진됩니다. 이러한 변환은 결정론적일 수 있지만 본질적으로 확률론적일 수도 있습니다.
가장 많이 연구된 것은 결정론적 기계(오토마타)이며, 여기에는 오토마타 이론의 주요 연구 대상인 유한 오토마타가 포함됩니다.
유한 상태 기계는 제한된 양의 메모리(내부 상태 수)가 특징이며 전이 함수를 사용하여 정의됩니다.일부 합리적인 이상화를 통해 모든 현대 수학 기계와 뇌까지도 기능의 관점에서 유한 자동 장치로 간주할 수 있습니다.
"순차 기계", "밀리 오토마톤", "무어 오토마톤"이라는 용어는 문헌에서 "유한 오토마톤"이라는 용어의 동의어로 사용되거나 유한 기계의 전이 기능에서 특정 기능을 강조하기 위해 사용됩니다(모든 저자가 균일하지는 않음). 자동 장치.
무제한 메모리가 있는 Automata는 (잠재적으로) 효율적인 정보 변환을 수행할 수 있는 Turing 기계입니다. "튜링 기계"의 개념은 "유한 상태 기계"의 개념보다 먼저 등장했으며 주로 알고리즘 이론에서 연구됩니다.
추상 오토마타 이론은 잘 알려진 대수 이론, 예를 들어 반군 이론과 밀접한 관련이 있습니다. 적용된 관점에서, 메모리 크기 측면에서 자동화 장치의 정보 변환을 특징짓는 결과가 흥미롭습니다.
예를 들어, 오토마타에 대한 실험 문제(E.F. Moore 등의 작업)에서 오토마타의 전이 기능 또는 메모리 용량에 대한 하나 또는 다른 정보가 결과에서 얻어지는 경우입니다. 실험.
또 다른 작업은 오토마톤의 메모리 크기와 입력 시퀀스의 기간에 대한 사용 가능한 정보를 기반으로 출력 시퀀스의 기간을 계산하는 것입니다.
매우 중요한 것은 유한 상태 기계의 메모리를 최소화하고 무작위 환경에서 동작을 연구하는 방법을 개발하는 것입니다.
추상 오토마타 이론에서 종합 문제는 다음과 같다.명확하게 형식화된 일부 언어의 관점에서 조건은 설계된 자동 장치의 동작(자동 장치에 표시된 이벤트에 대해)에 대해 작성됩니다. 이 경우 각 서면 조건에 따라 다음과 같은 방법을 개발할 필요가 있습니다.
1) 상태 기계에 의해 변환된 정보가 이 조건을 충족하는 상태 기계가 존재하는지 확인하십시오.
2) 그렇다면 유한 상태 기계의 전이 기능이 구성되거나 메모리 크기가 추정됩니다.
이러한 공식에서 합성 작업의 솔루션은 기록에서 전이 기능으로 전환하기 위한 편리한 알고리즘을 사용하여 자동 장치의 작동 조건을 기록하기 위한 편리한 언어의 예비 생성을 전제로 합니다.
오토마타의 구조 이론에서 합성 문제는 전이 함수에 의해 주어진 유한한 오토마타를 실현하는 주어진 유형의 요소 체인을 구성하는 것으로 구성됩니다. 이 경우 일반적으로 최적 기준(예: 요소의 최소 수)을 지정하고 최적 체계를 얻으려고 합니다.
나중에 밝혀졌듯이 이는 릴레이 접점 회로와 관련하여 이전에 개발된 일부 방법 및 개념이 다른 유형의 회로에도 적용 가능함을 의미합니다.
전자 기술의 발전과 관련하여 가장 널리 퍼진 계획은 다음과 같습니다. 기능적 요소의 (논리 네트워크). 논리 네트워크의 특수한 경우는 요소를 뉴런이라고 하는 추상 신경망입니다.
회로 유형 및 의도된 정보 변환(릴레이 장치의 합성)에 따라 많은 합성 방법이 개발되었습니다.
바라보다 -조합 회로, 카르노 맵, 회로 합성 최소화
유한 상태 기계 - 고정된(작동 중 증가할 수 없는) 메모리 크기를 가진 제어 시스템의 수학적 모델.
유한 상태 기계의 개념은 일련의 제어 시스템(예: 다중 루프 릴레이 장치)의 일반적인 특성을 특징짓는 수학적 추상화입니다. 이러한 모든 시스템에는 유한한 자동 장치의 정의로 자연스럽게 받아들일 수 있는 공통 기능이 있습니다.
완성된 모든 자동 장치에는 외부 영향과 내부 요소에 노출된 입구가 있습니다. 입력 요소와 내부 요소 모두에 대해 취할 수 있는 고정된 수의 불연속 상태가 있습니다.
입력 요소와 내부 요소의 상태 변화는 불연속적인 순간에 발생하며, 그 사이의 간격을 틱이라고 합니다. 테이프 끝의 내부 상태(internals의 상태)는 전적으로 내부 상태와 테이프 시작 부분의 입력 상태에 의해 결정됩니다.
유한 오토마톤의 다른 모든 정의, 특히 유한 오토마톤이 주어진 시간에 오토마톤의 내부 상태에 따라 달라지는 출력을 가지고 있다고 가정하는 정의에서 이 특성으로 축소될 수 있습니다.
이러한 특성의 측면에서 입력 및 내부 상태의 특성은 완전한 자동 장치의 설명과 관련이 없습니다. 입력 및 상태 대신 임의의 번호 매기기에서 번호를 볼 수 있습니다.
이전 내부 상태 번호 및 이전 입력 상태 번호에 대한 내부 상태 번호의 종속성이 지정된 경우 상태 머신이 설정됩니다. 이러한 작업은 최종 테이블의 형태일 수 있습니다.
완전한 자동화를 정의하는 또 다른 일반적인 방법은 소위 전환 다이어그램. 입력 상태는 종종 단순히 입력이라고 하며 내부 상태는 단순히 상태입니다.
유한 상태 기계는 기술 장치와 일부 생물학적 시스템의 모델이 될 수 있습니다. 첫 번째 유형의 Automata는 예를 들어 릴레이 장치 및 다양한 전자 컴퓨터입니다. 프로그래머블 로직 컨트롤러.
릴레이 장치의 경우 입력 상태의 역할은 릴레이 장치의 민감한 요소 상태의 조합에 의해 수행됩니다(이러한 상태의 각 조합은 «복잡한 상태»이며 모든 민감한 요소의 표시를 특징으로 합니다. 주어진 순간에 가지고 있는 이산 상태). 마찬가지로 릴레이 장치의 중간 요소 상태 조합은 내부 상태로 작동합니다.
프로그래밍 가능한 논리 컨트롤러(PLC)는 독립형 상태 기계라고 할 수 있는 릴레이 동작 장치의 예입니다.
실제로 프로그램이 PLC에 입력되고 컨트롤러가 계산을 시작하면 외부 영향에 노출되지 않으며 각 후속 상태는 이전 상태에 의해 완전히 결정됩니다. 입력이 모든 클록 주기에서 동일한 상태를 갖는다고 가정할 수 있습니다.
반대로 가능한 유일한 입력 상태를 가진 모든 유한 상태 기계는 당연히 자율적이라고 합니다. 이 경우 외부 환경은 동작을 제어하는 정보를 전달하지 않기 때문입니다.
또한보십시오: