한 NFA에서 허용하는 언어가 다른 NFA에서 허용하는 언어의 상위 집합인지 여부를 결정하는 효율적인 알고리즘이 있습니까?

두 결정적 유한 오토마타 주어 M1 및 M2, M1 수락 언어 M2 수락 언어의 수퍼인지를 결정하기위한 효율적인 알고리즘이 무엇입니까?한 NFA에서 허용하는 언어가 다른 NFA에서 허용하는 언어의 상위 집합인지 여부를 결정하는 효율적인 알고리즘이 있습니까?

출처

2012-02-25 Daniel Trebbien

P = NP가 아니면 제외. 그런 알고리즘을 사용하면 두 개의 NFA가 동형인지 여부를 쉽게 결정할 수 있습니다 (A가 B의 수퍼 세트이고 B가 A의 수퍼 세트 인 지 확인). known NP-hard problem입니다. 자세한 내용은 read this paper을 참조하십시오. 복잡성 결과에 대한 낙관적 인 표가 있습니다.

출처

2012-02-26 03:15:25 Mikola

다른 NP 완성 문제에서 NFA 동형 이의로의 감소를 알고 있습니까? – hugomg

@missigno : 축소를 더 자세히 설명하는 문서에 대한 링크를 추가했습니다. – Mikola

Mikola, 당신의 답은 맞지만 당신의 말씨가 틀립니다 : 같은 모양의 동형 의미, 두 가지 자동문은 그들의 상태 사이에 1-1 매핑이있는 경우 동형입니다, 그런 bla bla. 여기서는 관련이 없지만 두 개의 오토 마트는 동형이 아닌 동일한 언어를 허용 할 수 있습니다. (이것은 그래프 동형 검사가 NP-Hard인지 혼란을 준다.) "두 개의 NFA가 동형인지 여부"대신에 "두 개의 NFA가 동일한 언어를 수용하는지"로 답을 편집한다면 모두 괜찮을 것이다. –

한 NFA에서 허용하는 언어가 다른 NFA에서 허용하는 언어의 상위 집합인지 여부를 결정하는 효율적인 알고리즘이 있습니까?

답변

관련 문제