미계약문법

Noncontracting grammar

형식 언어 이론에서 문법은 모든 생산 규칙이 α → β 형식인 경우 비계약(또는 단조)이며 여기서 α와 β는 비터미널 및 단자 기호의 문자열이며, α의 길이는 β, α β의 길이보다 작거나 같으며, 즉 β는 α보다 짧지 않다. 문법은 e가 있을 수 있다면 본질적으로 비계약적이다.xception, 즉 규칙 S → ε 여기서 S는 시작 기호이고 ε 빈 문자열이며, 나아가 S는 어떤 규칙의 오른쪽에서 결코 발생하지 않는다.

계약되지 않은 문법의 어떤 규칙도 다시 쓰여지고 있는 문자열의 길이를 줄이지 않는다. 각 규칙들이 길이를 적절하게 증가시킨다면, 문법은 증가하는 문맥에 민감한 문법이라고 불린다.

역사

촘스키(1963)는 비계약 문법을 제1형 문법이라고 불렀고, 같은 작품에서는 문맥에 민감한 문법을 '제2형 문법'이라고 불렀으며, 이 두 가지가 약하게 동등하다는 것을 증명했다(본 작품에서는 '제4형'으로 정해졌다).[1] 1963년작 촘스키의 이 작품에서 유형 번호 매기기 제도는 오늘날 촘스키 계급으로 알려진 이전의 것과 일치하지 않는다. 왜냐하면 그는 약한 [세대]와 강한 [구조] 동등성의 구별을 강조하려고 노력했기 때문이다; 1959년 작품에서 그는 문맥에 민감한 문법을 나타내기 위해 "타입 1 문법"을 사용했고, 콘의 경우 "타입 2"를 사용했다.무문자의[2][3]

예

S → a b c
S → ASBC
cB → 비씨
bB → bb

이 문법은 시작 기호 S와 함께 { abcnnn : n },[4] 1}의 언어를 생성하는데, 이는 펌핑 보조기 때문에 맥락이 없는 것이 아니다.

같은 언어에 대한 문맥에 민감한 문법은 아래와 같다.

문맥에 민감한 문법으로 변환

모든 비계약 문법(N, σ, P, S)은 다음과 같이 문맥에 민감한 문법(N', σ, P', S)으로 변형될 수 있다.

  1. 모든 단자 기호 ∈ σ에 대해 새로운 비단자 기호 [a] ∈ N'과 새로운 규칙([a] → a) P'를 도입한다.
  2. P의 규칙에서, 모든 단자 기호 a를 해당 비단자 기호[a]로 교체한다. 결과적으로, 이 모든 규칙들은 X형식이야1...Xm → Y1...비터미널 Xi, Y, m³의j Yn.
  3. 각 규칙 X 바꾸기1...Xm → Y1...Yn(m >1 x 2m 규칙):[note 1]
X1 X2 ... Xm-1 Xm → Z1 X2 ... Xm-1 Xm
Z1 X2 ... Xm-1 Xm → Z1 Z2 ... Xm-1 Xm
:
Z1 Z2 ... Xm-1 Xm → Z1 Z2 ... Zm-1 Xm
Z1 Z2 ... Zm-1 Xm → Z1 Z2 ... Zm-1 Zm Ym+1 ... Yn
Z1 Z2 ... Zm-1 Zm Ym+1 ... Yn → Y1 Z2 ... Zm-1 Zm Ym+1 ... Yn
Y1 Z2 ... Zm-1 Zm Ym+1 ... Yn → Y1 Y2 ... Zm-1 Zm Ym+1 ... Yn
:
Y1 Y2 ... Zm-1 Zm Ym+1 ... Yn → Y1 Y2 ... Ym-1 Zm Ym+1 ... Yn
Y1 Y2 ... Ym-1 Zm Ym+1 ... Yn → Y1 Y2 ... Ym-1 Ym Ym+1 ... Yn
여기서 각 Zi ∈ N'은 다른 곳에서 발생하지 않는 새로운 비터미널이다.[5][6]

예를 들어, {abcnnn n 1 1 }에 대한 위의 비계약 문법은 동일한 언어에 대해 다음과 같은 문맥 민감 문법(시작 기호 S 포함)으로 이어진다.

[a] → a 1단계부터
[b] → b 1단계부터
[c] → c 1단계부터
S → [a] [b] [c] 2단계부터 변경되지 않음
S → [a] S B [c] 2단계부터 변경되지 않음
[c] B → B [c] 2단계부터 아래 추가 수정
[c] B → Z1 B 3단계에서 위로부터 수정됨
Z1 B → Z1 Z2 3단계에서 위로부터 수정됨
Z1 Z2 → B Z2 3단계에서 위로부터 수정됨
B Z2 → B [c] 3단계에서 위로부터 수정됨
[b] B → [b] [b] 2단계부터 아래 추가 수정
[b] B → Z3 B 3단계에서 위로부터 수정됨
Z3 B → Z3 Z4 3단계에서 위로부터 수정됨
Z3 Z4 → [b] Z4 3단계에서 위로부터 수정됨
[b] Z4 → [b] [b] 3단계에서 위로부터 수정됨

표현력

마찬가지로, 어떤 계약되지 않은 문법을 쿠로다 정상적인 형태로 가져오는 쉬운 절차가 있다.[7][8] 반대로 모든 문맥에 민감한 문법과 모든 쿠로다 정상형 문법도 사소한 것으로는 계약되지 않은 문법이다. 따라서 계약되지 않은 문법, 쿠로다 정상 형태의 문법, 문맥에 민감한 문법 등은 표현력이 동일하다. 정확히 말하면, 비계약형 그래머는 빈 문자열을 포함하지 않는 문맥 민감 언어를 정확히 기술하는 반면, 본질적으로 비계약형 그래머는 문맥 민감 언어의 집합을 정확히 기술한다.

참고 항목

메모들

  1. ^ 편의상 좌우의 비콘텍스트 부분은 볼드체로 표시한다.

참조

  1. ^ Noam Chomsky (1963). "Formal properties of grammar". In R.D. Luce and R.R. Bush and E. Galanter (ed.). Handbook of Mathematical Psychology. Vol. II. New York: Wiley. pp. 323–418. 여기: 360–363 페이지 및 367 페이지
  2. ^ 촘스키, 1959a. 그래머의 어떤 형식적인 특성에 대해서. 정보 및 제어 2: 137–67. (정의의 경우 141–42)
  3. ^ Willem J. M. Levelt (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. pp. 125–126. ISBN 978-90-272-3250-2.
  4. ^ Mateescu & Salomaa(1997), 사례 2.1, 페이지 188
  5. ^ 마테스쿠 & 살로마(1997), 정리 2.1, 페이지 187
  6. ^ John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. 연습 9.9 페이지 230. 2003년판에서는 비계약/문맥민감 언어에 관한 장이 생략되었다.
  7. ^ Sige-Yuki Kuroda (June 1964). "Classes of languages and linear-bounded automata". Information and Control. 7 (2): 207–223. doi:10.1016/s0019-9958(64)90120-2.
  8. ^ 마테스쿠 & 살로마(1997), 정리 2.2, 페이지 190
  • Book, R. V. (1973). "On the structure of context-sensitive grammars". International Journal of Computer & Information Sciences. 2 (2): 129–139. doi:10.1007/BF00976059. hdl:2060/19710024701. S2CID 31699138.
  • Mateescu, Alexandru; Salomaa, Arto (1997). "Chapter 4: Aspects of Classical Language Theory". In Rozenberg, Grzegorz; Salomaa, Arto (eds.). Handbook of Formal Languages. Volume I: Word, language, grammar. Springer-Verlag. pp. 175–252. ISBN 3-540-61486-9.