logo

오토마타 이론

오토마타 이론은 컴퓨터 과학 및 수학의 이론적 분야입니다. 추상기계에 대한 연구와 이러한 기계를 이용하여 해결할 수 있는 계산문제를 연구하는 것이다. 추상기계를 오토마타(automata)라고 부른다. 오토마타 이론 개발의 주요 동기는 개별 시스템의 동적 동작을 설명하고 분석하는 방법을 개발하는 것이었습니다.

이 자동화 장치는 상태와 전환으로 구성됩니다. 그만큼 상태 로 표현된다 서클 , 그리고 전환 로 표현된다 화살 .

오토마타(Automata)는 어떤 문자열을 입력으로 받아들이고 이 입력은 유한한 수의 상태를 거쳐 최종 상태에 들어갈 수 있는 일종의 기계입니다.

오토마타에서 중요하고 자주 사용되는 기본 용어는 다음과 같습니다.

기호:

기호는 문자, 알파벳 또는 그림이 될 수 있는 엔터티 또는 개별 개체입니다.

예:

1, 가, 비, #

알파벳:

알파벳은 유한한 기호 집합입니다. ∑로 표시됩니다.

예:

 ∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} 

끈:

그것은 알파벳의 유한한 기호 모음입니다. 문자열은 w로 표시됩니다.

예시 1:

∑ = {a, b}이면 ∑에서 생성할 수 있는 다양한 문자열은 {ab, aa, aaa, bb, bbb, ba, aba.....}입니다.

  • 기호가 전혀 나오지 않는 문자열을 빈 문자열이라고 합니다. ε으로 표현됩니다.
  • 문자열 w에 포함된 기호의 수를 문자열 길이라고 합니다. |w|로 표시됩니다.

예 2:

 w = 010 Number of Sting |w| = 3 

언어:

언어는 적절한 문자열의 모음입니다. Σ를 통해 형성된 언어는 다음과 같습니다. 한정된 또는 무한 .

예: 1

 L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> 

예: 2

 L2 = {Set of all strings starts with &apos;a&apos;} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>