오메가어

Ω 언어는 기호의 무한 길이 시퀀스 집합이다.

형식 정의

Ⅱ를 기호 집합(필수적으로 유한할 필요는 없음)으로 한다.형식^* 언어 이론의 표준 정의에 따라, is은 σ에 걸쳐 모든 유한한 단어들의 집합이다.유한한 단어마다 길이가 있는데, 이것은 자연수다.길이가 n인 단어 w가 주어지면 w는 설정 {0,1, 1,...,n-1} → σ에서 함수로 볼 수 있으며, i에서의 값은 위치 i에 기호를 부여한다.무한 단어 또는 Ω-words도 $\mathbb {N}$ 로 N ${\$ { $N}$ 에서 to까지의 $\mathbb {N}$ 함수로 볼 수 있다.σ에 걸쳐서 모든 무한한 단어들의 집합은 σ으로^ω 표시된다.σ에 걸쳐서 모든 유한하고 무한한 낱말의 집합은 σ이라고^∞ 쓰여지기도 한다.

따라서 σ에 대한 Ω 언어 L은 σ의^ω 하위 집합이다.

운영

Ω 언어에 대해 정의된 몇 가지 일반적인 작동은 다음과 같다.

교차로 및 조합: Ω-언어 L과 M이 주어진 경우, $L and$ $M$ 과 L $m$ M은 모두 Ω-언어다.
왼쪽 연결: L은 Ω언어, K는 유한한 단어의 언어일 뿐이다.그런 다음 K를 왼쪽, 왼쪽에만 L에 연결하여 새로운 Ω 언어 KL을 산출할 수 있다.
오메가(무한 반복): 표기법이 암시하듯이 조작 $(\cdot )^{\omega }$ ( $(\cdot )^{\omega }$ ) $(\cdot )^{\omega }$ ${\$ 은 유한한 길이의 언어에 대한 클레네 항성 연산자의 무한 버전이다 $(\cdot )^{\omega }$ .형식 언어 L이 주어진 경우^ω L은 L에서 나오는 모든 단어 순서의 Ω 언어로서, 기능적 관점에서 모든 $\mathbb {N} \to L$ N → $\mathbb {N} \to L$ ${\displaystyle \mathb {N} \to$ L $}$ 의 Ω 언어다 $\mathbb {N} \to L$
접두사: w를 Ω 단어로 하자.그러면 공식 언어 Pref(w)는 w의 모든 유한한 접두사를 포함한다.
한계: 유한 길이 언어 L이 주어지면, Ω-w는 $프리프(w)$ l $L$ 이 무한 집합인 경우에만 L의 한계에 들어간다.즉 임의로 큰 자연수 n의 경우, 길이가 n보다 크고 w의 접두어인 L에서 어떤 단어를 선택하는 것이 항상 가능하다.L에 대한 제한 작업은 L 또는^δ ${\vec {L}}$ → ${\$ 라고 쓸 수 있다 ${\vec {L}}$

Ω-words 사이의 거리

σ^ω 집합은 다음과 같이 $d:\Sigma ^{\omega }\times \Sigma ^{\omega }\rightarrow \mathbb {R}$ 미터법 $d:\Sigma ^{\omega }\times \Sigma ^{\omega }\rightarrow \mathbb {R}$ $d:\Sigma ^{\omega }\times \Sigma ^{\omega }\rightarrow \mathbb {R}$ $d:\Sigma ^{\omega }\times \Sigma ^{\omega }\rightarrow \mathbb {R}$ $d:\Sigma ^{\omega }\times \Sigma ^{\omega }\rightarrow \mathbb {R}$ → R ${\$ d $:\Sigma ^{\omega$ ^{\\\ $time \Sigma ^{\omega }\mathb$ { $R}}}}}}$ 을(를) 정의하여 미터법으로 만들 수 있다 $.$

d(w,v)=\inf\{2^{- x }:x\in \Sigma ^{*}\{\text{and}}\x\in {\text{Pref}(w)\cap {\text{Pref}(v)\}}}}}}

여기서 x는 "x의 길이"(x의 기호 수)로 해석되며, inf는 실제 숫자의 집합에 대한 최소값이다. $w=v$ = $w=v$ $w=v$ 이면 $w=v$ 가장 긴 접두사 x가 $d(w,v)=0$ d $d(w,v)=0$ , $d(w,v)=0$ ) = $d(w,v)=0$ {\ $displaystyle$ d $(w,v)=0$ 대칭은 분명하다.Transitivity follows from the fact that if w and v have a maximal shared prefix of length m and v and u have a maximal shared prefix of length n then the first $\min\{m,n\}$ characters of w and u must be the same so ${\d$ $isplaystyle d(w,u)\leq$ 2 $^{-\min\{m,n\}}\leq 2^{-m}+2^{-n}=d(w,v)+d(v,u$ 따라서 d는 메트릭이다.

중요 하위 클래스

Ω언어 중 가장 널리 사용되는 서브클래스는 Ω-정규어 집합으로, 부치오토마타(Büchi automata)가 인식할 수 있는 유용한 속성을 누린다.따라서 Ω-정규어 멤버십의 의사결정 문제는 Büchi 자동화를 사용하여 해독할 수 있으며, 계산이 상당히 간단하다.

언어 σ이 집합의 전원 집합("원자 명제"라고 함)이라면 Ω 언어는 선형 시간 속성이며, 모델 확인에서 연구된다.

참고 문헌 목록

페린, D., 핀, J.E. "무한 단어: 오토마타, 세미그룹, 로직, 게임"순수 및 응용 수학 Vol 141, Exvier, 2004.
스타이거, L. "Ω-Language"G. 로젠버그와 A. Salomaa, 편집자, 공식 언어 핸드북, 제3권 339-387페이지.1997년 베를린 스프링거-베를라크.
토마스, W. "무한한 물체에 대한 오토마타"얀 반 리우웬 편집장, 이론 컴퓨터 과학 핸드북, B권: 형식 모델과 의미론에서 133-192페이지.1990년 암스테르담의 엘시어 사이언스 출판사

Search

오메가어

네임스페이스

더

목차

형식 정의

운영

Ω-words 사이의 거리

중요 하위 클래스

참고 문헌 목록