L-system

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

L-system(엘 시스템, Lindenmayer system)은 형식문법의 일종으로서, 식물의 성장 프로세스를 기초로 한 다양한 자연물의 구조를 기술하거나 표현을 가능케 하는 알고리즘이다. 자연물 이외에도 망델브로 집합 반복함수계(Iterated Function System; IFS)와 같이 이른바 자기상사 도형이나 프랙탈 도형을 생성할 경우에도 사용된다. L-system은 1968년, 네덜란드 위트레흐트 대학교 대학의 이론생물학자이자 식물학자였던 아리스티드 린덴마이어(Aristid Lindenmayer)에 의해 제창되어 발전되었다.

기원[편집]

생물학자였던 린덴마이어는 효모곰팡이, 그리고 남세균류의 Anabaena catenula와 같은 조류 등, 다양한 생물의 성장패턴을 연구했다. 이와 같이 L-system은 단세포생물 또는 단순한 다세포생물의 성장식, 식물세포에 있어서 인접한 세포의 상호관계를 기술하기 위해 개발된 것이었다. 이후 L-system은 더욱 고도로 발달한 식물의 형태, 복잡한 분기구조를 기술하기 위한 도구로 발전하게 되었다.

L-system의 구조[편집]

L-system의 기본은 재귀성으로서, 자기상사도형, 프랙탈도형과 같은 형태를 단순히 기술하는 것이 가능하다. 식물과 그외의 형태가 자연스러운 생물구조도 함께 단순히 정의가 되어, 재귀호출의 회수를 늘려, 마치 구조가 성장, 복잡화되어가는 것처럼 보인다. L-system은 인공생명의 생성에도 잘 쓰인다.

L-system의 문법은 semi-Thue grammar와 닮았다.(→촘스키 위계) 현재, L-system은 아래와 같은 튜플로 정의된 "파라메트릭 L-system"로서 일반에 알려져 있다.

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

위의 각 요소는 이하의 의미를 갖고 있다.

  • V(문자): 치환규칙(다음에 기술하는 P)에 의해 순차적으로 바뀌어가는 변수의 집합.

L-system의 재귀적인 반복계수가 진행해 갈 때, 무언가로 성장해 나가는 것은 이 V의 요소에서부터 만들어지는 문자열이다.

  • S : 계산이 진행되어도 변화하지 않는정수의 집합.
  • ω : 시스템의 초기상태를 나타내는V의 요소에서 만들어지는 문자열.
  • P : V를 변화시켜가는 치환규칙의 집합. 각 요소는 예를들어 (A → AB)와 같이

치환전(치환대상)의 문자열과 치환후의 문자열의 조합에 의해 기술된다.

치환규칙 P에 관해, 치환대상이 단독의 문자만일 경우, L-system은 문맥자유언어이다. 한편, 치환규칙이 인접한 문자와의 상호관계까지 고려하는 것일 경우 L-system은 문맥의존언어이다. 또한 치환규칙P가 문자에 대해 매번 확실히 적용될 경우 L-system은 "결정론적"이다 라고 불리어, D0L-system(deterministic context-free L-system)등으로 불린다. 반대로, 치환규칙의 적용이 확률에 좌우될 경우엔 "확률론적" L-system라고 불린다.

L-system을 그래픽으로 응용하는 경우, L-system이 생성하는 문자열을, 무언가의 형태로 화면상의 도형으로 변환시키지 않으면 안 된다. 예를 들어 FractInt라는 프로그램에서는 로고와 같이 터틀을 이용하여 그래픽을 생성한다. 결국 프로그램이 L-system의 문자열을 터틀의 제어명령으로 번역해서 도형을 그려지게 하는 것이다.

참고문헌[편집]

외부 링크[편집]

아래 열거된 바깥 고리 목록은 위키백과의 정책 혹은 편집 지침을 따르고 있지 않습니다. 더 좋은 문서가 되도록 문서 수정을 도와주세요.