무제약 문법

오토마타 이론에서, 무제약 문법() 또는 0유형 문법()은 촘스키 위계에서 가장 일반적인 종류의 형식 문법이다. 무제약 문법의 생성 규칙은 좌변이 빈 문자열일 수 없다는 것 외에 아무런 제약도 받지 않는다. 무제약 문법은 어떤 재귀 열거 언어라도 생성할 수 있다.

 정의 
무제약 문법은 형식 문법 이다.
 은 비말단 기호의 유한집합이다.
 는 말단 기호의 유한집합이다. 과 는 서로소이다.사실 무제약 문법은 말단 기호와 비말단 기호를 구별하지 않으므로 과 가 꼭 서로소일 필요는 없다. 둘을 구별하는 이유는 문장 형식의 생성을 언제 멈출지 알기 위해서이다. 구체적으로 말해, 가 생성하는 형식 언어 는 말단 기호의 문자열로만 이루어진다.
 는 생성 규칙의 유한집합이다. 생성 규칙은  꼴이며, 이때  와 는 에 속한 기호들로 이루어진 문자열이고, 는 빈 문자열이 아니다.
 는 특별히 정한 시작 기호이다.

그 이름대로 무제약 문법의 생성 규칙에는 사실상 아무런 제약도 없다.Hopcroft and Ullman (1979)은 , , 의 크기를 명시적으로 언급하지 않지만, 정리 9.3(주어진 무제약 문법과 동치인 튜링 기계의 구성, p. 221, #튜링 기계와의 동치 문단 참조)의 증명은 암묵적으로 가 유한집합일 것과 의 규칙들에 속한 문자열의 길이가 모두 유한할 것을 요구한다. 에 나타나지 않는 이나 의 원소를 없애더라도 생성되는 언어는 달라지지 않는다.

 튜링 기계와의 동치 
무제약 문법이 생성하는 언어의 집합은 재귀 열거 언어의 집합과 같다. 달리 말하면, 모든 무제약 문법 에 대해 를 인식하는 튜링 기계가 존재하고, 그 역도 성립한다. 주어진 무제약 문법에 대응하는 2테이프 비결정론적 튜링 기계는 간단하게 만들 수 있다. 첫 번째 테이프에는 에 속하는지 알아볼 입력 단어 가 올라가고, 두 번째 테이프는 의 문장 형식(, 시작 기호에 생성 규칙을 유한 번 적용해서 얻을 수 있는 문자열)을 생성하는 데 사용한다. 기계는 다음과 같이 동작한다.
 두 번째 테이프의 왼쪽에서 시작해서, 오른쪽으로 움직이거나 현재 테이프 위치를 선택하는 것 중에서 고르기를 반복한다.
 의 생성 규칙들 중에서 규칙 를 비결정론적으로 고른다.
 가 두 번째 테이프의 특정 위치에 나타난다면, 그 위치에서 를 로 대체한다. 와 의 길이가 다르다면 테이프 위의 다른 기호들을 잘 이동시킨다.
 만들어진 문장 형식을 첫 번째 테이프와 비교한다. 둘이 일치하면, 입력 단어를 받아들인다. 일치하지 않으면, 1단계로 돌아간다.
이러한 튜링 기계가 만드는 문자열의 집합이 의 문장 형식의 집합과 같다는 것은 쉽게 알 수 있다. 따라서 언어 는 재귀 열거 가능하다.

반대의 구성도 가능하다. 주어진 튜링 기계와 동치인 무제약 문법을 만들 수 있으며, 이때 모든 생성 규칙이 좌변에 하나 이상의 비말단 기호를 포함하게 하는 것도 가능하다. 따라서 임의의 무제약 문법은 모든 생성 규칙이 그러한 꼴을 가지는 문법과 동치이다. 어떤 저자들은 후자를 무제약 문법의 정의로 삼기도 한다.

 계산적 성질 
주어진 문자열이 주어진 무제약 문법으로 생성될 수 있는지의 문제는 그 문법과 동치인 튜링 기계가 주어진 문자열을 받아들일지의 문제와 동치이다. 후자는 정지 문제라 불리며 이는 결정불가능하다.

재귀 열거 언어는 클레이니 스타, 문자열 연결, 합집합, 교집합 연산에 닫혀 있지만, 차집합 연산에는 닫혀 있지 않다.

무제약 언어와 튜링 기계가 동치라는 사실로부터 보편 튜링 기계에 대응하는 보편 무제약 문법이 존재함을 알 수 있다. 이러한 문법은 다른 무제약 문법에 대한 기술을 입력받으면 그 문법으로 생성되는 어떤 문자열이든 받아들일 수 있다. 따라서 무제약 문법을 바탕으로 한 프로그래밍 언어를 만드는 것도 가능하다.

 같이 보기 
 람다 대수
 문자열 재작성 체계: 말단과 비말단 기호를 구별하지 않고, 좌변에 빈 문자열을 허용하는 체계

 각주 
 내용주 

 참조주 

분류:형식 언어