별높이

이론 컴퓨터 과학에서, 형식 언어 이론에서 더 정확히 말하면, 별의 높이는 정규 표현과 정규 언어의 구조적 복잡성을 측정하는 척도다.정규식의 항성 높이는 그 표현에서 나타나는 별의 최대 보금자리 깊이와 같다.정규 언어의 별 높이는 해당 언어에 대한 정규 표현식 중 가장 작은 별 높이다.항성 높이의 개념은 Eggan(1963년)에 의해 처음 정의되고 연구되었다.

형식 정의

보다 공식적으로, 유한한 알파벳 A에 대한 정규식 E의 별 높이는 다음과 같이 귀납적으로 정의된다.

• ${\displaystyle \textstyle h\left(\emptyset \right)\,=\,0}$, ${\displaystyle \textstyle h\left(\varepsilon \right)\,=\,0}$, and ${\displaystyle \textstyle h\left(a\right)\,=\,0}$ for all alphabet symbols a in A.
• $\displaystyle \textstyle h\\(EF\right)\,=\,h\왼쪽(E\,mid \,F\right)\,=\,=\,\max \left(\,h(E),h(F)\,\right)}}$
• $[\\displaystyle \textstyle h\왼쪽(E^{*}\오른쪽)\,=\,h(E)+1.}$

여기서 $\varnothing {\displaystyle \mathrm{}}$ ${\$은 빈 세트를$$ 나타내는 특수 정규식이고 and 빈 단어를 나타내는 특수식이며, E와 F는 임의의 정규식이다.

일반 언어 L의 항성 높이 h(L)는 L을 나타내는 모든 정규식 중 최소 항성 높이로 정의된다.여기서 직관은 L이라는 언어가 항성 높이가 크면, 어떤 의미에서는 항성 높이가 낮은 "쉬운" 정규 표현으로 설명할 수 없기 때문에 본질적으로 복잡하다는 것이다.

예

정규 표현식의 항성 높이를 계산하는 것은 쉽지만 언어의 항성 높이를 결정하는 것은 때때로 까다로울 수 있다.그림의 경우 정규 표현식

${\displaystyle \textstyle \left(b\,\mid \,aa^{*}b\right)^{*}a^{*}}}$

알파벳 A = {a,b} 위에 별 높이 2가 있다.그러나 기술된 언어는 a로 끝나는 모든 단어의 집합일 뿐이다. 따라서 그 언어는 또한 표현으로 설명될 수 있다.

${\displaystyle \textstyle(a\,\mid \,b)^{*a}$

별 높이 1에 불과해이 언어가 실제로 항성 높이 1을 가지고 있다는 것을 증명하기 위해서는, 여전히 낮은 항성 높이의 규칙적인 표현으로 설명될 수 있다는 것을 배제할 필요가 있다.예를 들어, 이는 간접적인 증거에 의해 이루어질 수 있다.하나는 별높이 0의 언어가 아주 많은 단어만을 포함하고 있다는 것을 증명한다.고려 중인 언어는 무한하므로 별 키 0이 될 수 없다.

그룹 언어의 별 높이는 계산 가능하다. 예를 들어, a와 b의 발생 횟수가 일치하는 {a,b} 이상의ⁿ 언어의 별 높이는 n이다.^[1]

에그간의 정리

에그간(1963)은 정규 언어의 항성 높이에 대한 그의 정석적 연구에서 정규 표현, 유한한 오토마타, 지시된 그래프의 이론 사이의 관계를 설정했다.이후 몇 년 동안 이 관계는 에그간의 정리인 cf로 알려지게 되었다.사카로비치(2009년).우리는 그래프 이론과 오토마타 이론에서 몇 가지 개념을 떠올린다.

그래프 이론에서 지시된 그래프(화문) G = (V, E)의 주기 순위 r(G)는 다음과 같이 귀납적으로 정의된다.

• G가 반복적인 경우 r(G) = 0. 특히 G가 비어 있는 경우 적용된다.
• G가 강하게 연결되어 있고 E가 비어 있지 않으면

${\displaystyle \mathrm{r}}$( ${\displaystyle G}$)${\displaystyle }$= 1${\displaystyle }$+ ${\displaystyle \underset{}{v}}$ ${\displaystyle \underset{}{\in }}$ V ${\displaystyle \underset{}{}}$( G${\displaystyle }$- ${\displaystyle v}$)${\displaystyle }$, ${\$ r$(G)=1+\min _{v\in V}r($$G-v$$)\,},$ $여기$서 G -$v는$꼭지점 v와 v에서 시작되거나 끝나는 모든 가장자리의 삭제로 인한 디그라피이다$.$

• G가 강하게 연결되지 않은 경우, r(G)은 G의 모든 강하게 연결된 구성요소 중 최대 사이클 순위와 동일하다.

오토마타 이론에서, --transitions (--NFA)를 가진 비결정론적 유한 자동화는 다음과 같이 구성된 5-투플 (Q, ,, Δ, q₀, F)로 정의된다.

• 상태 Q의 유한 집합
• 입력 기호 symbols의 유한 집합
• 라벨이 부착된 가장자리 Δ(전환 관계)의 집합:Q × ( ( × {{{}) × Q. 여기서 ε은 빈말을 나타낸다.
• 초기 상태₀ Q ∈ Q
• 일련의 주들 F 수용 주들 F states Q.

Δ의^* 가장자리를 사용하여 F의 초기 상태 q에서₀ 최종 최종 상태까지의 지시 경로가 존재하는 경우, 경로를 따라 방문한 모든 라벨의 결합이 w를 산출하는 경우 w라는 단어가 ε-NFA에 의해 승인된다.자동자가 받아들인 σ에 대한^* 모든 단어 집합은 자동자 A가 받아들인 언어다.

상태가 Q로 설정된 비결정적 유한 자동자 A의 디그그래프 특성을 말할 때, 우리는 자연스럽게 디그그래프의 전환 관계에 의해 유도된 정점 세트 Q를 가진 디그그래프를 다룬다.이제 그 정리는 다음과 같이 명시되어 있다.

에그간의 정리:정규 언어 L의 항성 높이는 모든 비결정적 유한 자동자 사이의 최소 사이클 순위와 같으며, ε-변환 허용 L이다.

이 정리의 증명서는 에그간(1963년)이, 최근에는 사카로비치(2009년)가 제시한다.

일반화 항성 높이

위의 정의는 표준 연산자 집합 결합, 결합, 클레인 별만을 사용하여 알파벳 A의 요소로부터 정규 표현이 구축된다고 가정한다.일반화된 정규식은 정규식과 마찬가지로 정의되지만, 여기서도 집합보완 연산자가 허용된다(보완어는 항상 A보다 모든 단어의 집합에 대해 취한다).우리가 보완을 하는 것이 별의 높이를 증가시키지 않도록 정의를 바꾸면, 즉,

${\displaystyle \textstyle h\왼쪽(E^{c}\오른쪽)\,=\,h(E)}$

우리는 일반 언어 L의 일반화된 항성 높이를 L을 나타내는 모든 일반화된 정규식 중 최소 항성 높이로 정의할 수 있다.

참고로 별 높이 0의 언어는 아주 많은 단어만 포함할 수 있지만, 0의 일반화된 별 높이를 가진 무한한 언어가 존재한다.예를 들어, 정규식은

${\displaystyle \textstyle(a\,\mid \,b)^{*a}$

위의 예에서 본 바와 같이 일반화된 정규 표현으로 동등하게 설명할 수 있다.

${\displaystyle {\mathrm{\varnothing }}^{}}$ ${\displaystyle c^{}}$ ${\$

빈 세트의 보어는 정확히 A에 대한 모든 단어들의 집합이기 때문에따라서 알파벳 A에 끝나는 모든 단어의 집합은 항성 높이 1을 가지며, 일반화된 항성 높이는 0이다.

항성 높이 0이 일반화된 언어를 항성 없는 언어라고도 한다.언어 L은 그것의 구문론적 모노이드(Schützenberger (1965)가 aperiodic인 경우에만 항성이 없는 것으로 보일 수 있다.

참고 항목

• 항성 높이 문제
• 일반화된 항성 높이 문제.

참조

• Berstel, Jean; Reutenauer, Christophe (2011), Noncommutative rational series with applications, Encyclopedia of Mathematics and Its Applications, vol. 137, Cambridge: Cambridge University Press, ISBN 978-0-521-19022-0, Zbl 1250.68007
• Cohen, Rina S. (1971), "Techniques for establishing star height of regular sets", Theory of Computing Systems, 5 (2): 97–114, doi:10.1007/BF01702866, ISSN 1432-4350, S2CID 1970902, Zbl 0218.94028
• Cohen, Rina S.; Brzozowski, J.A. (1970), "General properties of star height of regular events", Journal of Computer and System Sciences, 4 (3): 260–280, doi:10.1016/S0022-0000(70)80024-1, ISSN 0022-0000, Zbl 0245.94038
• Eggan, Lawrence C. (1963), "Transition graphs and the star-height of regular events", Michigan Mathematical Journal, 10 (4): 385–397, doi:10.1307/mmj/1028998975, Zbl 0173.01504
• 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, Rockville, Maryland: Computer Science Press, ISBN 978-0-914894-69-8, Zbl 0487.68064
• Schützenberger, M.P. (1965), "On finite monoids having only trivial subgroups", Information and Control, 8 (2): 190–194, doi:10.1016/S0019-9958(65)90108-7, ISSN 0019-9958, Zbl 0131.02001