Llenguatge regular: diferència entre les revisions

Per expressions regulars, el problema d'universalitat és [[NP-complet]] inclús per un alfabet simple.<ref>{{Ref-llibre|cognom=V.|nom=Aho, Alfred|títol=The design and analysis of computer algorithms|url=https://www.worldcat.org/oclc/1147299|data=[1974]|editorial=Addison-Wesley Pub. Co|lloc=Reading, Mass.|isbn=0201000296}}</ref> Per alfabets més grans, el problema és [[PSPACE-complet]].<ref>{{Ref-web|url=https://mathscinet.ams.org/mathscinet-getitem?mr=0421145|títol=MR: Matches for: MR=421145|consulta=2019-02-13}}</ref><ref>{{Ref-publicació|cognom=Bowen Hurt III|nom=Harry|article=|publicació=On the time and tape complexity of languages|url=https://ecommons.cornell.edu/bitstream/handle/1813/6025/73-182.pdf?sequence=1&isAllowed=y|data=Agost 1973|pàgines=106}}</ref>