일반화 비계수적 유한자동화

Generalized nondeterministic finite automaton

계산 이론에서, 표현 자동 또는 일반화 비결정적 유한 상태 기계라고도 하는 일반화 비결정적 유한 자동화는 각 전환에 어떤 정규식이 붙어 있는 비결정적 유한 자동화의 변형이다.GNFA는 입력에서 기호의 블록을 읽으며, 입력에서 기호의 블록은 변환에 대한 정규식으로 정의된 문자열을 구성한다.표준 유한 상태 기계와 일반화된 비결정적 유한 상태 기계 사이에는 몇 가지 차이점이 있다.GNFA는 하나의 시작 상태와 하나의 승인 상태만 가져야 하며, 이는 동일한 상태가 될 수 없는 반면, NFA 또는 DFA는 둘 다 여러 개의 승인 상태를 가질 수 있으며, 시작 상태는 승인 상태가 될 수 있다.GNFA는 두 상태 사이에 하나의 전환만 있어야 하는 반면, NFA 또는 DFA는 상태 간의 수많은 전환을 허용한다.GNFA에서 상태는 일반화된 비계수적 유한 상태 기계를 그릴 때 빈 집합으로 표시된 전환을 무시하는 것이 보통이지만 기계의 모든 상태로 단일 전환이 있다.

형식 정의

GNFA는 5-투플(S, s, T, s, a)로 정의할 수 있다.

  • 유한 상태 집합(S)
  • 알파벳( ()이라고 하는 유한 집합
  • 전환 함수(T : (S ∖ {a} × (S ∖ {s} → R);
  • 시작 상태(s ∈ S)
  • 수락 상태(∈ S)

여기서 R은 알파벳 Ⅱ에 걸쳐 있는 모든 정규식의 집합이다.

전환 함수는 두 상태의 쌍을 인수로 삼고 정규식(전환의 라벨)을 출력한다.이것은 다른 유한 상태 기계들과 다르며, 이 기계들은 알파벳의 입력과 입력으로 받아들여지고, 다음 상태(또는 비결정적 유한 상태 기계의 경우 빈 문자열)를 출력한다.DFA 또는 NFA는 GNFA로 쉽게 변환할 수 있으며, 그 다음 S = {s, a}까지 GNFA의 일부를 단일 에지로 반복적으로 접음으로써 GNFA를 정규식으로 쉽게 변환할 수 있다.마찬가지로, 정규식 연산자를 새 에지로 변경하여 각 에지가 최대 1. 단일한 길이의 끈과 일치하는 정규식으로 라벨을 표시할 때까지 NFA를 새 에지로 줄일 수 있다.이것은 GNFA가 DFA와 NFA와 동일한 공식 언어 집합을 인식하고 있음을 보여준다.

참조

외부 링크

  • GNFA에 대한 그래픽 설명과 GNFA를 사용하여 NFA를 정규식으로 변환하는 프로세스는 [1]에서 확인할 수 있다.