정규 언어

이론 컴퓨터 과학과 형식 언어 이론에서 정규식에 의해, 이론적인 컴퓨터 과학의 엄격한 면(로 인식할 수 있는 기능을 증가 되었다 많은 현대적인 정규식 엔진과 대조하여로 정의 될 수 있지만, 정규 언어(또한 합리적인 언어라고 불리는)[1][2] 공식적인 언어이다. non의(정규어)

또는 정규언어는 유한오토마톤에 의해 인식되는 언어로서 정의될 수 있다.정규식과 유한 오토마타의 등가는 클린의 정리^[3](미국 수학자 스티븐 콜 클린의 이름을 따서)로 알려져 있다.촘스키 계층에서 정규 언어는 타입 3 문법에 의해 생성된 언어입니다.

형식적 정의

알파벳 σ 위의 정규 언어 모음은 다음과 같이 재귀적으로 정의됩니다.

• 빈 언어 ø는 정규 언어입니다.
• 각 ∈(a는 σ에 속함)에 대해 싱글톤 언어 {a}는 정규 언어입니다.
• A가 정규 언어인 경우 A*(Kleene star)는 정규 언어입니다.이로 인해 빈 문자열 언어 {}}도 규칙적입니다.
• A와 B가 정규 언어일 경우 A b B(연합)와 A • B(연결)는 정규 언어입니다.
• σ를 넘는 다른 언어는 정규적이지 않습니다.

정규 표현의 구문 및 의미에 대해서는 정규 표현을 참조하십시오.

예

모든 유한 언어는 정규 언어이며, 특히 빈 문자열 언어 {timeout} = ö*는 정규 언어입니다.기타 대표적인 예로는 짝수 as를 포함하는 알파벳 {a, b} 위의 모든 문자열로 구성된 언어 또는 형식의 모든 문자열로 구성된 언어(여러 b 뒤에 여러 bs)가 있습니다.

정규적이지 않은 언어의 간단한 예는 문자열ⁿⁿ 세트{ ab n 0 0 }^[4]입니다.직관적으로 유한 오토마톤은 유한한 메모리를 가지고 있고 정확한 a의 수를 기억할 수 없기 때문에 유한 오토마톤으로 인식할 수 없다.이 사실을 엄격하게 증명하기 위한 기술은 다음과 같다.

등가 형식주의

일반 언어는 다음과 같은 동등한 속성을 충족합니다.

1. (위의 정의에 따라) 정규 표현의 언어입니다.
2. 그것은 비결정론적 유한 오토마톤(NFA)^{[note 1][note 2]}에 의해 받아들여지는 언어이다.
3. 그것은 결정론적 유한 오토마톤(DFA)^{[note 3][note 4]}에 의해 받아들여지는 언어이다.
4. 그것은^{[note 5][note 6]} 정규 문법에 의해 생성될 수 있다
5. 그것은 교대 유한 자동화에 의해 받아들여지는 언어이다
6. 그것은 쌍방향 유한 자동화에 의해 받아들여지는 언어이다
7. 접두사 문법에 의해 생성될 수 있다
8. 그것은 읽기 전용 튜링 기계로 받아들여질 수 있다
9. 그것은 단수 2차 논리(Büchi-Elgot-Trahtenbrot 정리)^[5]로 정의될 수 있다.
10. 그것은 어떤 유한 구문적 모노이드 M에 의해 인식되며, 이것은 그것이 모노이드 동형사상 f: δ^* → 알파벳^{[note 7]} 상의 자유 모노이드로부터의 M에서 유한 모노이드 M의 부분 집합 S의 초기 이미지 { w δ^* δ f(w) δ S }임을 의미한다.
11. 그것의 구문적 합치의 동등성 클래스의 수는 ^{[note 8][note 9]}유한하다.(이 숫자는 최소 결정론적 유한 오토마톤 수용 L의 상태 수와 같습니다.)

속성 10과 11은 정규 언어를 정의하기 위한 순수 대수적 접근법이다.모노이드 M ⊆ ⊆ σ^* a a a a a a a a a a a a a a a a a a a a a a a a a a이 경우 M에 대한 동등성은 인식 가능한 언어의 개념으로 이어집니다.

일부 저자는 정규 언어의 대체 정의로 "1"과 다른 위의 속성 중 하나를 사용합니다.

위의 등가물들, 특히 처음 네 개의 형식론들 중 일부는 교과서에서 클라인의 정리라고 불린다.정확히 어떤 것이 (또는 어떤 부분집합이) 그렇게 불리는지는 저자들마다 다릅니다.한 교과서는 정규식과 NFA의 동등성을 "클린의 정리"^[6]라고 부른다.또 다른 교과서는 정규식과 DFA의 등가성을 클린의 ^[7]정리라고 부른다.다른 두 교과서는 먼저 NFA와 DFA의 표현적 등가성을 증명한 후 "클린의 정리"를 정규 표현과 유한 오토마타 사이의 등가성으로 기술한다.^[2][8]언어 지향 텍스트는 먼저 정규 문법을 DFA 및 NFA와 동일시하고, 이들 중 하나에 의해 생성된 언어를 정규라고 부르며, 그 후에 정규 표현을 도입하여 "합리적인 언어"를 기술하고, 마지막으로 "클린 정리"를 정규 ^[9]언어와 합리적인 언어의 일치로 기술합니다.다른 저자는 단순히 "합리적 표현"과 "정규적 표현"을 동의어로 정의하며 "합리적 언어"와 "정규적 언어"^[1][2]에 대해서도 동일한 작업을 수행합니다.

분명히 "정기적"이라는 용어는 클린이 "정기적 사건"을 소개하며 "좀 더 서술적인 ^[10]용어에 대한 어떠한 제안도" 환영한 1951년 기술 보고서에서 유래했다.노암 촘스키는 1959년에 쓴 그의 정석 기사에서 처음에는 "정기적"이라는 용어를 다른 의미로 사용했지만(오늘날 ^[11]"촘스키 정상형"이라고 불리는 것을 지칭함), 그의 "확실한 국가 언어"가 클라인의 "정기적 사건"^[12]과 동등하다는 것을 알아차렸다.

닫힘 속성

정규언어는 다양한 조작으로 닫힙니다.즉, 언어 K와 L이 정규인 경우에는 다음 조작의 결과도 마찬가지입니다.

• 집합 이론 부울 연산: 결합 K k L, 교차 K l L 및 보완 L. 따라서 상대 보완 K - ^[13]L.
• 정상 동작: K $aten{\displaystyle }$ L, 연결 K$l$ L$,$ K \ displaystyle^* K$\circ$ L$.$^[14]
• 3인방 연산: 문자열 동형, 역 문자열 동형 및 정규 언어와의 교차.그 결과 이들은 정규 언어를 사용하는 몫 K/L과 같이 임의의 유한 상태 변환 하에서 닫힙니다.또한 정규언어는 임의의 언어를 사용하는 인용문 아래에 닫힙니다.L이 정규라면 L/K는 임의의 ^{[citation needed]}K에 대해 정규입니다.
• 역(^[15]또는^R 거울상) L. L을 인식하는 비결정론적 유한 오토마톤이 주어졌을 때, L에^R 대한 오토마톤은 모든 전환을 반전시키고 시작 및 종료 상태를 교환함으로써 얻을 수 있다.이로 인해 여러 시작 상태가 발생할 수 있습니다. "-transitions를 사용하여 결합할 수 있습니다.

결정 가능성 속성

두 개의 결정론적 유한 오토마타 A와 B가 주어졌을 때, 그들이 ^[16]같은 언어를 받아들일지는 결정될 수 없다.그 결과, 상기의 폐색 특성을 이용해, 다음의 문제는, 각각 인정 언어_A L과 L을_B 가지는 임의의 결정론적 유한 오토마타 A와 B에 대해서도 판정할 수 있다.

• 콘테인먼트: L l_B L_A?^{[note 10]}
• 연결 끊김: L l_B L = {}입니까_A?
• 비어 있음: L = {}입니까_A?
• 범용성: L_A = σ^*?
• 멤버십 : σ^* a 、 l_B L?

정규식의 경우 보편성 문제는 단일톤 ^[17]알파벳에 대해 이미 NP-완전입니다.알파벳이 큰 경우 이 문제는 ^[18]PSPACE-complete입니다."A"가² "AA"와 같은 것을 나타내는 제곱 연산자를 허용하도록 정규 표현을 확장하면, 여전히 정규 언어만 기술할 수 있지만, 보편성 문제는 지수 공간 ^[19][20][21]하한을 가지며, 사실상 다항 시간 ^[22]감소에 관한 지수 공간에 대해 완전하다.

복잡도 결과

계산 복잡도 이론에서, 모든 정규 언어의 복잡도 클래스는 때때로 RECULAR 또는 REG로 불리며 DSPACE(O(1)와 동일하며, 이는 일정한 공간에서 해결할 수 있는 결정 문제(사용된 공간은 입력 크기와 독립적이다)이다.RECORGIAL ac⁰ AC는 입력 내의 1비트의 수가 짝수인지 홀수인지를 판별하는 패리티 문제를 포함하고 있으며 이 문제는 ^[23]AC에 없습니다⁰.한편, Palindrome의 비정규 언어 또는 비정규${\displaystyle }$언어 {${\displaystyle {}^{}{\mathrm{}}^{}}$ n 1${\displaystyle {}^{}{n}^{}}$ : n${\displaystyle n\mathbb{}}$ N$$} { $displaystyle$\ { $0$^ {$n }1^$ { n } : $n$ \ $in$ \$mathbb${ N$$} \ }는$$ 모두 ^[24]AC로 인식할⁰ 수 있기 때문에 RECULARGUAL에는 AC가 포함되어⁰ 있지 않습니다.

언어가 정규 언어가 아닌 경우 인식하기 위해서는 최소 δ(log log n)의 공간이 필요합니다(n은 입력 ^[25]크기입니다).즉, DSPACE(o(log log n))는 정규 언어의 클래스입니다.실제로 대부분의 비정규 문제는 최소한 로그 공간을 차지하는 기계에 의해 해결됩니다.

촘스키 계층 내 위치

촘스키 계층에서 정규 언어를 찾기 위해서는 모든 정규 언어가 문맥에 구애받지 않는다는 것을 알 수 있습니다.예를 들어, b와 같은 수의 a를 가진 모든 문자열로 구성된 언어는 문맥이 없지만 정규적이지 않습니다.언어가 규칙적이지 않다는 것을 증명하기 위해, 사람들은 종종 마이힐-네로드 정리와 펌핑 보조정리를 사용한다.다른 방법으로는 정규^[26] 언어의 폐쇄 속성을 사용하거나 콜모고로프 ^[27]복잡성을 정량화하는 방법이 있습니다.

정규 언어의 중요한 서브클래스는 다음과 같습니다.

• 한정된 언어,^[28] 한정된 수의 단어만 포함하는 언어.이들은 정규 언어이며, 언어 내의 모든 단어를 합친 정규 표현을 만들 수 있습니다.
• 별 없는 언어, 빈 기호, 문자, 연결 및 모든 부울 연산자(집합 대수 참조)로 구성된 정규식으로 설명할 수 있는 언어: 이 클래스는 모든 유한 ^[29]언어를 포함합니다.

정규 언어의 단어 수

${\displaystyle s_{}L}$ (${\displaystyle }$n )$${ $display style$s _ {$L （$ n ） } $n$$$、 L { $display style$ L$$}의 길이$$n { $display style$ n$$}의$$ 단어 수를 나타냅니다. L의 일반 생성 함수는 공식 멱급수입니다.

${\displaystyle S_{L}(z)=\sum _{n\geq 0}s_{L}(n)z^{n}\ .}$

언어 L의 생성 함수는 L이 ^[30]규칙적인 경우 합리적인 함수이다.따라서 모든 정규 $언어{\displaystyle }$L(\$displaystyle$ L$)$에 대해 $시퀀스{\displaystyle {}_{}}$ s $)$ n${\displaystyle 0_{}}$0$(\$$displaystyle s_{L}_{n\geq$0})은$$ 항상 반복됩니다.${\displaystyle {즉\mathrm{}}_{}}$, 정수 $n{\displaystyle {}_{}}$(\$displaystyle n_{$0$\}),$ 복소수 $(\$ style$n_0$ $_lda,$ {$1})$이 존재합니다.및 ${\displaystyle {복잡한\mathrm{}}_{}}$ $다항식{\displaystyle {}_{}}$ p${\displaystyle {}_{}1}$ (${\displaystyle }$x${\displaystyle }$) , ${\displaystyle ...}$ , ${\displaystyle p_{}}$k (${\displaystyle }$$x$$$) \ $displaystyle p_{1}$ $($x$$) , \$ldots$, , , $p_{$$k$} $($$x$ )$$such$$ n${\displaystyle {}_{}}$ 0$$n n \ $displaystyle$$$n \ $geq n$_ { $0$$$} the$$ n$$every n $every$ l$n{\displaystyle }$ $n$$$n$$ l $n{\displaystyle }$ l n l of$$ n l n n n n n of of of ${\displaystyle {of}_{}}$ of of of of of n n of of of l of of of of${\displaystyle n}$) ${\displaystyle {1\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$n + ${\displaystyle +}$ + ${\displaystyle p_{}}$ (${\displaystyle n}$ ) ${\displaystyle k_{}^{}}$ ${\displaystyle {}_{}^{}}$n { $displaystyle s$_ { $L$} ( n ) =$p$_ { $1$（ $n$) \ $lambda$_ { $n }$ + \ $lambda _$ { $n$} + $p$_ { $k$（ $n$）$$^{[31][32][33][34]}。

따라서 L ${\$ { $displaystyle$ L$\}$에서 주어진 $길이$의 단어를 세는 것으로 특정 $언어{\displaystyle {}^{}}$ L ${\$ { $displaystyle$ L$$}의$$ 불규칙성을 증명할 수 있습니다.예를 들어 균형 괄호 문자열의 Dick 언어를 생각해 보십시오.다이크 언어의 $길이{\displaystyle \mathrm{}}$ $({style 2n$$})$ 단어 수는 카탈로니아 ${\displaystyle {숫자}_{}Cn\frac{{\mathrm{}}^{}}{}}$~${\displaystyle \frac{{4n\mathrm{}}^{}}{}}$ 3$2$ 와 $({$^{$n}}{\sqrt$ {\pi$$$}}).$이 값은 p$display$) $styledisplay$ p$(n)$ ${\displaystyle {}^{}}$이 $아닙니다{\displaystyle }$.dyck 언어일부 고유값 ${\displaystyle {\delta }_{}}$ i$\$ _${i}$의 크기가 같을 수 있으므로 주의해야 합니다.예를 들어 모든 짝수 바이너리 워드의 언어에서 $길이{\displaystyle }$n{$displaystyle$ n$}$의 단어 수는 p${\displaystyle (n)}$ ${\$ ${\displaystyle n^{}}$ { $displaystyle p(n$)\$lambda ^{n$ 형식이 $아니지만{\displaystyle }$ 짝수 또는 홀수 길이의 단어 수는 이 형식입니다.대응되는 고유값은 $일반적$으로 2,${\displaystyle }$-$$2 \ $displaystyle$ 2, 2 입니다$.$gular language는 $항상$ d$\$$displaystyle$$$d가 존재하며$,$ $모든{\displaystyle }$ \${\displaystyle \mathrm{displaystyle}}$ a$\backslash$displaystyle dm${\displaystyle }$+ $\displaystyle$dm +$a$$\$^[35]$lambda_{a}$의 단어$$ 수가 $점근적$으로 ${\displaystyle {{Ca}_{}}^{}}$이다.

언어 L의^[30] 제타 함수는

$\displaystyle \zeta _{L}(z)=\exp \leftsum _{n\geq 0}s_{L}(n){\frac {z^{n}}\right}\ .}$

정규 언어의 제타 함수는 일반적인 이성이 아니지만 임의의 순환 언어의 제타 함수는 이성이다.^[36][37]

일반화

정규언어의 개념은 무한단어(ata-automata 참조)와 나무(트리 오토마톤 참조)로 일반화되었다.

유리 집합은 (일반/합리 언어의) 개념을 반드시 자유롭지 않은 모노이드로 일반화한다.마찬가지로 (유한 오토마톤에 의한) 인식 가능한 언어의 개념은 반드시 자유롭지 않은 모노이드 위에 인식 가능한 집합이라는 이름을 가지고 있다.하워드 스트라우빙은 이러한 사실과 관련하여 "정규어"라는 용어는 조금 유감스럽다고 지적한다.에일렌버그의 논문의^[38] 영향을 받은 논문들은 오토마타의 행동을 나타내는 "인식 가능한 언어" 또는 정규 표현과 합리적 멱급수 사이의 중요한 유사점을 나타내는 "합리적인 언어"라는 용어를 종종 사용한다.(사실, 아일렌버그는 임의의 모노이드의 합리적이고 인식 가능한 부분 집합을 정의한다; 일반적으로 두 개념은 일치하지 않는다.)이 용어는 동기부여가 더 좋기는 하지만 실제로 통용되는 경우는 없으며, "일반 언어"는 거의 ^[39]보편적으로 사용되고 있습니다.

유리 급수는 또 다른 일반화이며, 이번에는 세미링에 대한 공식 멱급수 맥락에서 볼 수 있습니다.이 접근방식은 가중치 있는 합리적 표현과 가중치 있는 자동화를 일으킨다.이 대수적 맥락에서 정규 언어(부울 가중치 유리 표현식에 해당)는 일반적으로 유리 ^[40][41]언어라고 불립니다.또한 이 맥락에서, 클라이네의 정리는 클라이네-슈첸베르거 정리라고 불리는 일반화를 발견한다.

예로부터 배우다

메모들

레퍼런스

추가 정보

• 클린, S.C:신경망과 유한 오토마타의 사건 표현.입력: 섀넌, C.E., 매카시, J. (eds)오토마타 연구, 페이지 3-41.Princeton University Press, Princeton (1956) 동명의 1951 RM704의 RAND Corporation 보고서를 약간 수정한 것입니다.
• Sakarovitch, J (1987). "Kleene's theorem revisited". Trends, Techniques, and Problems in Theoretical Computer Science. Lecture Notes in Computer Science. Vol. 1987. pp. 39–50. doi:10.1007/3540185356_29. ISBN 978-3-540-18535-2.

외부 링크

• Wikimedia Commons의 정규 언어 관련 미디어
• 복잡성 동물원: 클래스 REG