공허문제

이론 컴퓨터 과학과 공식 언어 이론에서, 만약 그것의 유효한 문장 집합이 빈 집합이라면, 공식 언어는 비어있다.공허 문제는 유한 상태 자동화와 같이 언어의 어느 정도 대표성을 고려해 볼 때 언어가 비어 있는지 여부를 판단하는 문제다.^[1]$n{\displaystyle }$ ${\displaystyle n}$ 상태가$$ 있는 자동화의 경우 $이$는 O (${\displaystyle {n\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$) ${\displaystyle O(n^{2})$ 시간$$ 내에 해결할 수 있는 의사결정 문제다.^[2]그러나 이러한 질문의 변형(예: 비소거 스택 오토마타에 대한 공허함 문제)은 PSPACE-완전하다.^[3]

공허 문제는 문맥에 민감한 문법으로는 이해할 수 없는 것인데, 이는 중단 문제의 불분명함에서 비롯된 사실이다.그러나 그것은 문맥이 없는 문법에서는 채택할 수 없다.^[3]

참조

이 컴퓨터 과학 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.

• v
• t