정규수문법

이론 컴퓨터 과학과 형식 언어 이론에서 정규 나무 문법은 지시된 나무, 또는 용어의 집합을 설명하는 형식적인 문법이다.^[1]규칙적인 단어 문법은 한 길의 나무들을 묘사하면서, 특별한 종류의 정규 나무 문법이라고 볼 수 있다.

정의

일반 나무 문법 G는 튜플에 의해 정의된다.

G = (N, σ, Z, P),

어디에

N은 유한한 비터미널 집합이다.
σ은 N으로부터 분리된 순위 알파벳(즉, 기호가 연관성을 갖는 알파벳)이다.
Z는 출발 비터미널이며, Z는 N이다.
P는 A → t형식의 유한 집합으로, A ∈ N, t ∈ T_Σ(N)는 연관 용어 대수, 즉_Σ σ N의 기호로 구성된 모든 나무의 집합으로, 비종단자는 무효로 간주된다.

나무의 유래

문법 G는 나무 집합을 암묵적으로 정의한다: 규칙 집합 P를 이용하여 Z로부터 파생될 수 있는 나무는 G가 기술한다고 한다.이 나무의 집합은 G의 언어로 알려져 있다. 보다 형식적으로 집합 T_Σ(N)에 대한 관계 ⇒_G을 다음과 같이 정의한다.

나무 t₁∈ T(N_Σ)는 다음과 같은 맥락 S와 생산(A→t) P가 있는 경우 t₂ ∈ T_Σ(N) (요컨대 t₁ ⇒_G t₂)로 단번에 파생될 수 있다.

t₁ = S[A] 및
t₂ = S[t]

여기서 문맥은 정확히 하나의 구멍이 있는 나무를 의미하며, 만약 S가 그러한 문맥이라면 S[t]는 나무 t를 S의 구멍에 채운 결과를 나타낸다.

G가 생성하는 트리 언어는 L(G) = { t ∈ T Z_Σ ⇒_G* t ⇒ t } 언어 입니다.

여기서 T는_Σ σ의 기호로 구성된 모든 나무의 집합을 나타내고, _G*⇒은 _Gof의 연속적인 적용을 나타낸다.

어떤 규칙적인 나무 문법에 의해 생성된 언어를 일반 나무 언어라고 부른다.

예

선형(왼쪽 위 표) 및 그래픽(주 그림) 표기법에서 G에서₁ 파생된 트리 예

G₁ = (N₁,N₁,NEG,Z₁,P₁), 여기서

N₁ = {Bool, BList }은(는) 비터미널 집합이지만
σ₁ = { true, false, nil, cons(,.) }은 우리의 순위 알파벳이며, 더미 인수에 의해 표시된 아리다(즉, 기호 cons는 arity 2)
Z₁ = BList는 우리의 시작점이 아니다.
세트 P는₁ 다음과 같은 제작으로 구성된다.
- Bool → false
- Bool → true
- BLISt → nil
- BLISt → cons(Bool,BLISt)

문법 G에서₁ 파생된 예는 다음과 같다.

BLISt ⇒ cons (Bool, Bool,BLISt) ⇒ cons(거짓말, cons(bool, bool)BList)) ) cons(허위, cons(진실,nil)).

이미지는 해당 파생 트리를 보여준다; 그것은 나무의 나무(주 그림)인 반면, 그라마어의 파생 트리는 문자열의 나무(왼쪽 위 테이블)이다.

G에₁ 의해 생성된 트리 언어는 부울 값의 모든 유한한 리스트의 집합이다. 즉, L(G₁)은 T와_Σ1 같다.문법 G는₁ 대수 데이터 유형 선언에 해당한다(표준 ML 프로그래밍 언어로).

  데이터타입 불     = 거짓의       진실의   데이터타입 블리스트     = 못을 박다       단점 의 불 * 블리스트

L(G₁)의 모든 멤버는 BList 유형의 Standard-ML 값에 해당한다.

다른 예로, 위에서₂ 비단어 집합과 알파벳을 사용하여 G = (N₁,N₁,NIGHT,BList1₁,P₂ ∪ P)로 하되, 다음과 같은 생산으로 구성된 P로₂ 생산 세트를 확장한다.

BList1 → cons(진실,BLISt)
BList1 → cons(거짓말,BList1)

언어 L(G₂)은 최소 한 번 이상 참이 포함된 모든 유한 부울 값 리스트의 집합이다.세트 L(G₂)은 표준 ML 또는 다른 기능 언어에서 데이터 형식 상대편이 없다.L(G₁)의 적절한 부분집합이다.위의 예시 용어는 L(G₂)에서도 나타나며, 다음과 같은 파생어가 보여준다.

BList1 ⇒ cons(거짓말,BList1) ⇒ cons(거짓말, cons(참말, 진실,BList)) ) cons(허위, cons(진실,nil)).

언어 속성

L₁, L이₂ 모두 일반 트리 언어라면, 트리는 L₁ l L₂₂, L₁₁ \ L도₂ 일반 트리 언어로서 L whether₂ L인지, L₁₁ = L인지를₂ 구분할 수 있다.

대체 특성화 및 기타 공식 언어와의 관계

일반 나무 문법은 일반 단어 문법의 일반화다.
일반 트리 언어는 상향 트리 오토마타(bottom-up tree automata)와 비결정론적인 하향 트리 오토마타(top-down tree automata)가 인정하는 언어이기도 하다.^[2]
Rajev Alur와 Parthasarathy Madhusdan은 정규 2진수 언어의 하위 클래스를 중첩된 단어와 눈에 띄게 푸시다운 언어에 연관시켰다.^[3]^[4]

적용들

일반 트리 그래머의 적용은 다음과 같다.

컴파일러 코드 생성^[5] 시 명령 선택
동일성(=)보다 공식을 우선시하는 1차 논리 이론의 결정 절차와 멤버십(membership^[6])을 유일한 술어로 설정
수학 집합에^[7] 대한 제약 조건 해결
유한 대수(항상 정규 트리 언어)^[8]에 대한 1차 논리학에서 표현할 수 있는 모든 진리의 집합
그래프 검색

참고 항목

제약 조건 설정 – 일반 트리 그래머의 일반화
나무접착문법

참조

^ "Regular tree grammars as a formalism for scope underspecification". CiteSeerX 10.1.1.164.5484. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
^ Comon, Hubert; Dauchet, Max; Gilleron, Remi; Löding, Christof; Jacquemard, Florent; Lugiez, Denis; Tison, Sophie; Tommasi, Marc (12 October 2007). "Tree Automata Techniques and Applications". Retrieved 25 January 2016.
^ Alur, R.; Madhusudan, P. (2004). "Visibly pushdown languages" (PDF). Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04. pp. 202–211. doi:10.1145/1007352.1007390. ISBN 978-1581138528. S2CID 7473479. 제4장 정리 5
^ Alur, R.; Madhusudan, P. (2009). "Adding nesting structure to words" (PDF). Journal of the ACM. 56 (3): 1–43. CiteSeerX 10.1.1.145.9971. doi:10.1145/1516512.1516518. S2CID 768006. 7장
^ Emmelmann, Helmut (1991). "Code Selection by Regularly Controlled Term Rewriting". Code Generation - Concepts, Tools, Techniques. Workshops in Computing. Springer. pp. 3–29.
^ Comon, Hubert (1990). "Equational Formulas in Order-Sorted Algebras". Proc. ICALP.
^ Gilleron, R.; Tison, S.; Tommasi, M. (1993). "Solving Systems of Set Constraints using Tree Automata". 10th Annual Symposium on Theoretical Aspects of Computer Science. LNCS. Vol. 665. Springer. pp. 505–514.
^ Burghardt, Jochen (2002). "Axiomatization of Finite Algebras". Advances in Artificial Intelligence. LNAI. Vol. 2479. Springer. pp. 222–234. arXiv:1403.7347. Bibcode:2014arXiv1403.7347B. ISBN 3-540-44185-9.
^ Ziv-Ukelson, Smoly (2016). Algorithms for Regular Tree Grammar Network Search and Their Application to Mining Human–viral Infection Patterns. J. of Comp. Bio. [1]

추가 읽기

일반 트리 그래머는 1968년에 이미 다음과 같이 설명되었다.
- Brainerd, W.S. (1968). "The Minimalization of Tree Automata". Information and Control. 13 (5): 484–491. doi:10.1016/s0019-9958(68)90917-0.
- Thatcher, J.W.; Wright, J.B. (1968). "Generalized Finite Automata Theory with an Application to a Decision Problem of Second-Order Logic". Mathematical Systems Theory. 2 (1): 57–81. doi:10.1007/BF01691346. S2CID 31513761.
나무 문법에 관한 책은 다음과 같다.
일반 트리 그래머의 알고리즘은 효율성 지향적 관점에서 다음과 같이 논의된다.
나무에서 무게까지의 매핑이 주어지면, 도날드 크누스의 Dijkstra의 최단 경로 알고리즘 일반화는 일반 트리 문법에 적용되어 각 비터미널에 대해 파생 가능한 트리의 최소 무게를 계산할 수 있다.이 정보를 바탕으로 가중치 순서로 언어를 열거하는 것이 간단하다.특히 무한의 최소 체중을 가진 어떤 비단어라도 빈 언어를 만들어 낸다.참조:
일반 나무 오토마타는 나무의 형제 노드들 사이의 동일성 테스트를 인정하기 위해 일반화되었다.참조:
더 깊은 노드들 사이에 동일성 테스트를 허용하면 불분명하게 된다.참조:

[1] "Regular tree grammars as a formalism for scope underspecification". CiteSeerX 10.1.1.164.5484. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)

[Comon-2] Comon, Hubert; Dauchet, Max; Gilleron, Remi; Löding, Christof; Jacquemard, Florent; Lugiez, Denis; Tison, Sophie; Tommasi, Marc (12 October 2007). "Tree Automata Techniques and Applications". Retrieved 25 January 2016.

[Alur2004-3] Alur, R.; Madhusudan, P. (2004). "Visibly pushdown languages" (PDF). Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04. pp. 202–211. doi:10.1145/1007352.1007390. ISBN 978-1581138528. S2CID 7473479. 제4장 정리 5

[Alur2009-4] Alur, R.; Madhusudan, P. (2009). "Adding nesting structure to words" (PDF). Journal of the ACM. 56 (3): 1–43. CiteSeerX 10.1.1.145.9971. doi:10.1145/1516512.1516518. S2CID 768006. 7장

[5] Emmelmann, Helmut (1991). "Code Selection by Regularly Controlled Term Rewriting". Code Generation - Concepts, Tools, Techniques. Workshops in Computing. Springer. pp. 3–29.

[6] Comon, Hubert (1990). "Equational Formulas in Order-Sorted Algebras". Proc. ICALP.

[7] Gilleron, R.; Tison, S.; Tommasi, M. (1993). "Solving Systems of Set Constraints using Tree Automata". 10th Annual Symposium on Theoretical Aspects of Computer Science. LNCS. Vol. 665. Springer. pp. 505–514.

[8] Burghardt, Jochen (2002). "Axiomatization of Finite Algebras". Advances in Artificial Intelligence. LNAI. Vol. 2479. Springer. pp. 222–234. arXiv:1403.7347. Bibcode:2014arXiv1403.7347B. ISBN 3-540-44185-9.

[9] Ziv-Ukelson, Smoly (2016). Algorithms for Regular Tree Grammar Network Search and Their Application to Mining Human–viral Infection Patterns. J. of Comp. Bio. [1]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Search