본문 바로가기
카테고리 없음

[계산이론] Finite Automata - 1

7_JUN_7 2023. 10. 17. 16:48

Automata

자동기 (an Automaton)

  • 자동기는 디지털 컴퓨터의 추상 모델(abstract model)이다.
  • 복잡한 계산 문제를 해결하기 위한 기본적인 구조와 원칙을 이해하는 데 도움을 주는 수학적 도구로 사용된다.
  • Automata 는 Automaton의 복수형

모든 Automaton은 핵심 특징들(essential features)을 포함한다 :

  • 입력 읽기(Reading input)
    • 자동기는 알파벳 위의 문자열(a string over alphabet)을 입력으로 읽을 수 있다.
    • 자동기가 이 입력을 읽을 수는 있지만 변경(change)할 수는 없다.
  • 출력 생성(Producing output)
    • 자동기는 주어진 입력에 따라 출력을 생성한다.
  •  임시 저장소( Containing a temporal storage )
    • 자동기는 현재의 상태나 다음에 수행할 작업을 기억하기 위한 일종의 저장소를 가지고 있다.
    • 이 저장소는 자동기의 현재 상태를 나타내는 데 사용된다.
  • 제어 유닛( Containing a control unit )
    • 자동기에는 제어 유닛이 포함되어 있다.
    • 이 제어 유닛은 유한한 수의 내부 상태(with a finite number of internal states) 를 가지며, 입력에 따라 어떤 상태로 전환될지를 결정한다.

요약하면, 자동기는 복잡한 계산 문제를 모델링하고 해결하는 데 사용되는 수학적 도구이다. 주어진 입력에 따라 어떤 출력을 생성할지, 어떤 상태로 전환될지를 결정하는 규칙을 가지고 있다.

 

an Automaton 구조도

 

Finite Automata

유한 자동기 (Finite Automata)

  • 가장 간단한 모델(simplest model)로, 유한 자동기 또는 유한 상태 기계(finite state machines)라고도 한다.
  • 내부에 유한한 상태 집합(a finite set in internal states)을 가지며, 다른 메모리는 포함하지 않는다. (with no other memory)
  • 유한 자동기는 다양한 분야에서 사용될 수 있다.
    • 보안(Security)
    • 컴파일러(Compiler)
    • 네트워크 프로토콜(network protocol)
    • etc.
  • 예시) 자동문 컨트롤러 ( a controller for automatic door )

  • 만약 사람이 문 앞(Front)에 있다면, 문은 열려야 한다.
  • 문은 사람이 완전히 지나갈 수 있을 만큼 충분한 시간 동안 열려 있어야 한다.
  • 문은 그 뒤에 서있는 사람을 치지 않아야 한다! (Rear)
  • 상태 전이표 ( State transition table)

상태전이표

상태 전이 표는 자동문의 현재 상태와 주변 환경(사람의 위치)에 따라 다음 상태로 전이되는 방식을 나타낸다.

  • NEITHER: 문 주변에 아무도 없을 때
  • FRONT: 문 앞에 사람이 있을 때
  • REAR: 문 뒤에 사람이 있을 때
  • BOTH: 문 앞과 뒤 양쪽에 사람이 있을 때

예를 들어, 문이 현재 닫힌 상태(CLOSED)이고 사람이 문 앞(FRONT)에 있다면, 문은 열린 상태(OPEN)로 전이된다. 또한, 문이 이미 열린 상태(OPEN)이고 사람이 문 뒤(REAR)에 있다면, 문은 계속 열린 상태로 유지된다.

  • State transition graph

상태 전이 그래프는 시스템의 각 상태와 그 상태들 사이의 전이를 시각적으로 나타내는 그래프이다. 자동문 컨트롤러의 경우, 문의 상태와 주변 환경(사람의 위치)에 따라 문의 상태가 어떻게 변화하는지를 그래프로 표현한다.

상태 전이 그래프는 다음과 같은 상태와 전이를 포함하고 있다:

  • 상태: CLOSED (문이 닫힌 상태), OPEN (문이 열린 상태)
  • 환경: NEITHER (문 주변에 아무도 없음), FRONT (문 앞에 사람 있음), REAR (문 뒤에 사람 있음), BOTH (문 앞과 뒤에 사람 있음)

그래프는 각 상태에서 시작하여 주어진 환경 조건에 따라 다른 상태로 전이되는 화살표로 구성된다. 예를 들어, 문이 닫힌 상태에서 사람이 문 앞에 있으면 문은 열린 상태로 전이된다.

 

Deterministic Finite Automata (DFA)

결정적 유한 자동기 (DFA)

  • DFA는 유한한 수의 내부 상태를 포함한다. (Containing a finite number of internal states)
    • 시작 상태 (Starting or Initial State): DFA의 작동을 시작하는 상태
    • 최종 상태 (Final or Accepting States): 입력 문자열이 DFA에 의해 수락되는 경우에 도달하는 상태
  • 입력 문자열 처리( Processing an input string ): DFA는 심볼의 연속으로 구성된( consisting of a sequence of symbols ) 입력 문자열을 처리한다.
  • 상태 전이( Making transitions ): 한 상태에서(one state)에서 다른 상태로(another)로 상태를 전이한다.
    • 현재 상태와 입력 심볼에 따라 다른 상태로 전이된다.
  • 출력 생성(Producing output):
    • DFA는 주어진 입력 문자열을 수락(Accept)하거나 거부(Reject)한다.

 

DFA는 주어진 입력에 대해 명확한 하나의 상태로 전이되는 특징을 가지며, 이는 비결정적 유한 자동기(NFA)와는 대조적이다.

 

예시)

  1. 상태: 이 DFA에는 세 개의 상태, q0, q1 및 q2가 있습니다.
  2. 시작 상태: q0는 시작 상태입니다.
  3. 허용 상태: q1는 이 DFA의 허용 상태(또는 종료 상태)이다.
  4. 전이 함수: 화살표로 표시된 transition은 다음과 같다:
    • q0에서 0을 입력하면 유지된다.
    • q0에서 1을 입력하면 q1로 이동한다.
    • q1에서 1을 입력하면 q2로 이동한다.
    • q1에서 0을 입력하면 q0로 이동한다.
    • q2에서 0을 입력하면 유지된다.
    • q2에서 1을 입력하면 q2로 이동한다.

여기서 Input string: 01101 이라고 가정하자.

시작 상태 q0에서 시작하여 종료상태 q2에서 마무리 되기 때문에 이 input은 accept 된다

 

DFA의 정의

  • DFA는 5-튜플(5-tuples)로 정의된다
  • 𝑀 = (𝑄, Σ, 𝛿, 𝑞_0, 𝐹)
    • 𝑄: 내부 상태의 유한 집합(finite set of internal states)이다.
    • Σ: 기호의 유한 집합(finite set of symbols)이다.
    • 𝛿: 𝑄 × Σ → Q 형태를 가지는 전이함수(transition function)이다.
      • 모든 상태는 모든 기호(symbol)에 대한 전이(transition)를 가진다.
    • 𝑞0: 시작 상태(initial state) ,  (𝑞_0 ∈ 𝑄)
    • 𝐹: 최종 상태의 집합(set of final states) , (𝐹 ⊆ 𝑄)
  • 모든 상태는 모든 심볼에 대한 전이를 가져야 합니다.

아까 봤던 Transition Graph에 대한 5 튜플은 다음과 같다.

𝑀 = ({𝑞0, 𝑞1, 𝑞2},{0, 1}, 𝛿, 𝑞0,{𝑞1})

 

𝛿 (𝑞0, 0) = 𝑞0      𝛿 (𝑞0, 1) = 𝑞1      𝛿 (𝑞1, 0) = 𝑞0

𝛿 (𝑞1, 1) = 𝑞2      𝛿 (𝑞2, 0) = 𝑞2      𝛿 (𝑞2, 1) = 𝑞1

 

𝑄 = {q0,q1,q2}

Σ = {0.1}

𝑞_0 = q0

𝐹 = {q1}

 

전이함수 𝛿에 대한 설명은 다음과 같다.

q0에서 0을 입력하면 상태가 유지된다.

q0에서 1을 입력하면 q1으로 전이된다.

q1에서 0을 입력하면 q0으로 전이된다.

q1에서 1을 입력하면 q2으로 전이된다.

q2에서 0을 입력하면 상태가 유지된다.

q2에서 1을 입력하면 q1으로 전이된다.

 

Transition Table

𝑞 0 1
→ 𝑞0 𝑞0 𝑞1
∗ 𝑞1 𝑞0 𝑞2
𝑞2 𝑞2 𝑞1

 

표의 각 열과 행은 다음을 나타낸다.

  • 첫 번째 열(q): 현재 상태를 나타낸다.
  • 두 번째 열(0): 입력 0에 대한 다음 상태를 나타낸다.
  • 세 번째 열(1): 입력 1에 대한 다음 상태를 나타낸다
  • → 기호는 q0이 시작 상태임을 나타낸다.
  • * 기호는 q1이 허용 상태(또는 종료 상태)임을 나타낸다.

 

Trap State

Transition grap의 Trap State

  • 트랩 상태는 전이 그래프(transition graph) 내에서 특별한 상태로, 일단 이 상태에 도달하면 다른 어떤 상태로도 전이되지 않는다.
  • 이는 주로 입력 문자열이 자동기의 규칙에 맞지 않을 때 사용되어, 해당 문자열을 거부(Reject)하는 데 사용된다.
  • 위 transition graph를 살펴보면 q2에서 0 또는 1을 둘다 입력하더라도 상태가 유지된다. 즉 어떤 입력을 하더라도 다른 상태로 전이되지 않는다.

확장 전이 함수 (Extended Transition Function)

  • 확장 전이 함수는 다음과 같이 정의된다
    • 𝛿* : 𝑄 × Σ* → 𝑄
  • 확장 전이 함수는 여러 전이 함수의 연결(Connection of multiple transition functions)을 나타낸다.
  • 𝛿 * (𝑞, 𝑤𝑎) = 𝛿(𝛿 * (𝑞, 𝑤), 𝑎)
    • 이 식은 현재 상태 𝑞와 입력 문자열 𝑤의 마지막 심볼 𝑎에 대한 확장 전이 함수의 결과를 나타낸다. 여기서 𝑤는 입력 문자열의 나머지 부분을 나타낸다.
  • 예제
  •  
     
    • 𝛿(𝑞0, 1) = 𝑞1 , 𝛿(𝑞1, 1) = 𝑞2 이다.
    • 그렇다면, 𝛿 * (𝑞0, 11) = 𝑞2 이다.
    • 𝛿 * (𝑞0, 100) = q0이다.

예제 문제

  • Σ = {𝑎, 𝑏}에 대한 모든 문자열(string) 집합 중에서 접두사(prefix) 𝑎𝑏로 시작하는 문자열을 인식(recognize)하는 DFA를 찾아라.
    • 수락되는 문자열 (Accepted): ab, abb, ababa, abbaaa, abaaa
    • 거부되는 문자열 (Rejected): aab, ba, bbba, baabaaa, aabbb

시작 상태 q0으로 시작한다.

수락되는 문자열을 살펴봤을 때

q0 에서 a 입력을 넣으면 q1 상태가 되고 q1에서 b입력을 넣으면 q2로 전이된다.

ab 의 입력을 받은 다음 어떤 입력을 받더라도 accept한 상태가 된다. 즉 종료상태 q2에서는 어떤 입력을 받더라도 상태가 유지된다.

거부되는 문자열을 살펴봤을 때

ab로 시작되지 않는 입력은 전부 종료상태에서 마무리되지 않는다. 그렇기 위해서는 새로운 상태 q3가 필요하다.

q0에서 b로 시작되는 입력을 넣는 경우 q3의 상태로 전이된다.

q0에서 a로 입력을 시작하여 q1으로 넘어가더라도 q1의 상태에서 b가 아닌 a를 입력하면 q3상태로 전이된다.

q3에서는 어떤 입력을 받더라도 q3의 상태를 유지한다.

 

실습 문제

주어진 이진 문자열( 즉,Σ = {0, 1} )의 비트 합이 3의 배수인 경우에만 문자열을 수락하는 결정적 유한 자동기 (DFA)를 설계하는 것이다.

 

  1. 상태 정의:
    • 각 상태는 이진 문자열의 비트 합을 3으로 나눈 나머지를 나타낸다. 따라서 3개의 상태가 필요하다: q0 (나머지가 0), q1 (나머지가 1), q2 (나머지가 2)
  2. 시작 상태 및 수락 상태 정의:
    • 시작 상태는 q0입니다. (비트 합이 0인 경우)
    • 수락 상태는 q0입니다. (비트 합이 3의 배수인 경우)

이렇게 설계된 DFA는 주어진 예제 문자열을 올바르게 수락하거나 거부한다.

  • 0, 111, 1011, 1001010111 => 수락됨
  • 1, 101, 1111, 1110000001 => 거부됨

언어의 수용 (Acceptance of a language)

  • DFA 𝑀 = (𝑄, Σ, 𝛿, 𝑞0, 𝐹)에 의해 수용되는 언어(Language)
    • =>     𝑀에 의해 수용되는 Σ 상의 모든 문자열의 집합이다.
    • 𝐿(𝑀) = {𝑤 ∈ Σ * : 𝛿 * (𝑞0, 𝑤) ∈ 𝐹} 
      • 𝑤는 Σ * 에 속하는 문자열이다.
      • 𝛿* (𝑞0, 𝑤)는 확장 전이 함수를 사용하여 시작 상태 𝑞0에서 문자열 𝑤를 처리한 결과 상태이다.
      • 𝐹는 수락(종료) 상태의 집합이다.

이 정의에 따라, 𝐿(𝑀)는 DFA 𝑀에 의해 수용되는 모든 문자열의 집합을 나타낸다. 즉, 𝑀이 주어진 입력 문자열 𝑤를 수용(accept)하는 경우, 𝑤는 𝐿(𝑀)에 포함된다.

  • 예제
    • ab, abb, ababa, abbaaa, abaaa, … ∈ 𝐿(𝑀)
    • aab, ba, bbba, baabaaa, aabbb, … ∉ 𝐿(𝑀)
    • 이는 다음과 같이 정의 될 수 있다.

𝐿(𝑀) = {𝑎𝑏𝑤 | 𝑤 ∈ {𝑎, 𝑏} * }

  • 𝑎𝑏𝑤는 'ab' 접두사로 시작하는 문자열을 나타낸다.
  • 𝑤는 {𝑎, 𝑏} * 에 속하는 문자열로, 'a'와 'b'로만 구성된 임의의 문자열을 나타낸다.
  • 𝐿(𝑀)는 'ab'로 시작하는 모든 문자열의 집합을 나타낸다. 이러한 문자열은 DFA 𝑀에 의해 수용(accepted)되며, 'ab'로 시작하지 않는 문자열은 거부(rejected)된다.

티스토리툴바