촘스키 정규형

Question

문법을 chomsky 정규형으로 변환하는 이유는 무엇입니까?장점이 있습니까?

Answer 1

예를 들어, CNF (또는 파생 트리)의 문법은 문맥없는 언어를위한 펌핑 기본형을 증명하는 데 사용됩니다.

Answer 2

한 가지로, Chomsky Normal Form 문법에서 CYK 알고리즘을 사용할 수 있습니다.

Answer 3

Chomsky 정규 형식을 사용하면 다항식 시간 알고리즘이 문법에 의해 문자열을 생성 할 수 있는지 여부를 결정할 수 있습니다. 동적 프로그래밍을 알고 있다면 알고리즘이 매우 매끄 럽습니다 ...

입력 길이 (I)가 n이면 dim nxn의 2d 배열 (A)을 사용합니다.

A [i, j]는 하위 문자열 I (i, j)를 유도 할 수있는 문법 G의 모든 기호를 나타냅니다.

마지막으로 A [1, n]에 시작 기호 (S)가 포함되어 있으면 확인하려는 S로 문자열을 파생시킬 수 있다는 의미입니다. 라코 디스

색인이 상당히 미친 것 같다는 것을 알고 있습니다. 하지만 기본적으로 여기에 무슨 일이 일어나고 있는지 알려드립니다.

-기본 케이스는 꽤 분명하다고 생각합니다

-유도 단계에서는 길이가 s 미만인 모든 솔루션에서 길이 s 하위 문자열에 대한 솔루션을 빌드합니다.

-인덱스 1에서 시작하는 길이 5 하위 문자열 (sub)에 대한 솔루션을 찾고 있다고 가정합니다. 그런 다음 규칙이 있는지 확인하는 루프 (다른 부분) .....를 시작합니다 (A-> BC). B와 C는 sub의 연속적이고 분리 된 두 개의 하위 문자열을 파생시키고 만약 그렇다면 그러한 모든 A를 N [1,6]에 추가합니다.

-마지막으로 N [1, n]에 시작 기호가 있으면 수락합니다!