Tomhetsproblem
Inom teoretisk datavetenskap och formell språkteori är ett formellt språk tomt om dess uppsättning giltiga meningar är den tomma uppsättningen . Tomhetsproblemet är frågan om att avgöra om ett språk är tomt med tanke på någon representation av det, till exempel en automat med ändligt tillstånd . För en automat som har tillstånd är detta ett beslutsproblem som kan lösas i tid . Men varianter av den frågan, som tomhetsproblemet för stackautomater som inte raderas , är PSPACE-kompletta .
Tomhetsproblemet är oavgörbart för kontextkänsliga grammatiker , ett faktum som följer av det oavgjorda problemet med stoppproblemet . Det är dock avgörbart för sammanhangsfria grammatiker .