Lenguaje local (lenguaje formal)

En matemáticas, un idioma local es un idioma formal para el cual la pertenencia de una palabra al idioma se puede determinar observando el primer y el último símbolo y cada subcadena de dos símbolos de la palabra. ^[1] De manera equivalente, es un idioma reconocido por un autómata local , un tipo particular de autómata finito determinista . ^[2]

Formalmente, un lenguaje L sobre un alfabeto A se define como local si hay subconjuntos R y S de A y un subconjunto F de A × A tales que una palabra w está en L si y solo si la primera letra de w está en R , la última letra de w está en S y ningún factor de longitud 2 en w está en F. ^[3] Esto corresponde a la expresión regular ^{[1] [4]}

${\displaystyle (RA^{*}\cap A^{*}S)\setminus A^{*}FA^{*}\ .}$

En términos más generales, un lenguaje k - comprobable L es uno para el cual la pertenencia de una palabra w en L depende únicamente del prefijo y sufijo de longitud k y del conjunto de factores de w de longitud k ; ^[5] un lenguaje es localmente comprobable si es k -comprobable para algún k . ^[6] Un lenguaje local es 2-comprobable. ^[1]

• Sobre el alfabeto { a , b , [ , ] } ^[4]

${\displaystyle aa^{*},\ [ab]\ .}$

• La familia de lenguas locales sobre A está cerrada bajo intersección y estrella de Kleene , pero no complemento, unión o concatenación. ^[4]
• Todo lenguaje regular que no contenga la cadena vacía es la imagen de un lenguaje local bajo un morfismo estrictamente alfabético . ^{[1] [7] [8]}

• Lawson, Mark V. (2004). Autómatas finitos . Chapman y Hall/CRC. ISBN 1-58488-255-7.Zbl 1086.68074  .
• McNaughton, Robert; Papert, Seymour (1971). Autómatas sin contador . Monografía de investigación. Vol. 65. Con un apéndice de William Henneman. MIT Press. ISBN 0-262-13076-9.Zbl 0232.94024  .
• Sakarovitch, Jacques (2009). Elementos de la teoría de autómatas . Traducido del francés por Reuben Thomas. Cambridge: Cambridge University Press . ISBN 978-0-521-84425-3.Zbl 1188.68177  .
• Salomaa, Arto (1981). Joyas de la teoría del lenguaje formal . Pitman Publishing. ISBN 0-273-08522-0.Zbl 0487.68064  .