형식 언어

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

형식 언어는 유한한 종류의 문자로 이루어진 유한한 길이의 문자열의 집합을 말한다.

형식 언어는 수학, 논리학, 언어학, 정보 이론 등에서 사용하고 있으며, 또한 계산가능성 이론과 밀접하게 관련되어 있다.

정의[편집]

각 형식 언어에는 그 언어에서 사용하는 문자의 집합이 있으며, 그 집합은 무한할 수도 있다. 그 형식 언어에 속하는 문자열은 문자들로 이루어진 유한한 길이의 수열로 정의된다. 문자 집합을 라고 정의했을 때, 그 문자들로 이루어진 모든 문자열의 집합은 가 된다. 여기에서 별표는 클레이니 스타 연산자이다.

이 때, 위에 존재하는 형식 언어 부분집합으로 정의된다.

형식 언어의 기술 방식[편집]

형식 언어는 특정한 문자열의 집합이기 때문에, 다음과 같은 방식을 이용해 형식 언어를 만들 수도 있다.

형식 언어의 연산[편집]

기존의 형식 언어를 결합하여 새로운 언어를 만들어 낼 수 있다. 두 형식 언어 L1L2가 있다고 하면, 다음과 같은 연산을 할 수 있다.

  • L1L2연쇄L1 의 문자열 vL2 의 문자열 w 를 연쇄시켜 만든 단어들의 집합이다. 표기: 또는 .
  • L1L2교집합L1L2 에 동시에 속해 있는 문자열들의 집합이다. 표기 : .
  • L1L2합집합L1에 속하거나 L2 에 속하는 문자열들의 집합이다. 표기 : 또는 .
  • L1여집합L1 에 속하지 않는 문자열들의 집합이다.
  • 우상(右商: 오른쪽 몫)은 L2의 문자열 w 에 대하여 vwL1 에 속하도록 하는 문자열 v 의 집합이다. 표기 : .