이론 컴퓨터 과학과 형식 언어 이론에서, 동등성 문제는 형식 언어의 두 가지 표현이 주어졌을 때, 그것들이 동일한 형식 언어를 의미하는지 여부를 결정하는 문제이다.
이 의사결정 문제의 복잡성과 결정 가능성은 고려 중인 표현의 유형에 따라 달라집니다.예를 들어 유한상태 오토마타의 경우 등가성은 결정 가능하며 문제는 PSPACE-완전인 반면 푸시다운 오토마타, 컨텍스트프리 문법 [1]등은 결정되지 않는다.
이 컴퓨터 과학 기사는 촌스럽다.위키피디아를 확장함으로써 위키피디아를 도울 수 있습니다.
