Chomsky 표준 형식 변환 알고리즘

왜 우리가 Chomsky 표준 형식으로 문법을 변환하고 싶을 때 새로운 시작 상태 S0 -> S를 추가합니까? 우리가 그렇게하지 않으면 어떻게 될까요?Chomsky 표준 형식 변환 알고리즘

처음에는 그것이 엡실론 규칙 때문이라고 생각했습니다. 그러나 우리는 시작 변수에서 엡실론 규칙을 제거하지 않습니다. 그렇다면 S0 -> S를 추가하면 어떤 이점이 있습니까?

감사합니다.

2016-05-31 A. Mashreghi

빈 문자열이 언어에 있는지 여부에 따라 $ S -> \ ε $ (또는 $ S_0 -> \ 엡실론 $) 규칙이있을 수 있습니다. 규칙의 오른쪽에 $ $ 기호가 있으면 기호 $ S $의 임의의 수를 삭제할 수 있습니다. 시작 기호가 다시 나타나기를 원하지 않기 때문에 새로운 기호를 도입합니다.

이렇게하면 규칙 A -> BC의 응용 프로그램마다 정확히 하나 더 많은 기호가 나타납니다.

출처

2016-06-03 15:24:16

변수가 시작 기호가 아닌 경우에만 엡실론 규칙이 삭제되므로 S ---> \ 엡실론 규칙이 있어도 엡실론 규칙이 삭제되므로 제거하지 않을 것이므로 문제가되지 않는다고 생각합니다. –

요점은 CNF를 사용하면 길이가 n 인 문자열의 유도가 n-1 규칙 A -> BC 및 n - A 형태임을 알 수 있습니다. 문법 S-> A, A-> AS, A-> a, S-> eps는 문자열 a를 임의의 많은 방법으로 유도 할 수 있습니다. 이것은 ** 정상적인 양식 **에서 원하는 것이 아닙니다. –

제가 약간의 설명이 있다고 생각합니다.

: - : 문법은 다음과 같은 경우 처음> S1 우리는해야합니다 우리가 어떤 특정 순서를 고려하지 않기 때문에 "단위 규칙"을 제거하는 단계에서

S --> S1 
S1 --> S 
S1 --> a

그런 다음, 우리는 S를 제거 할 수

S1 --> S1 
S1 --> a

시작 변수가 완전히 제거되었습니다.

출처

2016-06-01 02:41:59

답변

관련 문제