제한 없는 문법

오토마타 이론에서, 제한 없는 문법 클래스(반화, 타입 0 또는 구 구조 문법이라고도 함)는 촘스키 계층에서 가장 일반적인 문법 클래스이다.각 왼쪽이 비어 ^[1]^{: 220}있지 않은 것을 제외하고 제한되지 않은 문법의 생성에 대한 제한은 없습니다.이 문법 클래스는 임의 재귀 열거형 언어를 생성할 수 있습니다.

형식적 정의

제한 없는 문법은 정식 ${\textstyle G=(N,T,P,S)}$ G ${\textstyle G=(N,T,P,S)}$ ( ${\textstyle G=(N,T,P,S)}$ , ${\textstyle G=(N,T,P,S)}$ , ${\textstyle G=(N,T,P,S)}$ , ${\textstyle G=(N,T,P,S)}$ ) ${\textstyle G=(N,T,P,S)}$ { $textstyle$ G = ( $N$ , $T$ , $P$ , $S$ ) ${\textstyle G=(N,T,P,S)}$ 。

$(\displaystyle$ N $)$ 은 $N$ 유한한 비말단 기호 세트입니다.
$T$ {\ $displaystyle$ T $}$ 는 $T$ N{\ $displaystyle$ N $}$ 과 $N$ T {\ $displaystyle$ T $}$ 가 $T$ 분리된 유한한 ^{[note 1]}단자 $기호$ 세트입니다.
$(\displaystyle$ P $)$ 는 $P$ $\alpha \to \beta ,$ $\alpha \to \beta ,$ β , $\alpha \to \beta ,$ \ $displaystyle \alpha$ $}$ 및 $\alpha \to \beta ,$ β(\ $displaystyle$ \alpha $N\cup T$ 형식의 유한한 $\alpha \to \beta ,$ 규칙 집합입니다. $\alpha$ 서 $\alpha$ $N\cup T$ $(\displaystyle$ $\$ $alpha$ $}$ $\beta$ β(\displaystyle $\$ $cup$ T)는 $\alpha \to \beta ,$ $\beta$ $N\cup T$ N\cup $\alpha$ T $)$ 의 기호 문자열이며 $\alpha$ 이 아닙니다.

$S\in N$ N(\ $displaystyle$ S $\in$ N $)$ 은 $S\in N$ 특별히 지정된 시작 ^[1]^{: 220}기호입니다.

이름에서 알 수 있듯이 제한되지 않은 문법이 ^{[note 2]}가질 수 있는 프로덕션 규칙 유형에는 실질적인 제한이 없습니다.

튜링 기계와의 동등성

제한되지 않는 문법은 반복적으로 열거할 수 있는 언어의 특성을 나타냅니다.이는 모든 제한 $없는$ 문법G(\ $L(G)$ G $)$ 에 대해 $G$ L $(\displaystyle$ L $(G)$ 을 $L(G)$ $L(G)$ 할 수 있는 튜링 기계가 존재하며 그 반대의 경우도 마찬가지입니다.제한되지 않은 문법이 주어진다면, 그러한 튜링 기계는 2테이프 비결정적 튜링 ^[1]^{: 221}기계로 구성하기에 충분히 간단하다.첫 번째 테이프에는 테스트할 w $\style$ w라는 $w$ $입력어가$ 포함되어 있습니다.두 번째 테이프는 기계가 G $style$ 에서 sententential 형식을 생성하기 위해 사용합니다.그 후 튜링 머신은 다음을 수행합니다.

두 번째 테이프의 왼쪽부터 시작하여 오른쪽으로 이동하거나 테이프 상의 현재 위치를 반복적으로 선택합니다.
비결정적으로G의 $프로덕션$ 에서 $\beta \to \gamma$ β $\beta \to \gamma$ γ （ \ $display$ $style \ to$ \ display $G$ 를 $\beta \to \gamma$ 선택합니다.
두 번째 테이프의 어떤 위치에 $\beta$ β(\ $displaystyle$ $\beta$ $)$ 가 $\beta$ $\beta$ 그 시점에서 $\beta$ β(\ $displaystyle\gamma)$ 를 $\beta$ $\gamma$ (\ $displaystyle\beta)$ 로 $\gamma$ $\beta$ 합니다.또한 β $(\$ displaystyle\gamma) $\gamma$ 와 $\beta$ $\gamma$ (예:\ $displaystyle\gamma)$ 의 상대적인 길이에 따라 테이프의 기호가 좌우로 바뀔 수 있습니다. $\beta$ β $(\displaystyle\displaystyle\$ displaystyle\displaystyle $\gamma$ 보다 $\beta$ $\gamma$ . $테이프$ 기호를 왼쪽으로 바꿉니다 $.$
테이프 2의 sentential 폼과 테이프 1의 단어를 비교합니다.만약 그것들이 일치한다면, 튜링 기계는 그 단어를 받아들인다.그렇지 않으면 튜링 기계는 1단계로 돌아갑니다.

이 튜링 머신은 마지막 스텝이 임의의 횟수로 실행된 후 두 번째 테이프에 G $(\displaystyle$ G $)$ 의 $G$ 센텐셜 형식만 생성하므로 $L(G)$ L $G)\displaystyle L($ G)을 $L(G)$ 재귀적으로 열거할 수 있어야 함을 쉽게 알 수 있습니다.

역시공도 가능합니다.몇몇 튜링 기계가 주어지면, 왼쪽에 하나 이상의 비말단 기호가 있는 생산물만을 사용하는 동등한 제한^[1]^{: 222} 없는 문법을 만드는 것이 가능하다.따라서 임의의 무제한 문법은 튜링 기계로 변환했다가 다시 변환함으로써 항상 후자의 형식에 따르도록 동등하게 변환될 수 있다.일부^{[citation needed]} 저자들은 제한 없는 문법의 정의로 후자의 형식을 사용한다.

계산 속성

주어진 $문자열$ s $\displaystyle$ s가 $s$ 제한되지 않은 문법에 의해 생성될 수 있는지 여부를 결정하는 문제는 그것이 문법과 동등한 튜링 기계에 의해 받아들여질 수 있는지의 문제와 동일합니다.후자의 문제는 정지 문제로 불리며 판별할 수 없습니다.

재귀 열거형 언어는 Kleene 별, 연결, 결합 및 교차점 아래에 닫히지만 설정된 차이점 아래에서는 닫히지 않습니다. 재귀 열거형 언어 #폐쇄 속성을 참조하십시오.

튜링 기계와 제한되지 않은 문법의 등가는 언어에 대한 서술이 주어진 다른 제한되지 않은 문법의 언어를 받아들일 수 있는 보편적인 제한되지 않은 문법의 존재를 암시한다.따라서 이론적으로 제한되지 않은 문법에 기반한 프로그래밍 언어를 구축할 수 있습니다(예:(화요일)

「」를 참조해 주세요.

람다 미적분
Semi-Thues 시스템 - 단자 기호와 비단말 기호를 구분하지 않고 왼쪽 빈칸을 사용할 수 있습니다.

메모들

^ 사실 T $T\cap N=\emptyset$ N $T\cap N=\emptyset$ ${\$ \ $displaystyle$ T \ $cap$ N = \ $emptyset$ }는 $T\cap N=\emptyset$ 제한되지 않은 문법은 둘을 실질적으로 구분하지 않기 때문에 엄밀하게 필요하지 않습니다.문법의 센텐셜 형식의 생성을 정지하는 타이밍을 알기 위해서만 존재하는 명칭입니다.정확히 말하면G(\ $displaystyle$ $)$ 가 $L(G)$ $인식$ 하는 L $(G)$ 언어는 종단 기호 문자열로 제한됩니다.
^ Hopcroft와 Ullman(1979)은 N $(\displaystyle$ N $N$ $T$ $(\displaystyle$ T $T$ P $(\displaystyle$ P $)$ 의 기수를 명시적으로 $P$ 언급하지 않았지만, 이들의 정리 9.3(특정 문법에 의한 동등한 튜링 기계 구성, 페이지 221, cf)의 증명이다.섹션 #Turing 머신에 대한 동등성)은 암묵적으로P(\ $displaystyle$ P) $P$ 내의 모든 문자열의 유한 길이와 P $(\displaystyle$ P $P$ 의 $N$ 최종성을 필요로 합니다 $.P$ (\ $displaystyle$ N $)$ $T$ (\ $displaystyle$ P $)$ 에서 $T$ $P$ 하지 않는 멤버는 생략할 수 있습니다.게이지

레퍼런스

^ ^a ^b ^c ^d Hopcroft, John; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. ISBN 0-201-44124-1.

[2] 사실 T $T\cap N=\emptyset$ N $T\cap N=\emptyset$ ${\$ \ $displaystyle$ T \ $cap$ N = \ $emptyset$ }는 $T\cap N=\emptyset$ 제한되지 않은 문법은 둘을 실질적으로 구분하지 않기 때문에 엄밀하게 필요하지 않습니다.문법의 센텐셜 형식의 생성을 정지하는 타이밍을 알기 위해서만 존재하는 명칭입니다.정확히 말하면G(\ $displaystyle$ $)$ 가 $L(G)$ $인식$ 하는 L $(G)$ 언어는 종단 기호 문자열로 제한됩니다.

[3] Hopcroft와 Ullman(1979)은 N $(\displaystyle$ N $N$ $T$ $(\displaystyle$ T $T$ P $(\displaystyle$ P $)$ 의 기수를 명시적으로 $P$ 언급하지 않았지만, 이들의 정리 9.3(특정 문법에 의한 동등한 튜링 기계 구성, 페이지 221, cf)의 증명이다.섹션 #Turing 머신에 대한 동등성)은 암묵적으로P(\ $displaystyle$ P) $P$ 내의 모든 문자열의 유한 길이와 P $(\displaystyle$ P $P$ 의 $N$ 최종성을 필요로 합니다 $.P$ (\ $displaystyle$ N $)$ $T$ (\ $displaystyle$ P $)$ 에서 $T$ $P$ 하지 않는 멤버는 생략할 수 있습니다.게이지

[Hopcroft.Ullman.1979-1] Hopcroft, John; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. ISBN 0-201-44124-1.

[1]

[note 1]

[note 2]

Search

제한 없는 문법

네임스페이스

더

목차

형식적 정의

튜링 기계와의 동등성

계산 속성

「」를 참조해 주세요.

메모들

레퍼런스

Search

제한 없는 문법

형식적 정의

튜링 기계와의 동등성

계산 속성

「 」를 참조해 주세요.

메모들

레퍼런스

「」를 참조해 주세요.