L-system

3. L-system의 구조

L-system은 일반적으로 다음과 같은 네 개의 튜플로 정의되는 "파라메트릭 L-system"으로 알려져 있다.^[3]

: '''G''' = {''V'', ''S'', ω, ''P''},

각 요소는 다음을 의미한다.

• '''V''' (문자): 치환 규칙('''P''')에 의해 순차적으로 바뀌어가는 변수의 집합이다. L-system의 재귀적인 반복이 진행될 때, 결과 문자열은 이 '''V'''의 요소들로 구성된다.
• '''S''' (상수): 계산 과정에서 변화하지 않는 상수의 집합이다. 일부 정의에서는 상수를 '''V''' 알파벳에 포함시키기도 한다.
• '''ω''' (공리 또는 시작 문자열): 시스템의 초기 상태를 나타내는 문자열로, '''V'''의 요소들로 이루어진다.
• '''P''' (치환 규칙): '''V'''의 요소들을 변화시키는 치환 규칙의 집합이다. 각 규칙은 예를 들어 `A → AB`와 같이 치환 전 문자열(전임자)과 치환 후 문자열(후임자)의 쌍으로 기술된다. '''P'''에 명시적인 규칙이 없는 문자는 자신으로 치환되는 항등 규칙(예: `B → B`)을 따른다고 가정하며, 이런 문자를 상수라고 부르기도 한다.

• 치환 규칙이 주변 문자를 고려하지 않고 개별 문자에만 적용될 경우, 해당 L-system은 문맥 자유 언어와 관련되며 문맥 자유 L-system이라 한다.
• 치환 규칙이 인접 문자와의 관계를 고려하는 경우, 문맥 의존 언어와 관련되며 문맥 의존 L-system이라 한다.
• 각 문자에 대해 적용될 치환 규칙이 유일하게 정해진 경우, L-system은 결정론적이라고 하며, 특히 문맥 자유이면서 결정론적인 시스템을 D0L 시스템(deterministic context-free L-system)이라고 부른다.
• 각 문자에 대해 여러 치환 규칙이 존재하고 특정 확률에 따라 규칙이 선택되어 적용되는 경우, 확률론적 L-system이라고 한다.

4. L-system의 응용

L-system은 자기 유사성을 가지는 복잡한 구조를 효율적으로 생성하는 규칙 기반 시스템이다. 이러한 특성 덕분에 컴퓨터 그래픽스 분야에서 식물 모델링이나 프랙탈 생성 등에 널리 활용되며, 그 외에도 다양한 분야에서 응용 가능성을 보여주고 있다.

4. 1. 그래픽 응용

5. L-system의 예시

L-system은 간단한 규칙으로부터 복잡한 구조를 생성하는 능력 덕분에 다양한 분야에서 모델링 도구로 활용된다. 대표적인 예시들은 다음과 같다.

• 조류(Algae): 린덴마이어가 L-system을 처음 고안했을 때 사용한 모델로, 조류 세포의 성장 과정을 모방한다.
• 피보나치 수열(Fibonacci sequence): 특정 규칙을 통해 생성되는 문자열의 길이가 피보나치 수열을 따르는 것을 보여준다.
• 칸토어 집합(Cantor set): 선분을 반복적으로 3등분하고 가운데 부분을 제거하는 과정을 L-system으로 표현하여 칸토어 집합을 생성한다.
• 코흐 곡선(Koch curve): 프랙탈 도형인 코흐 곡선의 생성을 L-system 규칙과 터틀 그래픽스를 이용해 보여준다.
• 시에르핀스키 삼각형(Sierpinski triangle): 또 다른 유명한 프랙탈인 시에르핀스키 삼각형을 생성하는 여러 L-system 규칙을 소개한다.
• 드래곤 곡선(Dragon curve): 자기 유사성을 가지는 드래곤 곡선을 L-system으로 생성하는 방법을 설명한다.
• 프랙탈 식물(Fractal plant): L-system을 이용하여 나무나 풀과 같은 식물의 복잡한 분지 구조나 잎의 배열 등을 모델링하는 예시를 보여준다. Barnsley fern과 같은 특정 프랙탈 식물도 L-system으로 생성할 수 있다.

5. 1. 조류(Algae)

• 변수: A, B
• 상수: 없음
• 공리 (시작 상태): A
• 규칙:
• * (A → AB)
• * (B → A)

• ''n'' = 0 : A
• ''n'' = 1 : AB
• ''n'' = 2 : ABA
• ''n'' = 3 : ABAAB
• ''n'' = 4 : ABAABABA
• ''n'' = 5 : ABAABABAABAAB
• ''n'' = 6 : ABAABABAABAABABAABABA
• ''n'' = 7 : ABAABABAABAABABAABABAABAABABAABAAB

5. 2. 피보나치 수열(Fibonacci sequence)

• 변수 (V): A, B
• 상수 (S): 없음
• 시작 문자열 (ω): A
• 규칙 (P): (A → AB), (B → A)

각 세대별 문자열의 길이를 보면 1, 2, 3, 5, 8, ... 와 같이 피보나치 수열이 나타나는 것을 확인할 수 있다. (단, 이 예시에서는 시작 문자열 A 때문에 피보나치 수열의 첫 번째 1은 건너뛴 형태이다.) 만약 첫 번째 1부터 시작하는 수열을 원한다면, 시작 문자열을 'B'로 설정하면 된다.

생성된 문자열은 피보나치 워드의 시퀀스와 일치한다. 각 문자열에서 왼쪽 끝부터 ''k''번째 문자를 계산할 때, 황금비율의 배수가 $(k-1,\; k)$ 구간 내에 속하는지에 따라 값이 결정된다. 또한, 문자 A와 B의 비율 역시 황금비율에 수렴하는 특징을 보인다. 만약 규칙을 (A → BA), (B → A)로 변경하면, 생성되는 문자열은 원래 문자열의 좌우가 뒤집힌 형태가 되지만, 각 문자열의 길이는 동일하게 피보나치 수열을 따른다.

'''예시 2:'''

• 변수 (V): A, B
• 상수 (S): 없음
• 시작 문자열 (ω): A
• 규칙 (P): (A → B), (B → AB)

이 경우, 각 문자열의 길이는 1, 1, 2, 3, 5, 8, 13, 21, ... 로 피보나치 수열 전체를 보여준다. 이 예시 역시 규칙 (B → AB)를 (B → BA)로 바꾸어도 문자열의 길이는 동일하게 피보나치 수열을 따른다.

두 번째 예시에서 생성된 시퀀스는 $G(n)=G(n-1)G(n-2)$ 관계를 만족하기 때문에 지역 연결 시퀀스이다. 여기서 $G(n)$은 ''n''번째 세대의 문자열을 의미한다.

5. 3. 칸토어 집합(Cantor set)

• '''변수''': A, B
• '''상수''': 없음
• '''시작 문자열''' (axiom 또는 initiator): A
• '''규칙''' (production rules):
• * A → ABA
• * B → BBB

• '''V''' (변수 집합): {A, B}
• '''S''' (상수 집합): 없음
• '''ω''' (시작 문자열): A
• '''P''' (규칙 집합): {(A → ABA), (B → BBB)}

• ''n'' = 0 : A
• ''n'' = 1 : ABA
• ''n'' = 2 : ABABBBABA
• ''n'' = 3 : ABABBBABABBBBBBBBBABABBBABA
• ...

5. 4. 코흐 곡선(Koch curve)

• '''변수''': F
• '''상수''': +, -
• '''시작''' (공리): F
• '''규칙''': F → F+F-F-F+F

• F: 앞으로 선을 그린다.
• +: 왼쪽으로 90° 회전한다.
• -: 오른쪽으로 90° 회전한다.

• ''n'' = 0:
• * 문자열: F
• * --

• ''n'' = 1:
• * 문자열: F+F-F-F+F
• * --

• ''n'' = 2:
• * 문자열: F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F
• * --

• ''n'' = 3:
• * 문자열: F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F-F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F-F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F
• * --

5. 5. 시에르핀스키 삼각형(Sierpinski triangle)

• '''변수''': F, G
• '''상수''': +, −
• '''시작''': F−G−G
• '''규칙''': (F → F−G+F+G−F), (G → GG)
• '''각도''': 120°

• '''변수''': A, B
• '''상수''': +, −
• '''시작''': A
• '''규칙''': (A → B−A−B), (B → A+B+A)
• '''각도''': 60°

5. 6. 드래곤 곡선(Dragon curve)

5. 7. 프랙탈 식물(Fractal plant)

• '''변수''': 0, 1
• '''상수''': "[", "]"
• '''공리''': 0
• '''규칙''': (1 → 11), (0 → 1[0]0)

문자열은 재귀가 반복될수록 크기와 복잡성이 빠르게 증가하는 것을 볼 수 있다. 이 문자열은 각 기호에 특정 그래픽 연산을 할당하여 터틀 그래픽스를 사용해 그림으로 나타낼 수 있다. 예를 들어, 위 샘플에서 터틀 그래픽스는 다음과 같은 지침을 따를 수 있다.

• 0: 잎으로 끝나는 선분을 그린다.
• 1: 선분을 그린다.
• [: 위치와 각도를 저장하고 왼쪽으로 45도 회전한다.
• ]: 저장된 위치와 각도를 복원하고 오른쪽으로 45도 회전한다.

• '''변수''' : X F
• '''상수''' : + − [ ]
• '''시작''' : X
• '''규칙''' : (X → F+[[X]-X]-F[-FX]+X), (F → FF)
• '''각도''' : 25°

• F: 앞으로 선을 그린다.
• −: 오른쪽으로 25° 회전한다.
• +: 왼쪽으로 25° 회전한다.
• X: 아무런 그리기 동작을 하지 않으며, 곡선의 형태를 만드는 데 사용된다.
• [: 현재 위치와 각도를 스택에 저장(push)한다.
• ]: 스택에서 가장 최근에 저장된 위치와 각도를 복원(pop)한다.

• 지이류 또는 선태식물 예시:

• 초본 작도 예시:

• 목본 작도 예시:

• 원생동물 등 유사 구조 예시:

6. L-system의 확장

L-시스템 규칙의 재귀적 특성은 자기 유사성으로 이어지며, 이를 통해 프랙탈과 같은 복잡한 형태를 쉽게 표현할 수 있다. 이러한 특징 덕분에 식물 모델링이나 자연스러운 유기체 형태 생성, 인공 생명 연구 등 다양한 분야에서 활용된다.

L-시스템은 일반적으로 다음과 같이 정의되는 '''매개변수 L-시스템'''(Parametric L-system)으로 설명될 수 있다.

:'''G''' = (''V'', ω, ''P'')

여기서 각 요소는 다음을 의미한다.

• '''V''' (알파벳): 시스템에서 사용되는 기호의 집합으로, 대체될 수 있는 변수(''variable'')와 대체될 수 없는 상수(''constant'') 또는 터미널(''terminal'')을 포함한다.
• '''ω''' (시작 문자열): 시스템의 초기 상태를 나타내는 기호 문자열이다. 공리(''axiom'') 또는 개시자(''initiator'')라고도 불린다.
• '''P''' (생산 규칙): 변수를 다른 변수나 상수의 조합으로 대체하는 규칙들의 집합이다. 각 규칙은 전임자(''predecessor'')와 후임자(''successor'') 문자열로 구성된다. 규칙에 정의되지 않은 기호는 자신으로 변환되는 항등 규칙(A → A)을 따른다고 가정하며, 이를 상수 또는 터미널이라 한다.

6. 1. 확률적 L-system (Stochastic L-system)

• `A (0.5) → AB` (50% 확률로 `AB`로 치환)
• `A (0.5) → A` (50% 확률로 변경되지 않음)

6. 2. 문맥 의존 L-system (Context-sensitive L-system)

6. 3. 파라메트릭 L-system (Parametric L-system)

7. L-system 관련 문제

L-시스템 연구와 관련하여 아직 해결되지 않은 여러 문제들이 존재한다. 대표적인 예는 다음과 같다.

• 모든 결정적 문맥 자유 L-시스템이 국소 연결되는 조건을 명확히 밝히는 문제이다. 이 문제는 현재 변수가 두 개뿐인 경우에만 해답이 알려져 있다.^[5]
• 특정 구조가 주어졌을 때, 그 구조를 생성할 수 있는 L-시스템, 즉 생성 규칙이나 매개변수를 역으로 찾아내는 문제이다. 이는 L-시스템을 거꾸로 추적하는 것이 매우 어렵기 때문이며, 특히 자연에서 볼 수 있는 복잡한 구조처럼 여러 단계를 거쳐 형성된 경우 더욱 두드러지는 난제이다.

8. L-system의 종류

L-system은 다양한 차원에서 정의될 수 있다.

'''실수선''' ('''R''')에서의 L-system:

• 투에-모스 수열

• 공간 채움 곡선
• * 힐베르트 곡선
• * 페아노 곡선
• * 콜람
• 기타 곡선 및 타일링
• * 레비 C 곡선
• * 드래곤 곡선
• * 펜로즈 타일링

• 자연물 모델링
• * 식물: 목본, 초본, 양치식물 등
• * 조류 및 원생생물: 방산충 등

참조

_[1] 학술지 Mathematical models for cellular interactions in development II. Simple and branching filaments with two-sided inputs 1968-03
_[2] 서적 The mathematical theory of L systems Academic Press, New York 1980
_[3] 웹사이트 L-systems https://encyclopedia[...] Springer 2022-07-26
_[4] 간행물 A Bi‐Directional Procedural Model for Architectural Design https://www.research[...] 2017-12
_[5] 서적 Handbook of Formal Languages
_[6] 서적 Proceedings of the 27th International Conference on Scientific and Statistical Database Management https://hal.archives[...]
_[7] 학술지 L-Py: An L-System Simulation Framework for Modeling Plant Architecture Development Based on a Dynamic Language