NFA 최소화

NFA minimization

오토마타 이론(이론 컴퓨터 과학의 한 분야)에서, NFA 최소화는 주어진 비결정론적 유한 오토마톤(NFA)을 최소한의 상태, 전이 또는 둘 모두를 갖는 동등한 NFA로 변환하는 작업이다.DFA 최소화를 위한 효율적인 알고리즘이 존재하지만 NFA 최소화는 PSPACE-완전입니다.[1]효율적인(다항 시간) 알고리즘은 알려져 있지 않으며, 표준 가정 P p PSPACE에서는 존재하지 않는다.지금까지 알려진 알고리즘 중 가장 효율적인 것은 Kameda'입니다.와이너 [2]알고리즘

최소 NFA의 고유성 없음

결정론적 유한 오토마타와 달리 최소 NFA는 고유하지 않을 수 있습니다.같은 크기의 NFA가 여러 개 있을 수 있으며, 같은 정규 언어를 사용할 수 있지만 그보다 적은 상태의 동등한 NFA 또는 DFA는 없습니다.

레퍼런스

  1. ^ Jiang, Tao; Ravikumar, B. (1993), "Minimal NFA Problems are Hard", SIAM Journal on Computing, 22 (6): 1117–1141, doi:10.1137/0222067
  2. ^ Kameda, Tsunehiko; Weiner, Peter (August 1970). "On the State Minimization of Nondeterministic Finite Automata". IEEE Transactions on Computers. IEEE. C-19 (7): 617–627. doi:10.1109/T-C.1970.222994. S2CID 31188224. Retrieved 2020-05-03.

외부 링크

  • Kameda-Weiner의 C# 구현 수정(1970) [1]