L계

이 문서에는 여러 가지 문제가 있습니다.개선을 돕거나 토크 페이지에서 이러한 문제에 대해 논의해 주십시오.(이러한 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다) 이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : "L-system" – 뉴스 · 신문 · 서적 · 학자 · JSTOR (2013년 4월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인) 이 기사는 교과서처럼 읽힌다. 이 글의 톤을 중립으로 하고 Wikipedia의 품질 기준을 충족하도록 개선해 주십시오. (2020년 8월) (이 템플릿메시지를 삭제하는 방법과 타이밍을 확인합니다)

L-시스템 또는 Lindenmayer 시스템은 병렬 개서 시스템이며 형식 문법의 한 종류입니다.L-시스템은 문자열을 만드는 데 사용할 수 있는 기호 알파벳, 각 기호를 더 큰 기호 문자열로 확장하는 생산 규칙의 집합, 구축을 시작하는 초기 "축" 문자열 및 생성된 문자열을 기하학적 구조로 변환하는 메커니즘으로 구성됩니다.L-시스템은 위트레흐트 대학의 ^[1]헝가리 이론 생물학자이자 식물학자 아리스티드 린덴마이어에 의해 1968년에 도입되고 개발되었습니다.Lindenmayer는 L-systems를 사용하여 식물 세포의 동작을 설명하고 식물 발달의 성장 과정을 모델링했습니다.L-시스템은 또한 다양한 유기체의^[2] 형태학을 모델링하는 데 사용되어 왔고 자기 유사 프랙탈을 생성하는데 사용될 수 있다.

오리진스

생물학자로서, 린덴마이어는 효모와 필라멘트 균을 가지고 연구했고 시아노박테리아 아나베나 카테눌라와 같은 다양한 종류의 박테리아들의 성장 패턴을 연구했습니다.원래 L-시스템은 그러한 단순한 다세포 생물의 발달에 대한 공식적인 설명을 제공하고 식물 세포 간의 인접 관계를 설명하기 위해 고안되었다.나중에, 이 시스템은 더 높은 식물과 복잡한 분기 구조를 설명하기 위해 확장되었다.

L계 구조

L-시스템 규칙의 재귀적 특성은 자기 유사성으로 이어지며, 따라서 프랙탈과 같은 형태는 L-시스템으로 설명하기가 쉽습니다.식물 모형과 자연 그대로의 유기 형태는 정의하기 쉬운데, 이는 재귀 레벨을 높임으로써 형태가 천천히 '그로우'되고 복잡해지기 때문입니다.린덴마이어 시스템은 인공생명체의 세대에서도 인기가 있다.

L-시스템 문법은 반 화요일 문법과 매우 유사합니다(촘스키 계층 참조).L-시스템은 일반적으로 파라메트릭 L시스템으로 알려져 있으며, 튜플로 정의되어 있습니다.

G = (V, δ, P),

어디에

• V(알파벳)는 치환 가능한 요소(변수)와 치환 불가능한 요소('상수' 또는 '종단')를 모두 포함하는 기호 집합입니다.
• §(start, aciom 또는 initiator)는 시스템의 초기 상태를 정의하는 V의 기호 문자열입니다.
• P는 변수를 상수 및 기타 변수의 조합으로 대체하는 방법을 정의하는 일련의 생산 규칙 또는 생산입니다.프로덕션은 이전 문자열과 후속 문자열의 두 가지 문자열로 구성됩니다.집합 V의 구성원으로 P에서 생산물의 왼쪽에 나타나지 않는 기호 A에 대해 항등식 생성 A → A로 가정한다. 이러한 기호를 상수 또는 단자라고 한다(항등식 법칙 참조).

L-system 문법의 규칙은 초기 상태부터 반복적으로 적용된다.반복마다 가능한 한 많은 규칙이 동시에 적용됩니다.각 반복이 가능한 한 많은 규칙을 사용한다는 사실은 L-시스템을 반복당 하나의 규칙만 적용하는 형식 문법에 의해 생성된 형식 언어와 구별한다.생산 규칙을 한 번에 하나씩만 적용하면 언어에서 문자열을 생성할 수 있으며, 이러한 응용 프로그램의 모든 시퀀스는 문법에 의해 지정된 언어를 생성합니다.그러나 일부 언어에는 문법을 언어 사양이 아닌 L-system으로 취급할 경우 생성할 수 없는 문자열이 있습니다.예를 들어,^[3] 문법에 규칙 S→SS가 있다고 가정합니다.한 번에 1개씩 생산이 이루어지면 S부터 시작하여 첫 번째 SS를 얻고 다시 규칙을 적용하면 SSS를 얻을 수 있습니다.단, L-system과 같이 모든 적용 가능한 규칙이 모든 단계에서 적용되면 이 sentential 형식을 얻을 수 없습니다.대신 첫 번째 단계는 SS를 제공하지만 두 번째 단계는 규칙을 두 번 적용하여 SSSS를 제공합니다.따라서, 주어진 문법에서 L-시스템에 의해 생성된 문자열 집합은 문법에 의해 정의된 형식 언어의 부분 집합이며, 만약 우리가 문자열 집합으로 정의되는 언어를 취한다면, 이것은 주어진 L-시스템이 사실상 L-시스템의 문법에 의해 정의된 형식 언어의 부분 집합임을 의미한다.

각 생산 규칙이 인접 관계가 아닌 개별 기호만을 참조하는 경우 L 시스템은 컨텍스트가 없습니다.따라서 문맥이 없는 L-시스템은 문맥이 없는 문법에 의해 지정됩니다.규칙이 단일 기호뿐만 아니라 인접 기호에도 의존하는 경우, 컨텍스트에 민감한 L-시스템이라고 합니다.

각 심볼에 대해 정확히 하나의 생산물이 존재하는 경우, L-시스템은 결정론적이라고 한다(결정론적인 문맥이 없는 L-시스템은 일반적으로 D0L 시스템이라고 불린다).만약 여러 개가 있고, 각 반복 동안 각각 특정한 확률로 선택된다면, 그것은 확률적 L-시스템이다.

그래픽 이미지를 생성하기 위해 L 시스템을 사용하려면 모델의 기호가 컴퓨터 화면에 있는 도면의 요소를 참조해야 합니다.예를 들어, Frackint 프로그램은 로고 프로그래밍 언어와 유사한 거북 그래픽을 사용하여 화면 이미지를 생성합니다.L-시스템 모형의 각 상수를 거북이 명령으로 해석합니다.

L-시스템 예시

예 1: 조류

조류의 성장을 모델링하기 위한 린덴마이어의 오리지널 L-시스템.

변수 : A B

상수: 없음

공리 : A

규칙: (A → AB), (B → A)

그 결과, 다음과 같이 됩니다.

n = 0 : A

n = 1 : AB

n = 2 : ABA

n = 3 : ABAB

n = 4 : ABABABA

n = 5 : ABAB아바바

n = 6 : ABAB아바바바AABABA

n = 7 : ABAB아바바바AABABABABABAABAB

예 1: 조류, 설명

n=0: 시작(예/예)/\n=1: 규칙(A → AB), 규칙(B → A)에 의해 AB로 생성된 초기 단일 A를 적용할 수 없음/\n=2: 모든 규칙이 적용된 이전 문자열 AB, A가 AB로 생성된 이전 문자열 A, 다시 AB로 변환된 이전 문자열 A/ \ n = 3 : A A A B는 모든 A가 애초에 자신의 복사본을 만들고, 그 다음에 B가 ... / \ \ n = 4 : A B A A B B A ...가 한 세대 후에 A A A A A B B A ...가 생성/생성/생성/생성되는 것을 주목한다.

그 결과는 피보나치어들의 순서이다.각 문자열의 길이를 세면 유명한 피보나치 수열을 얻을 수 있습니다(공리를 선택했기 때문에 첫 번째 1은 생략).

1 2 3 5 8 13 21 34 55 89 ...

첫 번째 1을 건너뛰지 않으려면 공리 B를 사용할 수 있습니다.그러면 위의 그래프의 맨 위 노드(A) 앞에 B 노드가 배치됩니다.

각 문자열에 대해 문자열의 왼쪽 끝에서k번째 위치를 카운트하면 황금 비율의 배수가 간격$({\displaystyle k}$ ${\displaystyle -1}$,${\displaystyle }$k $)\displaystyle (k-1,k$ 내에 있는지 여부에 따라 값이 결정됩니다.A 대 B의 비율도 마찬가지로 황금 평균으로 수렴됩니다.

이 예에서는 규칙(A → AB)이 (A → BA)로 대체될 경우 문자열이 미러링된다는 점을 제외하고 각 문자열의 길이 측면에서 동일한 결과를 얻을 수 있습니다.

$G{\displaystyle }$(${\displaystyle }$${\displaystyle n}$ )$$${\displaystyle =G}$ (${\displaystyle n}$ - ${\displaystyle 1}$)${\displaystyle G}$ (${\displaystyle n}$ - ${\displaystyle 2}$) \ $displaystyle$$G$ ( n ) $= G$ ( n - 1 ) G ( n - 2 ) （ n - 1 ) G ( n - 2$$） （ n - 2 ${\displaystyle ）}$ 。$여기$서 G ( n ) \ $displaystyle$ G ( n )는 n - generation입니다$.$

예 2: 프랙탈(이진) 트리

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

모양은 생산 규칙을 통해 공리를 재귀적으로 공급함으로써 만들어집니다.입력 문자열의 각 문자를 규칙 목록과 대조하여 출력 문자열에서 대체할 문자열이 결정됩니다.이 예에서는 입력 문자열의 '1'이 출력 문자열의 '11'이 되는 반면 '['은 그대로입니다.이를 '0'의 공리에 적용하면 다음과 같이 됩니다.

공리:	0
첫 번째 재귀:	1[0]0
두 번째 재귀:	11[1[0]0]1[0]0
세 번째 재귀:	1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0
…

이 문자열은 크기와 복잡성이 빠르게 증가하는 것을 알 수 있습니다.이 문자열은 거북 그래픽을 사용하여 이미지로 그릴 수 있으며, 각 기호에는 거북이가 수행할 그래픽 작업이 할당됩니다.예를 들어, 위의 샘플에서 거북이는 다음과 같은 지시를 받을 수 있습니다.

• 0: 리프에서 끝나는 선분을 그립니다.
• 1: 선분을 그립니다.
• [: 위치와 각도를 누르고, 왼쪽으로 45도 회전합니다.
• ]: 위치 및 각도를 팝업하여 45도 오른쪽으로 돌립니다.

푸시 앤 팝은 LIFO 스택을 나타냅니다(더 기술적인 문법은 "밀기 위치"와 "좌회전"에 대한 별도 기호를 가집니다).거북이 해석에서 '['가 발견되면 현재 위치와 각도가 저장되고 ']'가 발견되면 복원됩니다.여러 개의 값이 "푸시"된 경우 "팝"이 가장 최근에 저장된 값을 복원합니다.위의 그래픽 규칙을 이전 재귀에 적용하면 다음과 같은 결과가 나옵니다.

예 3: 칸토어 세트

변수 : A B

상수: 없음

start : {시작문자열}

규칙 : (A → ABA), (B → BBB)

A는 "앞으로 나아가다"를 의미하고 B는 "앞으로 나아가다"를 의미한다고 합시다.

이것은 실제 직선 R에 유명한 칸토어의 프랙탈 세트를 생성합니다.

예 4: 코흐 곡선

직각만 사용하는 코흐 곡선의 변형입니다.

변수 : F

상수: + -

시작 : F

규칙 : (F → F+F-F+F)

여기서 F는 "앞으로 당김", +는 "좌회전 90°", -는 "우회전 90°"를 의미합니다(터틀 그래픽 참조).

n = 0:

F

n = 1:

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

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-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+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: 시에르핀스키 삼각형

L-시스템을 사용하여 그려진 시에르핀스키 삼각형.

변수 : F G

상수: + -

시작 : F-G-G

규칙 : (F→F+F+G-F), (G→GG)

각도 : 120°

여기서 F는 "앞으로 당기기", G는 "앞으로 당기기", +는 "각도로 좌회전", -는 "각도로 우회전"을 의미합니다.

• 

  n = 2

• 

  n = 4

• 

  n = 6

시에르핀스키 화살촉 곡선 L-계를 사용하여 시에르핀스키 삼각형을 근사할 수도 있습니다.

변수 : A B

상수: + -

시작 : A

규칙 : (A→B-A-B), (B→A+B+A)

각도 : 60°

여기서 A와 B는 모두 "앞으로 긋기", +는 "각도로 좌회전", -는 "각도로 우회전"을 의미합니다(터틀 그래픽 참조).

n = 2, n = 4, n = 6, n = 8에 대한 진화

예 6: 용곡선

L-시스템을 사용하여 그린 드래곤 곡선입니다.

변수 : F G

상수: + -

시작 : F

규칙 : (F → F+G), (G → F-G)

각도 : 90°

여기서 F와 G는 모두 "앞으로 당김", +는 "각도로 좌회전", -는 "각도로 우회전"을 의미합니다.

용 곡선(n = 10)

예 7: 프랙탈 플랜트

변수 : X F

상수: + - [ ]

시작 : X

규칙 : (X → F+[X]-X]-F[-FX]+X), (F → FF)

각도: 25°

여기서 F는 "앞으로 당김", - "우회전 25°"를 의미하며 +는 "좌회전 25°"를 의미합니다.X는 그리기 작업에 해당하지 않으며 곡선의 진화를 제어하는 데 사용됩니다.대괄호 ""는 위치 및 각도에 대한 현재 값을 저장하는 것에 해당하며, 해당 "]가 실행될 때 복원됩니다.

프랙탈 플랜트(n = 6)

바리에이션

서로 연계하여 사용할 수 있는 이 기본적인 L-시스템 기술에 대한 많은 세부 사항이 개발되었습니다.그 중에는 확률적 문법, 문맥에 민감한 문법, 파라메트릭 문법 등이 있습니다.

확률적 문법

지금까지 논의한 문법 모델은 결정론적이었습니다.즉, 문법의 알파벳에 기호가 있는 경우 항상 선택되고 항상 동일한 변환을 수행하는 생산 규칙이 정확히 하나 있습니다.한 가지 방법은 한 기호에 대해 둘 이상의 생산 규칙을 지정하여 각 기호가 발생할 확률을 지정하는 것입니다.예를 들어, 예 2의 문법에서는 "0"을 다시 쓰는 규칙을 다음과 같이 변경할 수 있습니다.

0 → 1[0]0

확률론적 규칙에 준거:

0 (0.5) → 1[0]0

0 (0.5) → 0

이 프로덕션에서는 문자열 개서 중에 "0"이 발생할 때마다 앞에서 설명한 대로 동작할 확률이 50%이고, 프로덕션 중에 변경되지 않을 확률이 50%입니다.확률적 문법이 진화적 맥락에서 사용될 때, 무작위 종자를 유전자형에 포함시켜 세대 간에 영상의 확률적 특성이 일정하게 유지되도록 하는 것이 바람직하다.

문맥 의존 문법

상황에 맞는 생성 규칙은 수정 중인 기호뿐만 아니라 문자열의 앞뒤에 나타나는 기호를 확인합니다.예를 들어, 생산 규칙은 다음과 같습니다.

b < a > c → aaa

는 "a"를 "aa"로 변환하지만 "a"가 입력 문자열의 "b"와 "c" 사이에서 발생하는 경우에만 다음과 같이 변환합니다.

…자세히…

확률적 생산과 마찬가지로, 다양한 맥락에서 기호를 처리하기 위한 여러 생산물이 있습니다.특정 컨텍스트에 대해 프로덕션 규칙을 찾을 수 없는 경우 ID 생산이 가정되며 변환 시 기호는 변경되지 않습니다.문맥 의존형 및 문맥 의존형 모두 같은 문법에 존재할 경우 문맥 의존형 생산이 적용 가능한 경우 우선하는 것으로 간주됩니다.

파라메트릭 문법

파라메트릭 문법에서 알파벳의 각 기호는 관련된 파라메타 리스트를 가진다.파라미터 목록과 결합된 기호를 모듈이라고 하며, 파라미터 문법의 문자열은 일련의 모듈입니다.예를 들어 다음과 같은 문자열이 있습니다.

a(0,1)[b(0,0)]a(1,2)

매개변수는 도면 기능 및 생산 규칙에서 사용할 수 있습니다.프로덕션 규칙은 두 가지 방법으로 매개 변수를 사용할 수 있습니다. 첫째, 규칙의 적용 여부를 결정하는 조건부 문에서 그리고 둘째, 실제 매개 변수를 수정할 수 있습니다.예를 들어 다음과 같습니다.

a(x,y):x == 0 → a(1,y+1)b(2,3)

모듈 a(x,y)는 조건부 x=0이 충족되면 이 생산 규칙에 따라 변환을 거칩니다.예를 들어 a(0,2)는 변환을 수행하고 a(1,2)는 변환을 수행하지 않습니다.

프로덕션 규칙의 변환 부분에서는 파라미터와 모듈 전체가 영향을 받을 수 있습니다.위의 예에서는 모듈 b(x,y)가 초기 파라미터(2,3)와 함께 문자열에 추가됩니다.또한 기존 모듈의 파라미터도 변환됩니다.상기의 생산규칙에 따라

a(0,2)

된다

a(1,3)b(2,3)

a(x,y)의 "x" 매개변수가 "1"로 명시적으로 변환되고 a의 "y" 매개변수가 1씩 증가합니다.

파라메트릭 문법을 사용하면 거북 해석 방법이 아닌 문법에 따라 선 길이와 분기 각도를 결정할 수 있습니다.또 모듈의 파라미터로 에이징을 지정하면 플랜트 세그먼트의 에이징에 따라 규칙이 변경되어 트리의 라이프 사이클 전체의 애니메이션을 작성할 수 있다.

쌍방향 문법

양방향 모델은 기호 다시 쓰기 시스템을 모양 할당에서 명시적으로 분리합니다.예를 들어 예제 2(프랙탈 트리)의 문자열 다시 쓰기 프로세스는 그래픽 연산이 심볼에 할당되는 방법에 따라 독립적입니다.즉, 주어진 개서 시스템에 무한한 수의 그리기 방법을 적용할 수 있다.

쌍방향 모델은 1) 순방향 프로세스가 생산 규칙을 사용하여 파생 트리를 구성하고 2) 역방향 프로세스가 단계적(잎에서 뿌리까지) 방식으로 도형을 가진 트리를 실현하는 것으로 구성됩니다.각각의 역파생 단계는 필수적인 기하학적 위상적 추론을 포함한다.이 쌍방향 프레임워크에서는 설계 제약사항과 목적이 문법형 변환으로 부호화됩니다.건축설계 어플리케이션에서 쌍방향 문법은 일관된 내부 연결성과 풍부한 ^[4]공간 계층을 특징으로 합니다.

미해결 문제

L-시스템에 대한 연구와 관련된 많은 미해결 문제들이 있다.예를 들어 다음과 같습니다.

• 국소적으로 개선되는 모든 결정론적 문맥이 없는 L-시스템의 특성화(완전한 솔루션은 변수가 ^[5]두 개뿐인 경우에만 알려져 있습니다).
• 구조가 주어지면 그 구조를 ^{[citation needed]}만들 수 있는 L-system을 찾습니다.

L-시스템의 종류

실선상의 L-시스템 R:

• 프루셰-투-모르스 시스템

평면² R의 잘 알려진 L 시스템은 다음과 같습니다.

• 공간을 채우는 곡선(힐버트 곡선, 페아노 곡선, 데킹 교회, 콜람스)
• 중앙 공간 채우기 곡선(Levy C 곡선, Harter-Heighway 드래곤 곡선, Davis-Knuth Terdragon),
• 타일링(스핑크스 타일링, 펜로즈 타일링)

「 」를 참조해 주세요.

• 디지털 형태 형성
• 프랙탈
• 반복 기능 시스템
• 힐베르트 곡선
• 반응-확산 시스템 – 확산-화학-반응제 시뮬레이션을 제공하는 수학적 모델의 유형(생명과 유사한 것 포함)
• 확률적 문맥 자유 문법
• 스피드 트리
• 식물의 알고리즘적 아름다움

메모들

책들

• Przemyswaw Prusinkiewicz, Aristid Lindenmayer – 식물의 알고리즘 아름다움 PDF 버전은 여기에서 무료로 구할 수 있습니다.
• Grzegorz Rozenberg, Arto Salomaa – Lindenmayer Systems: 이론 컴퓨터 과학, 컴퓨터 그래픽스 및 개발 생물학에 미치는 영향 ISBN 978-3-540-55320-5
• D.S. Ebert, F.K. Musgrave 등 – 텍스처링 및 모델링: 절차적 접근법, ISBN 0-12-228730-4
• Burry, Jane, Burry Mark, (2010).뉴욕 건축의 새로운 수학:템즈와 허드슨입니다.
• 아리스티드 린덴메이어, "세포가 발달하는 과정에서 상호작용하는 수학적 모델" J. 컨솔트.생물학, 18:280-315, 1968.

외부 링크