El lenguaje hoja es un método en la teoría de la complejidad computacional para caracterizar una clase de complejidad formalizando lo que significa para una máquina "aceptar" una entrada. [1]
Las clases de complejidad se definen típicamente en términos de una máquina de Turing no determinista de tiempo polinómico (MNT). Estas máquinas poseen múltiples caminos computacionales, y los resultados de estos caminos determinan si una entrada es aceptada o rechazada. [1] Tradicionalmente, una MNT acepta una entrada si al menos un camino la acepta, y la rechaza solo si todos los caminos la rechazan. Por el contrario, una máquina de Turing co-no determinista (co-MNT) acepta una entrada solo si todos los caminos la aceptan, y la rechaza si algún camino la rechaza. Además, también se pueden definir nociones más complejas de aceptación.
Para formalizar la caracterización de una clase de complejidad, se puede examinar el lenguaje formal asociado con cada condición de aceptación. Esto implica asumir un árbol ordenado y leer las cadenas aceptadas/rechazadas de las hojas del árbol de cómputo . Las NTM aceptarán si la cadena de hoja está en el lenguaje 0*1{0, 1}* y rechazarán si la cadena de hoja está en el lenguaje 0* . [2]