누구나이 문맥없는 문법을 나에게 설명 할 수 있습니까?

Question

숙제 때문에이 점을 이해해야합니다. 당신은 나에게이 말을함으로써 나에게 대답을주지 않을 것이고, 당신은 단순히 질문받는 것을 이해하도록 도와 줄 것이다.

인터넷에서 문맥이없는 문법 정보를 검색하는 것뿐만 아니라별로 도움이되지 않은 수업 노트를 읽었습니다. 나는 내가 뭘 봤는지 알 수 없으며, 나는 매우 혼란 스럽다.

누군가이 CFG의 내용을 설명하거나이 주제를 설명 할 수있는 좋은 자료를 제공하면 정말 감사하겠습니다.

S는 시작 심볼

<S> → <A> | ε 
<A> → 0<B> | 1<A> 
<B> → 0<C> | 1<B> 
<C> → 0<D> | 1<C> 
<D> → 1<D> | 0<B> | ε 

Answer 1

CFG 문자열의 패턴을 정의하고있다 :

는 CFG이있다.

여기서 문자열은 1,0, e. (영문)의 패턴 일 수 있습니다. CFG 규칙은 표현식을 영문자 문자열로 확장하는 방법을 알려줍니다. 여기 A

<S> → <A> | ε 
<A> → 0<B> | 1<A> 
<B> → 0<C> | 1<B> 
<C> → 0<D> | 1<C> 
<D> → 1<D> | 0<B> | ε 

은 0B 1A 또는 확장 될 수있다. LHS는 확장 만 가능합니다.

문자열이 주어지면 CFG에 의해 설명되는지 여부를 확인할 수 있습니다.

1000 개를 가져와이 CFG에서 설명하는지 확인하십시오.

우리는 A 또는 e로 확장 할 수있는 S로 시작합니다.

expr = S 

e는 문자열의 종료를 나타내는 특수 기호입니다. e으로 끝나는 대신 희망을 주므로 A을 사용합니다.

expr = A  (S ->A) 

A는 0B 또는 1A로 확장 될 수 있습니다. 우리는 1A를 사용합니다.

expr = 1A  (A ->1A) 

이제 1A에는 A가 있습니다. 규칙 테이블 A를 검색하면 0B 또는 1A로 확장 될 수 있습니다. 주어진 문자열 뒤에 오는 0B를 취합니다. 이제 결과는 10B입니다.

0C 또는 1B로 확장되는 찾아보기 B. 주어진 패턴과 일치하기 때문에 0C를 사용합니다. 그러므로 우리의 끈은 100C가됩니다.

expr = 100C (B -> 0C) 

마찬가지로 표현식을 확장하고 e를 사용하여 종료 할 수 있습니다.

expr = 1000D (C -> 0D) 
expr = 1000e (D -> e) 

Answer 2

는 CFG : 문맥 - 자유 문법 (CFG)이 공식 grammar.In의 문맥 자유 문법의 특정 유형을 설명하는 공식 언어 이론에서 사용되는 용어입니다, 모든 규칙은, 일대일 하나 문맥 자유 문법에 의해 생성 된 언어는 문맥 자유 언어 (CFL)로 알려져 있습니다. 다른 문맥 자유 문법은 동일한 문맥 자유 언어를 생성 할 수 있습니다.언어의 속성과 특정 문법의 속성을 구별하는 것이 중요합니다. 언어 평등 문제 (두 문맥 자유 문법은 동일한 언어를 생성합니까?)는 결정 불가능합니다. 우리가 CFG에서 설명 될 수 문자열의 집합을 찾으려고 주어진

위 라인은 CFG에서, 짧은 그래서 CFG

에서 부분을 선택합니다. 이러한 일련의 문자열은 특정 CFG의 언어를 만듭니다. 솔루션에서

는, 직사각형 상자에 문자열이 종료 단계는 다음과 같습니다

다음은 그래픽 형태로 질문의 솔루션입니다.

{100, 0,100, 1,001, 1,010, 01,001, 10,011, 10,101, 010,011, 0,100,111, ...} 그래서

이 CFG :

따라서 주어진 CFG 같은 문자열을 가질 수있다

1. 적어도 하나 (1), 적어도 두 개의 0
2. 및

3. 길이> = 3, 관찰 우리는 최소 길이를 얻을으로서 ST : 갖는 열의 임의의 유형을 가질 수있다 링 (100)가 될 수 있습니다

그리고 당신은 쉽게 CFG는 세 가지 속성 이상이 문자열의 모든 유형을 가질 수 있음을 얻을 수 있습니다 각 단계에 문자열을 관찰하여

S --> A --> 1B --> 10C --> 100D --> 100e --> 100 

.

그래서이 CFG는 3 가지 이상의 속성을 가진 문맥 자유 언어를 설명합니다.