Problém prázdnoty - Emptiness problem

v teoretická informatika a teorie formálního jazyka, je formální jazyk prázdný pokud jeho soubor platných vět je prázdná sada. The problém prázdnoty je otázka určení, zda je jazyk prázdný vzhledem k jeho určitému zastoupení, například a konečný stavový automat.^[1] Pro automat, který má ${ displaystyle n}$ státy, to je a rozhodovací problém které lze vyřešit v ${ displaystyle O (n ^ {2})}$ čas.^[2] Varianty této otázky, například problém prázdnoty pro nevymazávací automaty zásobníku, jsou PSPACE - kompletní.^[3]

Problém prázdnoty je nerozhodnutelný pro kontextové gramatiky, skutečnost, která vyplývá z nerozhodnutelnosti zastavení problému. Je však rozhodující pro bezkontextové gramatiky.^[3]

Reference

^ Sipser, Michael (2012). Úvod do teorie výpočtu. Cengage Learning. ISBN 9781285401065.
^ „Přednáška 6: Vlastnosti běžných jazyků - II“. Teorie COMS W3261 CS. Ústav výpočetní techniky, Columbia University. Citováno 2019-08-22.
^ ^A ^b Hopcroft, J. E.; Ullman, J. D. (1979). Úvod do teorie automatů, jazyků a výpočtu (první vydání). Addison-Wesley. ISBN 81-7808-347-7.

Tento počítačová věda článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.