Místní jazyk (formální jazyk) - Local language (formal language)

V matematice, a místní jazyk je formální jazyk u kterého lze určit příslušnost slova v jazyce pohledem do „okna“^{[je zapotřebí objasnění ]} délky dva.^[1] Ekvivalentně je to jazyk uznávaný a místní automat určitý druh deterministický konečný automat.^[2]

Formálně jazyk L přes abecedu A je definován jako místní pokud existují podmnožiny R a S z A a podmnožina F z A×A takové, že slovo w je v L právě tehdy, pokud první písmeno z w je v R, poslední písmeno z w je v S a žádný faktor délky 2 palce w je v F.^[3] To odpovídá regulární výraz^[1][4]

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

Obecněji, a k-testovatelný Jazyk L je členství, pro které je členství ve slově w v L záleží pouze na prefixu, příponě a množině faktorů w délky k; jazyk je místně testovatelné Pokud to je k-testovatelné pro některé k.^[5] Místní jazyk je testovatelný na 2.^[1]

Příklady

• Přes abecedu {A,b,[,]}^[4]

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

Vlastnosti

• Rodina místních jazyků skončila A je uzavřen v průsečíku a Kleene hvězda, ale ne doplnění, sjednocení nebo zřetězení.^[4]
• Každý běžný jazyk neobsahující prázdný řetězec je obrazem místního jazyka pod a přísně abecední morfismus.^[1][6][7]

Reference

• Lawson, Mark V. (2004). Konečné automaty. Chapman and Hall / CRC. ISBN  1-58488-255-7. Zbl  1086.68074.
• McNaughton, Robert; Papert, Seymour (1971). Bezplatné automaty. Výzkumná monografie. 65. S dodatkem od Williama Hennemana. MIT Stiskněte. ISBN  0-262-13076-9. Zbl  0232.94024.
• Sakarovitch, Jacques (2009). Základy teorie automatů. Z francouzštiny přeložil Reuben Thomas. Cambridge: Cambridge University Press. ISBN  978-0-521-84425-3. Zbl  1188.68177.
• Salomaa, Arto (1981). Klenoty teorie formálního jazyka. Pitman Publishing. ISBN  0-273-08522-0. Zbl  0487.68064.