로컬 언어(공식 언어)

수학에서 지방어는 언어의 단어의 멤버십을 단어의 첫 번째와 마지막 기호, 그리고 각 두 개의 심볼 하위 문자들을 보고 결정할 수 있는 공식적인 언어다.^[1] 동등하게, 그것은 지역 자동화에 의해 인식된 언어로서, 결정론적 유한 자동화의 특정한 종류다.^[2]

형식적으로 알파벳 A에 대한 언어 L은 A의 하위 집합 R과 S와 A×A의 하위 집합 F가 있는 경우 국부적인 것으로 정의되며, w의 첫 번째 문자가 R에 있는 경우에만 w의 마지막 문자가 S에 있고 w의 길이 2 인자가 F에 있지 않은 경우.^[3] 이것은 정규식에^[1][4] 해당한다.

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

보다 일반적으로, k-검정 가능한 언어 L은 L에서 w 단어의 멤버십이 w 길이 k의 접두사^{[further explanation needed]}, 접미사 및 요인 집합에만 의존하는 언어로서, 어떤 k-검정 가능한 언어는 k-검정 가능한 경우 국소적으로 시험할 수 있다.^[5] 지역 언어는 2가지 테스트가 가능하다.^[1]

예

• {a,b,[,]}^[4] 알파벳 이상

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

특성.

• A 이상의 지역 언어군은 교차로와 클레인별 아래 폐쇄되지만, 결합이나 결합은 보완되지 않는다.^[4]
• 빈 문자열을 포함하지 않는 모든 정규어는 엄밀히 알파벳 형태론 아래 지역 언어의 이미지다.^[1][6][7]

참조

• Lawson, Mark V. (2004). Finite automata. Chapman and Hall/CRC. ISBN 1-58488-255-7. Zbl 1086.68074.
• McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata. Research Monograph. Vol. 65. With an appendix by William Henneman. MIT Press. ISBN 0-262-13076-9. Zbl 0232.94024.
• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.
• Salomaa, Arto (1981). Jewels of Formal Language Theory. Pitman Publishing. ISBN 0-273-08522-0. Zbl 0487.68064.