강의/Theory of Computation

Construct Minimal DFA

studylida 2025. 2. 1. 03:47
  1. 결정적 유한 자동자(DFA)의 정의
    • DFA는 5개의 요소(Q, Σ, δ, q₀, F)로 구성된 수학적 시스템이다:
      • Q (상태 집합): 자동자가 가질 수 있는 모든 상태.
      • Σ (입력 알파벳): 허용되는 입력 기호 집합.
      • δ (전이 함수): 현재 상태와 입력 기호에 따라 다음 상태를 결정.
      • q₀ (초기 상태): 시작 상태.
      • F (수락 상태): 입력을 수락하는 상태 집합.
  2. DFA의 동작 원리
    • 초기 상태(q₀)에서 시작하여, 입력 문자열의 각 기호를 δ에 따라 처리하면서 상태를 전이.
    • 모든 입력을 처리한 후, 최종 상태가 F에 포함되면 문자열을 수락.
  3. 전이 함수의 특징
    • DFA에서 모든 상태(Q)와 모든 입력 심볼(Σ)에 대해 정확히 하나의 전이가 정의되어야 함.
    • 이는 DFA가 결정적임을 보장하며, 모든 입력에 대해 정확히 한 경로만 따름.
  4. 예제
    • DFA를 사용해 이진수 입력 문자열이 짝수 개의 1을 포함하는지 판단:
      • Q = {q₀, q₁}, q₀: 짝수 개의 1, q₁: 홀수 개의 1.
      • Σ = {0, 1}.
      • δ:
        • q₀에서 1을 읽으면 q₁으로 전이.
        • q₁에서 1을 읽으면 q₀으로 전이.
        • 0은 현재 상태 유지.
      • q₀ = 초기 상태, F = {q₀} (수락 상태).
  5. 결정적과 비결정적 차이
    • DFA (결정적): 모든 입력에 대해 전이가 고정.
    • NFA (비결정적): 하나의 입력에 대해 여러 전이가 가능.

DFA는 형식 언어와 자동화기의 기초를 이루는 중요한 모델로, 입력을 체계적으로 처리하여 언어에 속하는지를 판별하는 데 사용됩니다. 이해의 핵심은 상태 전이와 결정적 특성입니다.

  1. DFA(Deterministic Finite Automata)의 언어
    • DFA의 언어는 DFA가 수락하는 문자열들의 집합으로 정의됨.
    • DFA는 초기 상태에서 시작하여 입력 문자열을 읽으며 상태를 전이하고, 최종 상태(수락 상태)에 도달하면 해당 문자열을 수락.
    • 언어의 정의: DFA가 수락하는 모든 문자열의 집합은 해당 DFA의 언어임.
  2. 수학적 정의
    • DFA의 언어는 다음과 같이 정의 가능:
      • L(DFA): DFA가 수락하는 문자열들의 집합.
      • L(DFA) = {w ∈ Σ* | δ(q₀, w) ∈ F}
        • 여기서, q₀는 초기 상태, w는 문자열, F는 수락 상태 집합.
  3. DFA의 상태 전이
    • DFA는 전이 함수(δ)를 사용해 상태를 전이하며 입력 문자열을 처리.
    • 상태 전이는 현재 상태와 입력 심볼에 의해 결정됨.
    • 입력 문자열이 끝날 때 DFA가 수락 상태에 도달하면 문자열을 수락.
  4. Epsilon Closure (ε-클로저)
    • ε-클로저: DFA의 모든 입력 심볼로 구성된 가능한 문자열 조합의 집합.
    • ε-클로저를 통해 DFA가 처리할 수 있는 모든 문자열의 조합을 정의할 수 있음.
  5. 예제 설명
    • DFA 구성:
      • 상태: Q = {q₀, q₁, q₂}
      • 입력 알파벳: Σ = {0, 1}
      • 초기 상태: q₀
      • 수락 상태: q₂
    • 전이 함수:
      • q₀에서 0을 읽으면 q₀로 이동.
      • q₀에서 1을 읽으면 q₁로 이동.
      • q₁에서 0을 읽으면 q₁로 이동.
      • q₁에서 1을 읽으면 q₂로 이동.
      • q₂에서 0을 읽으면 q₁로 이동.
      • q₂에서 1을 읽으면 q₂로 이동.
  6. 문자열 처리 예제
    • 문자열 101:
      1. q₀에서 시작, 1을 읽고 q₁로 이동.
      2. q₁에서 0을 읽고 q₁에 머무름.
      3. q₁에서 1을 읽고 q₂로 이동.
      4. 문자열이 끝났고 q₂는 수락 상태 → 101은 DFA에 의해 수락됨.
    • 문자열 1010:
      1. q₀에서 시작, 1을 읽고 q₁로 이동.
      2. q₁에서 0을 읽고 q₁에 머무름.
      3. q₁에서 1을 읽고 q₂로 이동.
      4. q₂에서 0을 읽고 q₁로 이동.
      5. 문자열이 끝났고 q₁은 수락 상태가 아님 → 1010은 DFA에 의해 거부됨.
  7. DFA 언어 소속 여부 판별
    • 문자열이 DFA의 초기 상태에서 수락 상태로 도달한다면 해당 문자열은 DFA 언어에 속함.
    • 문자열 처리 중 수락 상태에 도달하지 못하면 해당 문자열은 DFA 언어에 속하지 않음.
  1. 문제 정의
    • DFA(Deterministic Finite Automata)를 구성하는 두 가지 문제를 다룸:
      1. 모든 이진 문자열(0, 1 포함), ε(빈 문자열) 포함하여 수락하는 DFA
      2. 모든 이진 문자열 중 ε(빈 문자열)을 제외하고 수락하는 DFA

1. 모든 이진 문자열 포함 (ε 포함)

요구사항

  • 입력 기호: Σ = {0, 1}
  • DFA는 ε 및 모든 가능한 이진 문자열(0, 1) 조합을 수락해야 함.
  • ε을 수락하려면 DFA의 초기 상태가 곧 수락 상태여야 함.

DFA 설계

  • 상태:
    • q₀: 초기 상태이자 수락 상태 (ε 및 모든 문자열 수락).
  • 전이:
    • q₀에서 입력이 0 또는 1일 때, 상태는 그대로 유지 (q₀).
  • 결론:
    • DFA는 하나의 상태(q₀)만으로 구성되며, 모든 문자열을 수락.

결과

  • 언어: {ε, 0, 1, 00, 01, 10, 11, ...} (무한 집합).
  • DFA는 상태 하나만으로도 모든 이진 문자열을 처리할 수 있음.

2. 모든 이진 문자열 포함 (ε 제외)

요구사항

  • 입력 기호: Σ = {0, 1}
  • DFA는 ε을 제외한 모든 이진 문자열을 수락해야 함.
  • ε을 제외하려면 초기 상태(q₀)는 수락 상태가 아니어야 하며, 최소 한 개 이상의 입력을 받아야 수락 상태로 전이.

DFA 설계

  • 상태:
    • q₀: 초기 상태 (ε 포함 불가).
    • q₁: 수락 상태 (최소 하나의 입력 후).
  • 전이:
    • q₀에서:
      • 입력이 0 또는 1일 때, q₁로 전이.
    • q₁에서:
      • 입력이 0 또는 1일 때, 상태는 그대로 유지 (q₁).
  • 결론:
    • DFA는 두 개의 상태(q₀, q₁)로 구성되며, ε을 제외한 모든 이진 문자열을 수락.

결과

  • 언어: {0, 1, 00, 01, 10, 11, ...} (ε 제외).
  • DFA는 초기 상태에서 최소 하나의 입력을 처리한 후 수락 상태로 전이.
  • DFA에서 문자열을 입력받다가 수락 상태에 도달하면, 입력받은 문자열이 DFA의 언어(L)에 속한다고 판단합니다.
  • 그런데 초기 상태가 수락 상태라면, DFA는 입력 없이도(즉, ε 상태에서) 이미 수락 상태에 머물러 있기 때문에 빈 문자열(ε)을 수락한다고 판단하게 됩니다.

다시 정리하자면:

  1. DFA의 동작 원리
    • DFA는 입력 문자열을 하나씩 처리하며 상태를 전이합니다.
    • 문자열 처리가 끝난 뒤 현재 상태가 수락 상태라면, 해당 문자열은 DFA의 언어에 속한다고 판단합니다.
  2. 초기 상태가 수락 상태라면?
    • 입력을 전혀 받지 않은 상태, 즉 ε 상태에서 DFA가 초기 상태에 머뭅니다.
    • 초기 상태가 수락 상태에 포함되어 있다면, DFA는 빈 문자열(ε)을 언어에 포함시킵니다.

문제 1: 모든 문자열이 0으로 시작

요구사항

  • 언어: 모든 문자열이 "0"으로 시작하고, 그 뒤에 어떤 문자열이 와도 수락.
  • 입력 알파벳: Σ = {0, 1}

DFA 설계

  • 상태:
    • ( q_0 ): 초기 상태 (시작 상태)
    • ( q_1 ): "0"으로 시작했음을 확인한 수락 상태
    • ( q_{\text{dead}} ): "1"로 시작한 문자열을 처리하는 죽음 상태
  • 전이 규칙:
    • ( q_0 ):
      • 입력 "0" → ( q_1 )로 전이
      • 입력 "1" → ( q_{\text{dead}} )로 전이
    • ( q_1 ):
      • 입력 "0" 또는 "1" → ( q_1 )에 머무름
    • ( q_{\text{dead}} ):
      • 입력 "0" 또는 "1" → ( q_{\text{dead}} )에 머무름
  • 최종 상태: ( F = {q_1} )

동작

  • 입력이 "0"으로 시작하면 ( q_1 )에 도달 → 수락.
  • 입력이 "1"으로 시작하면 ( q_{\text{dead}} )에 도달 → 거부.

문제 2: 모든 문자열이 "10"으로 시작

요구사항

  • 언어: 모든 문자열이 "10"으로 시작하고, 그 뒤에 어떤 문자열이 와도 수락.
  • 입력 알파벳: Σ = {0, 1}

DFA 설계

  • 상태:
    • ( q_0 ): 초기 상태
    • ( q_1 ): 첫 번째 "1"을 읽은 상태
    • ( q_2 ): "10"으로 시작했음을 확인한 수락 상태
    • ( q_{\text{dead}} ): 조건을 만족하지 못하는 문자열을 처리하는 죽음 상태
  • 전이 규칙:
    • ( q_0 ):
      • 입력 "1" → ( q_1 )로 전이
      • 입력 "0" → ( q_{\text{dead}} )로 전이
    • ( q_1 ):
      • 입력 "0" → ( q_2 )로 전이
      • 입력 "1" → ( q_{\text{dead}} )로 전이
    • ( q_2 ):
      • 입력 "0" 또는 "1" → ( q_2 )에 머무름
    • ( q_{\text{dead}} ):
      • 입력 "0" 또는 "1" → ( q_{\text{dead}} )에 머무름
  • 최종 상태: ( F = {q_2} )

동작

  • 입력이 "10"으로 시작하면 ( q_2 )에 도달 → 수락.
  • "10"으로 시작하지 않으면 ( q_{\text{dead}} )에 도달 → 거부.

문제 3: 모든 문자열이 "011"로 시작

요구사항

  • 언어: 모든 문자열이 "011"로 시작하고, 그 뒤에 어떤 문자열이 와도 수락.
  • 입력 알파벳: Σ = {0, 1}

DFA 설계

  • 상태:
    • ( q_0 ): 초기 상태
    • ( q_1 ): 첫 번째 "0"을 읽은 상태
    • ( q_2 ): "01"을 읽은 상태
    • ( q_3 ): "011"을 읽고 수락한 상태
    • ( q_{\text{dead}} ): 조건을 만족하지 못하는 문자열을 처리하는 죽음 상태
  • 전이 규칙:
    • ( q_0 ):
      • 입력 "0" → ( q_1 )로 전이
      • 입력 "1" → ( q_{\text{dead}} )로 전이
    • ( q_1 ):
      • 입력 "1" → ( q_2 )로 전이
      • 입력 "0" → ( q_{\text{dead}} )로 전이
    • ( q_2 ):
      • 입력 "1" → ( q_3 )로 전이
      • 입력 "0" → ( q_{\text{dead}} )로 전이
    • ( q_3 ):
      • 입력 "0" 또는 "1" → ( q_3 )에 머무름
    • ( q_{\text{dead}} ):
      • 입력 "0" 또는 "1" → ( q_{\text{dead}} )에 머무름
  • 최종 상태: ( F = {q_3} )

동작

  • 입력이 "011"로 시작하면 ( q_3 )에 도달 → 수락.
  • "011"로 시작하지 않으면 ( q_{\text{dead}} )에 도달 → 거부.

문제 1: 모든 문자열이 "0"으로 끝나야 함

요구사항

  • 언어: 모든 문자열이 "0"으로 끝나야 함. 문자열의 앞부분은 자유로우나 마지막 문자는 반드시 "0"이어야 함.
  • 입력 알파벳: Σ = {0, 1}

DFA 설계

  • 상태:
    • ( q_0 ): 초기 상태 (문자열이 아직 "0"으로 끝나지 않음)
    • ( q_1 ): 수락 상태 ("0"으로 끝나는 문자열)
  • 전이 규칙:
    • ( q_0 ):
      • 입력 "0" → ( q_1 )
      • 입력 "1" → ( q_0 )
    • ( q_1 ):
      • 입력 "0" → ( q_1 )
      • 입력 "1" → ( q_0 )
  • 최종 상태: ( F = {q_1} )

동작

  • 문자열이 마지막에 "0"으로 끝나면 ( q_1 )에 도달 → 수락.
  • 문자열이 마지막에 "1"으로 끝나면 ( q_0 )에 도달 → 거부.

문제 2: 모든 문자열이 "10"으로 끝나야 함

요구사항

  • 언어: 모든 문자열이 "10"으로 끝나야 함. 문자열의 앞부분은 자유로우나 마지막 두 문자는 반드시 "10"이어야 함.
  • 입력 알파벳: Σ = {0, 1}

DFA 설계

  • 상태:
    • ( q_0 ): 초기 상태
    • ( q_1 ): "1"을 읽은 상태
    • ( q_2 ): "10"을 읽고 수락한 상태
  • 전이 규칙:
    • ( q_0 ):
      • 입력 "1" → ( q_1 )
      • 입력 "0" → ( q_0 )
    • ( q_1 ):
      • 입력 "0" → ( q_2 )
      • 입력 "1" → ( q_1 )
    • ( q_2 ):
      • 입력 "0" → ( q_0 )
      • 입력 "1" → ( q_1 )
  • 최종 상태: ( F = {q_2} )

동작

  • 문자열이 마지막 두 문자로 "10"을 포함하면 ( q_2 )에 도달 → 수락.
  • 그렇지 않으면 ( q_0 ) 또는 ( q_1 )에 머물러 거부.

문제 3: 모든 문자열이 "011"로 끝나야 함

요구사항

  • 언어: 모든 문자열이 "011"로 끝나야 함. 문자열의 앞부분은 자유로우나 마지막 세 문자는 반드시 "011"이어야 함.
  • 입력 알파벳: Σ = {0, 1}

DFA 설계

  • 상태:
    • ( q_0 ): 초기 상태
    • ( q_1 ): "0"을 읽은 상태
    • ( q_2 ): "01"을 읽은 상태
    • ( q_3 ): "011"을 읽고 수락한 상태
  • 전이 규칙:
    • ( q_0 ):
      • 입력 "0" → ( q_1 )
      • 입력 "1" → ( q_0 )
    • ( q_1 ):
      • 입력 "0" → ( q_1 )
      • 입력 "1" → ( q_2 )
    • ( q_2 ):
      • 입력 "0" → ( q_1 )
      • 입력 "1" → ( q_3 )
    • ( q_3 ):
      • 입력 "0" → ( q_1 )
      • 입력 "1" → ( q_2 )
  • 최종 상태: ( F = {q_3} )

동작

  • 문자열이 마지막 세 문자로 "011"을 포함하면 ( q_3 )에 도달 → 수락.
  • 그렇지 않으면 ( q_0 ), ( q_1 ), 또는 ( q_2 )에 머물러 거부.

문제 1: 문자열에 "01"이 서브스트링으로 포함되어야 함

요구사항

  • 언어: 문자열의 어느 위치에든 "01"이 반드시 포함되어야 함.
  • 입력 알파벳: Σ = {0, 1}

DFA 설계

  • 상태:
    • ( q_0 ): 초기 상태
    • ( q_1 ): "0"을 읽은 상태
    • ( q_2 ): "01"을 읽고 서브스트링 조건을 충족한 수락 상태
  • 전이 규칙:
    • ( q_0 ):
      • 입력 "0" → ( q_1 )
      • 입력 "1" → ( q_0 )
    • ( q_1 ):
      • 입력 "0" → ( q_1 )
      • 입력 "1" → ( q_2 )
    • ( q_2 ):
      • 입력 "0" 또는 "1" → ( q_2 )
  • 최종 상태: ( F = {q_2} )

동작

  • 입력 문자열이 "01"을 포함하면 ( q_2 )에 도달 → 수락.
  • "01"을 포함하지 않으면 ( q_2 )에 도달하지 못함 → 거부.

문제 2: 문자열에 "100"이 서브스트링으로 포함되어야 함

요구사항

  • 언어: 문자열의 어느 위치에든 "100"이 반드시 포함되어야 함.
  • 입력 알파벳: Σ = {0, 1}

DFA 설계

  • 상태:
    • ( q_0 ): 초기 상태
    • ( q_1 ): "1"을 읽은 상태
    • ( q_2 ): "10"을 읽은 상태
    • ( q_3 ): "100"을 읽고 서브스트링 조건을 충족한 수락 상태
  • 전이 규칙:
    • ( q_0 ):
      • 입력 "1" → ( q_1 )
      • 입력 "0" → ( q_0 )
    • ( q_1 ):
      • 입력 "0" → ( q_2 )
      • 입력 "1" → ( q_1 )
    • ( q_2 ):
      • 입력 "0" → ( q_3 )
      • 입력 "1" → ( q_1 )
    • ( q_3 ):
      • 입력 "0" 또는 "1" → ( q_3 )
  • 최종 상태: ( F = {q_3} )

동작

  • 입력 문자열이 "100"을 포함하면 ( q_3 )에 도달 → 수락.
  • "100"을 포함하지 않으면 ( q_3 )에 도달하지 못함 → 거부.

문제 3: 문자열에 "0110"이 서브스트링으로 포함되어야 함

요구사항

  • 언어: 문자열의 어느 위치에든 "0110"이 반드시 포함되어야 함.
  • 입력 알파벳: Σ = {0, 1}

DFA 설계

  • 상태:
    • ( q_0 ): 초기 상태
    • ( q_1 ): "0"을 읽은 상태
    • ( q_2 ): "01"을 읽은 상태
    • ( q_3 ): "011"을 읽은 상태
    • ( q_4 ): "0110"을 읽고 서브스트링 조건을 충족한 수락 상태
  • 전이 규칙:
    • ( q_0 ):
      • 입력 "0" → ( q_1 )
      • 입력 "1" → ( q_0 )
    • ( q_1 ):
      • 입력 "0" → ( q_1 )
      • 입력 "1" → ( q_2 )
    • ( q_2 ):
      • 입력 "0" → ( q_1 )
      • 입력 "1" → ( q_3 )
    • ( q_3 ):
      • 입력 "0" → ( q_4 )
      • 입력 "1" → ( q_0 )
    • ( q_4 ):
      • 입력 "0" 또는 "1" → ( q_4 )
  • 최종 상태: ( F = {q_4} )

동작

  • 입력 문자열이 "0110"을 포함하면 ( q_4 )에 도달 → 수락.
  • "0110"을 포함하지 않으면 ( q_4 )에 도달하지 못함 → 거부.

1. DFA의 조건별 정의

  • Prefix (접두사): 문자열이 특정 문자열로 시작해야 함.
    • 예: "101"로 시작하는 문자열.
    • DFA는 반드시 시작 상태에서 정해진 접두사를 읽고, 이후 어떤 문자열도 수락해야 함.
  • Suffix (접미사): 문자열이 특정 문자열로 끝나야 함.
    • 예: "110"으로 끝나는 문자열.
    • DFA는 마지막 문자열을 확인한 후 수락 상태로 전이.
  • Substring (부분 문자열): 문자열의 어디에든 특정 문자열이 포함되어야 함.
    • 예: "011"이 포함된 문자열.
    • DFA는 서브스트링이 확인된 이후 어떤 문자열도 수락해야 함.

2. 상태 수 계산

1) Prefix (접두사)

  • 상태 수: 접두사의 길이를 ( n )이라 하면, ( n + 2 )개의 상태가 필요.
    • 이유:
      • 접두사를 읽는 데 ( n )개의 상태.
      • 접두사가 완료된 후의 상태.
      • Dead State (죽음 상태): 접두사가 아닌 문자열을 처리.
  • 예: 문자열이 "101"로 시작 → 상태 수 ( 3(길이) + 2 = 5 ).

2) Suffix (접미사)

  • 상태 수: 접미사의 길이를 ( n )이라 하면, ( n + 1 )개의 상태가 필요.
    • 이유:
      • 접미사를 읽는 데 ( n )개의 상태.
      • 접미사가 확인된 후의 상태.
      • Dead State가 필요하지 않음.
  • 예: 문자열이 "110"으로 끝남 → 상태 수 ( 3(길이) + 1 = 4 ).

3) Substring (부분 문자열)

  • 상태 수: 서브스트링의 길이를 ( n )이라 하면, ( n + 1 )개의 상태가 필요.
    • 이유:
      • 서브스트링을 읽는 데 ( n )개의 상태.
      • 서브스트링이 확인된 후의 상태.
      • Dead State가 필요하지 않음.
  • 예: 문자열에 "011" 포함 → 상태 수 ( 3(길이) + 1 = 4 ).

3. 문제 예시

(1) 서브스트링이 "100"인 문자열의 상태 수

  • 서브스트링 길이 = 3
  • 상태 수: ( 3 + 1 = 4 ).

(2) 문자열이 "99개의 0"으로 끝나는 경우의 상태 수

  • 접미사 길이 = 99
  • 상태 수: ( 99 + 1 = 100 ).

(3) 문자열이 "111110"으로 시작하는 경우의 상태 수

  • 접두사 길이 = 6
  • 상태 수: ( 6 + 2 = 8 ) (Dead State 포함).

4. 요약

  1. Prefix (접두사): ( n + 2 )개의 상태 필요 (Dead State 포함).
  2. Suffix (접미사): ( n + 1 )개의 상태 필요 (Dead State 없음).
  3. Substring (부분 문자열): ( n + 1 )개의 상태 필요 (Dead State 없음).

문제 정의

  • 언어 조건: 모든 이진 문자열에서 마지막 두 비트가 반드시 동일해야 함.
    • ( \text{Accept: } 00, 11 )
    • 예: "00", "1100", "1011", "01100", 등.
    • 마지막 두 비트가 같지 않은 경우 문자열을 거부.
  • 입력 알파벳: Σ = {0, 1}

DFA 설계

1. DFA의 상태 정의

  • 상태 설명:
    • ( q_0 ): 초기 상태 (시작점, 아직 마지막 두 비트를 알 수 없음).
    • ( q_1 ): 마지막 비트가 "0".
    • ( q_2 ): 마지막 두 비트가 "00" (수락 상태).
    • ( q_3 ): 마지막 비트가 "1".
    • ( q_4 ): 마지막 두 비트가 "11" (수락 상태).

2. 상태 전이

  • 전이 규칙:
    • ( q_0 ):
      • 입력 "0" → ( q_1 )
      • 입력 "1" → ( q_3 )
    • ( q_1 ):
      • 입력 "0" → ( q_2 ) (마지막 두 비트: "00")
      • 입력 "1" → ( q_3 )
    • ( q_2 ):
      • 입력 "0" → ( q_2 ) (마지막 두 비트 유지: "00")
      • 입력 "1" → ( q_3 )
    • ( q_3 ):
      • 입력 "0" → ( q_1 )
      • 입력 "1" → ( q_4 ) (마지막 두 비트: "11")
    • ( q_4 ):
      • 입력 "0" → ( q_1 )
      • 입력 "1" → ( q_4 ) (마지막 두 비트 유지: "11")

3. DFA의 수락 상태

  • 수락 상태: ( F = {q_2, q_4} )
    • ( q_2 ): 마지막 두 비트가 "00".
    • ( q_4 ): 마지막 두 비트가 "11".

DFA 동작

예제 1: 입력 "1011"

  1. ( q_0 ): 초기 상태에서 "1" 입력 → ( q_3 ).
  2. ( q_3 ): "0" 입력 → ( q_1 ).
  3. ( q_1 ): "1" 입력 → ( q_3 ).
  4. ( q_3 ): "1" 입력 → ( q_4 ) (수락 상태, 마지막 두 비트 "11").
  • 결과: 문자열 수락.

예제 2: 입력 "10010"

  1. ( q_0 ): 초기 상태에서 "1" 입력 → ( q_3 ).
  2. ( q_3 ): "0" 입력 → ( q_1 ).
  3. ( q_1 ): "0" 입력 → ( q_2 ).
  4. ( q_2 ): "1" 입력 → ( q_3 ).
  5. ( q_3 ): "0" 입력 → ( q_1 ) (마지막 두 비트가 "10").
  • 결과: 문자열 거부.

DFA 시각화

  • 상태와 전이 요약: 
    q0 --0--> q1 --0--> q2
 |         |         |
 v         v         v
q3 --1--> q4 <------ q3
    • ( q_0 ): 시작 상태.
    • ( q_2, q_4 ): 수락 상태.

문제 정의

  • 언어 조건: 이진 문자열의 처음 두 비트가 반드시 동일해야 함.
    • ( \text{Accept: } 00, 11 )로 시작하는 문자열.
    • 예: "00", "11", "001", "1101", "0000", 등.
    • 처음 두 비트가 같지 않으면 문자열을 거부.
  • 입력 알파벳: Σ = {0, 1}

DFA 설계

1. DFA의 상태 정의

  • 상태 설명:
    • ( q_0 ): 초기 상태 (시작점).
    • ( q_1 ): 첫 번째 비트가 "0".
    • ( q_2 ): 처음 두 비트가 "00" (수락 상태).
    • ( q_3 ): 첫 번째 비트가 "1".
    • ( q_4 ): 처음 두 비트가 "11" (수락 상태).
    • ( q_{\text{dead}} ): 처음 두 비트가 같지 않을 때로 이동하는 죽음 상태.

2. 상태 전이

  • 전이 규칙:
    • ( q_0 ):
      • 입력 "0" → ( q_1 )
      • 입력 "1" → ( q_3 )
    • ( q_1 ):
      • 입력 "0" → ( q_2 ) (처음 두 비트가 "00").
      • 입력 "1" → ( q_{\text{dead}} ) (처음 두 비트가 "01").
    • ( q_2 ):
      • 입력 "0" 또는 "1" → ( q_2 ) (처음 두 비트 "00" 충족 후 어떤 문자열도 수락).
    • ( q_3 ):
      • 입력 "1" → ( q_4 ) (처음 두 비트가 "11").
      • 입력 "0" → ( q_{\text{dead}} ) (처음 두 비트가 "10").
    • ( q_4 ):
      • 입력 "0" 또는 "1" → ( q_4 ) (처음 두 비트 "11" 충족 후 어떤 문자열도 수락).
    • ( q_{\text{dead}} ):
      • 입력 "0" 또는 "1" → ( q_{\text{dead}} ) (죽음 상태 유지).

3. DFA의 수락 상태

  • 수락 상태: ( F = {q_2, q_4} )
    • ( q_2 ): 처음 두 비트가 "00".
    • ( q_4 ): 처음 두 비트가 "11".

DFA 동작

예제 1: 입력 "0011"

  1. ( q_0 ): 초기 상태에서 "0" 입력 → ( q_1 ).
  2. ( q_1 ): "0" 입력 → ( q_2 ) (수락 상태, 처음 두 비트 "00").
  3. ( q_2 ): "1" 입력 → ( q_2 ).
  4. ( q_2 ): "1" 입력 → ( q_2 ).
  • 결과: 문자열 수락.

예제 2: 입력 "1010"

  1. ( q_0 ): 초기 상태에서 "1" 입력 → ( q_3 ).
  2. ( q_3 ): "0" 입력 → ( q_{\text{dead}} ) (처음 두 비트 "10").
  3. ( q_{\text{dead}} ): 나머지 입력은 모두 ( q_{\text{dead}} )에 머뭄.
  • 결과: 문자열 거부.

DFA 시각화

  • 상태와 전이 요약: 
    q0 --0--> q1 --0--> q2
 |         |         |
 v         v         v
q3 --1--> q4 <------ q3
 \        /         /
  \---> q_dead <---
    • ( q_0 ): 시작 상태.
    • ( q_2, q_4 ): 수락 상태.
    • ( q_{\text{dead}} ): 거부 상태.

'강의 > Theory of Computation' 카테고리의 다른 글

Non-Deterministic PushDown Automata (NFA)  (0) 2025.02.05
Construction of Minimal DFA Examples  (0) 2025.02.02
TOC Fundamentals, Regular Languages  (0) 2025.01.28
Introduction  (0) 2025.01.26

'강의/Theory of Computation'의 다른글

  • 현재글Construct Minimal DFA

관련글

티스토리툴바