정기적 인 컨텍스트가없는 문법

StackOverflow https://stackoverflow.com/questions/559763

문제

나는 내 공부하고있다 계산 언어 테스트, 머리를 감싸는 데 문제가있는 아이디어가 하나 있습니다.

나는 그것을 이해했다 일반 문법 더 간단하고 모호성을 포함 할 수는 없지만 언어를 프로그래밍하는 데 필요한 많은 작업을 수행 할 수 없습니다. 나는 또한 그것을 이해했다 상황이없는 문법 모호성을 허용하지만 언어를 프로그래밍하는 데 필요한 몇 가지를 허용합니다 (Palindromes).

내가 문제가있는 것은 일반 문법 비 터미널 터미널 또는 비 터미널에 맵핑 한 다음 터미널 또는 컨텍스트가없는 비 터미널 맵이 터미널 및 비 터미널의 조합에 대한 맵핑을 할 수 있습니다.

누군가 내가이 모든 것을 함께 모으도록 도와 줄 수 있습니까?

도움이 되었습니까?

해결책

일반 문법은 오른쪽 또는 왼쪽 선형 인 반면 컨텍스트 자유 문법은 기본적으로 단자와 비 터미널의 모든 조합입니다. 따라서 일반 문법은 상황이없는 문법의 하위 집합임을 알 수 있습니다.

예를 들어 Palindrome의 경우, 형식입니다. 

S->ABA
A->something
B->something

Palindromes는 정기적 인 문법으로 표현할 수 없다는 것을 분명히 알 수 있습니다. 오른쪽 또는 왼쪽 선형이어야하므로 양쪽에 비 터미널을 가질 수 없기 때문입니다.

일반 문법은 모호하지 않기 때문에 주어진 비 터미널에 대한 생산 규칙은 단 하나 뿐인 반면 상황이없는 문법의 경우 하나 이상이있을 수 있습니다.

다른 팁

나는 당신이 생각하고 싶은 것이 다양한 펌핑 레마타라고 생각합니다. 정기적 인 언어는 유한 한 자동으로 인식 할 수 있습니다. 컨텍스트가없는 언어에는 스택이 필요하며 컨텍스트 민감한 언어에는 두 개의 스택이 필요합니다 (이는 완전 튜링 머신이 필요하다고 말하는 것과 같습니다.)

우리가 생각한다면 일반 언어를위한 레마를 펌핑합니다, 본질적으로, 모든 일반 언어는 세 조각으로 나눌 수 있다는 것입니다. 엑스, 와이, 그리고 지, 언어의 모든 사례가있는 곳 xy*z (여기서 *는 Kleene 반복, 즉 0 개 이상의 사본입니다. 와이.) 기본적으로 확장 할 수있는 하나의 "비 터미널"이 있습니다.

이제 상황이없는 언어는 어떻습니까? 비슷한 점이 있습니다 상황이없는 언어를위한 레마를 펌핑합니다 언어의 문자열을 다섯 부분으로 나누고 UVXYZ, 그리고 언어의 모든 인스턴스가있는 곳 UV나xy나지, I ≥ 0의 경우, 지금은 있습니다 둘 복제되거나 펌핑 될 수있는 "비 터미널" 당신이 같은 숫자를 가지고있는 한.

정기적 인 문법과 문맥의 차이점 :(n, σ, p, s) : 터미널, 비 터미널, 생산, 시작 상태 터미널 기호 시작

● 공식 문법으로 정의 된 언어의 기본 기호

● ABC

비 터미널 기호 (또는 구문 변수)

● 생산 규칙에 따라 터미널 기호 그룹으로 대체

● ABC

정기 문법 : 오른쪽 또는 왼쪽 일반 문법 오른쪽 정기 문법, 모든 규칙은 형태에 따릅니다.

  1. B → A 여기서 B는 N의 비 터미널이고 A는 σ의 터미널입니다.
  2. B → AC 여기서 B와 C는 N이고 A는 σ입니다.
  3. B → ε 여기서 b는 n이고 ε은 빈 줄, 즉 길이의 줄을 나타냅니다.

정기적 인 문법을 남기면 모든 규칙은 형태에 따라야합니다

  1. a → a 여기서 a는 n의 비 터미널이고 a는 σ의 터미널입니다.
  2. a → ba는 a와 b가 n에 있고 a는 σ입니다.
  3. a → ε 여기서 a는 n이고 ε는 빈 줄입니다.

컨텍스트 자유 문법 (CFG)

○ 모든 생산 규칙이 형식 V → W 인 공식 문법

○ V는 단일 비 터미널 기호입니다

○ W는 일련의 터미널 및/또는 비 터미널입니다 (W는 비어있을 수 있음)

정규 표현

  • 어휘 분석의 기초
  • 일반 언어를 나타냅니다

맥락이없는 문법

  • 구문 분석의 기초
  • 언어 구성을 나타냅니다

enter image description here

일반 문법 :- 다음과 같이 생산을 포함하는 문법은 rg입니다.

V->TV or VT
V->T

여기서 v = 변수 및 t = 터미널

RG는 왼쪽 선형 문법 또는 오른쪽 라이너 문법 일 수 있지만 중간 선형 문법은 아닙니다.

우리가 알고 있듯이 모든 RG는 선형 문법이지만 왼쪽 선형 또는 오른쪽 선형 문법 만 RG입니다.

일반 문법은 모호 할 수 있습니다.

S->aA|aB
A->a
B->a

모호한 문법 :- 문자열 X의 경우 하나 이상의 LMD 또는 RMD 이상 또는 하나 이상의 구문 분석 트리 또는 하나의 LMD 및 하나의 RMD가 존재하지만 둘 다 다른 구문 분석 트리를 생성합니다.

                S                   S

              /   \               /   \
             a     A             a     B
                    \                   \
                     a                   a

이 문법은 두 개의 구문 분석 나무 때문에 모호한 문법입니다.

CFG :- 생산이 형성되면 CFG라고 말한 문법.

   V->@   where @ belongs to (V+T)*

DCFL :- 우리가 알다시피 모든 DCFL은 LL (1) 문법이고 모든 LL (1)은 LR (1)이므로 결코 모호하지 않습니다. 따라서 DCFG는 결코 모호하지 않습니다.

우리는 또한 모든 RL이 DCFL이므로 RL은 결코 모호하지 않습니다. RG는 모호 할 수 있지만 RL은 아닙니다.

CFL : CFL은 모호하거나 모호하지 않을 수 있습니다.

메모: RL은 본질적으로 모호하지 않습니다.

모든 생산 규칙에 양식이있는 경우 문법이없는 문법이 없습니다. (즉, 규칙의 왼쪽은 단일 변수 일 수 있습니다. 오른쪽은 제한되지 않으며 모든 단자 및 변수 시퀀스 일 수 있습니다). 우리는 v가 유한 세트 (변수), _는 유한 세트 (터미널), s는 시작 변수, r은 유한 규칙 세트이며 각각 매핑입니다. V
일반 문법은 오른쪽 또는 왼쪽 선형 인 반면 컨텍스트 자유 문법은 기본적으로 단자와 비 터미널의 모든 조합입니다. 따라서 우리는 일반 문법이 상황이없는 문법의 하위 집합이라고 말할 수 있습니다. 이러한 속성 후에는 컨텍스트 자유 언어 세트에도 일반 언어 세트도 포함되어 있다고 말할 수 있습니다.

기본적으로 일반 문법은 컨텍스트가없는 문법의 하위 집합이지만, 모든 컨텍스트 자유 문법이 일반 문법이라고 말할 수는 없습니다. 주로 상황이없는 문법은 모호하며 일반 문법은 모호 할 수 있습니다.

일반 그레이머는 선형이 왼쪽 또는 오른쪽 선형이기 때문에 결코 모호하지 않으므로 일반 그레이머를 위해 두 개의 의사 결정 트리를 만들 수 없으므로 항상 명확하지 않습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top