Concepto en informática teórica
En informática teórica y teoría del lenguaje formal , la complementación de un autómata [ aclarar ] es el problema de calcular un autómata que acepte precisamente las palabras rechazadas por otro autómata. Formalmente, dado un autómata A que reconoce un lenguaje regular L , queremos calcular un autómata que reconozca precisamente las palabras que no están en L , es decir, el complemento de L.
Se estudian varias cuestiones sobre la operación de complementación, tales como:
- Su complejidad computacional : ¿cuál es la complejidad, dado un autómata, de calcular un autómata para el lenguaje complementario?
- Su complejidad de estados : ¿cuál es el menor número de estados de un autómata que reconoce el complemento?
Con autómatas finitos deterministas
Con autómatas finitos no deterministas
Con un autómata finito no determinista , la complejidad de estado del autómata complementario puede ser exponencial. [1] Los límites inferiores también se conocen en el caso de autómatas no ambiguos . [2]
Con autómatas bidireccionales
También se ha estudiado la complementación para autómatas bidireccionales . [3]
Con autómatas Büchi
Véase también
Referencias
- ^ Birget, Jean-Camille (1993). "Órdenes parciales de palabras, elementos mínimos de lenguajes regulares y complejidad de estados". Ciencias Informáticas Teóricas . 119 (2): 267–291. doi :10.1016/0304-3975(93)90160-U. ISSN 0304-3975.
- ^ Göös, Mika; Kiefer, Stefan; Yuan, Weiqiang (12 de febrero de 2022). "Límites inferiores para autómatas inequívocos mediante la complejidad de la comunicación". arXiv : 2109.09155 [cs.FL].
- ^ Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (1 de agosto de 2007). "Complementación de autómatas finitos bidireccionales". Información y computación . 205 (8): 1173–1187. doi : 10.1016/j.ic.2007.01.008 . ISSN 0890-5401.
