재귀 문법
Recursive grammar컴퓨터 과학에서 문법은 비공식적으로 재귀적인 생산 규칙을 포함한다면 재귀 문법이라고 불리며, 이는 이러한 규칙에 따라 비단말기를 확장하면 결국 동일한 비단말기를 포함하는 문자열로 이어질 수 있음을 의미한다.그렇지 않으면 비재귀 [1]문법이라고 불립니다.
예를 들어, 컨텍스트프리 언어의 문법은 A를 가진 문자열을 생성하기 위해 생성 규칙을 통과할 수 있는 비터미널 기호 A가 존재하는 경우 재귀적으로 유지됩니다(맨 왼쪽 기호).[2][3]촘스키 계층 구조의 모든 유형의 문법은 재귀적일 수 있으며,[1] 무한 단어 집합을 생성할 수 있는 것은 재귀입니다.
특성.
비재귀적 문법은 유한한 언어만을 생성할 수 있으며, 각각의 유한한 언어는 비재귀적 [1]문법에 의해 생성될 수 있습니다.예를 들어, 직선 문법은 단 하나의 단어만을 만들어낸다.
불필요한 규칙을 포함하지 않는 문맥이 없는 재귀 문법은 반드시 무한한 언어를 생성합니다.이 속성은 문맥이 없는 문법이 유한한 언어를 [4]생성하는지 무한 언어를 생성하는지 효율적으로 테스트할 수 있는 알고리즘의 기초를 형성합니다.
레퍼런스
- ^ a b c 를 클릭합니다Nederhof, Mark-Jan; Satta, Giorgio (2002), "Parsing Non-recursive Context-free Grammars", Proceedings of the 40th Annual Meeting on Association for Computational Linguistics (ACL '02), Stroudsburg, PA, USA: Association for Computational Linguistics, pp. 112–119, doi:10.3115/1073083.1073104.
- ^ 형식 언어 이론과 해석에 관한 메모, 아일랜드 메이누스 메이누스, 아일랜드, 코킬데어, 아일랜드 컴퓨터 사이언스 국립대학 학부 제임스 파워.
- ^ 를 클릭합니다Moore, Robert C. (2000), "Removing Left Recursion from Context-free Grammars", Proceedings of the 1st North American Chapter of the Association for Computational Linguistics Conference (NAACL 2000), Stroudsburg, PA, USA: Association for Computational Linguistics, pp. 249–255.
- ^ 를 클릭합니다Fleck, Arthur Charles (2001), Formal Models of Computation: The Ultimate Limits of Computing, AMAST series in computing, vol. 7, World Scientific, Theorem 6.3.1, p. 309, ISBN 9789810245009.
