CYK 알고리즘: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 ~하는 데 사용하다/사용되다 |
잔글 {{제목 변경|토론=알고리즘}} |
||
1번째 줄:
'''CYK 알고리즘'''(CYK Algorithm)은 주어진 [[문맥자유문법]]이 특정한 [[문자열]]을 만들어내는지, 만약 그렇다면 어떻게 만들어내는지 판단하는 알고리즘이다. 이 문제는 [[파싱|구문분석(파싱)]]이라고 불린다. 이 알고리즘은 [[동적 계획법]]의 한 예이다.▼
{{제목 변경|토론=알고리즘}}
▲'''CYK 알고리즘'''(CYK Algorithm)은 주어진 [[문맥자유문법]]이 특정한 [[문자열]]을 만들어내는지, 만약 그렇다면 어떻게 만들어내는지 판단하는 알고리즘이다. 이 문제는 [[파싱|구문분석(파싱)]]이라고 불린다. 이 알고리즘은 [[동적 계획법]]의 한 예이다.
CYK 알고리즘은 기본적으로 [[촘스키 정규형식(CNF)]]으로 표현된 문맥자유문법에 의해 정의된 언어를 판단하는 데 사용한다. 하지만 모든 문맥자유문법은 CNF로 표현이 가능하므로 CYK 알고리즘은 모든 문맥자유문법에 대해 사용할 수 있다. 또한, CYK 알고리즘은 CNF로 표현되지 않은 문맥자유문법을 처리하도록 확장할 수 있는데 일반적으로 성능을 높이기 위해 확장하지만 알고리즘을 이해하기는 더 어려워진다.
| |||