문맥 자유 문법이 주어지면 생성 된 언어를 찾으십시오.

Question

이 문법에 의해 생성 된 언어를 찾기 위해 프로덕션 규칙을 수동으로 적용해야합니까? 지루하고, 속도를 높이기위한 트릭/팁이 있습니까?

G = {{S, B}, {a, b}, P, S} 
P = {S -> aSa | aBa, B -> bB | b} 

편집 : 그 비 터미널 기호에 의해 생성 된 각 언어에 대해 생각하고 그들을 결합되어, 좋은 Matajon의 답변을 발견했다.

하지만이 같은 일부 복잡한 예를 해결해야 할 때 여전히 붙어있어 :

G = {{S, R, T}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, P, S} 

P = {S -> A | AS | BR | CT, 
    R -> AR | BT | C | CS, 
    T -> AT | B | BS | CR, 
    A -> 0 | 3 | 6 | 9, 
    B -> 1 | 4 | 7, 
    C -> 2 | 5 | 8} 

미친, 그렇지? 과거 시험 (프로그래밍 언어 과정)에서 가져 왔습니다.

Answer 1

나는 일반적인 트릭을 모르지만 대개 각 비 - 터미널에서 생성 된 언어에 대해 생각하는 것이 도움이됩니다.

B에서 생성 된 예제 언어는 분명히 L(B) = {b}^+입니다. 그런 다음 S 규칙에 대해 생각해보십시오. 첫 번째 규칙을 사용하면 sentencial forms {a^n.S.a^n | n >= 1}을 생성 할 수 있습니다. 이 sentencial 양식이나 S에서만 두 번째 규칙을 사용하면 sentencial 양식 {a^n.B.a^n | n >= 1}을 생성 할 수 있습니다.

나머지는 세트가 아닌 튜플이다 문법 터미널과 비끝의 정의에, 그런데 L(G) = {a^n.b^+.a^n | n >= 1}

을이 두 가지를 결합하여 얻을 매우 쉽습니다. 그리고 세 번째 구성 요소는 시작 규칙이 아닌 생산 규칙입니다. 따라서 G = {{S, B}, {a, b}, P, S}을 써야합니다.

편집 실제로

훨씬 단순한 요리 책 같은 것을 따라 생각하지 않고 두 번째 예를 해결하는 방법이있다. 왜냐하면 두 번째 문맥 - 자유 문법에 의해 생성 된 언어는 실제로 규칙 적이기 때문입니다.

처음 세 개의 규칙을 A, B 및 C에 대한 규칙을 대체

, 당신은

P' = {S -> 0 | 3 | 6 | 9 | 0S | 3S | 6S | 9S | 1R | 4R | 7R | 2T | 5T | 8T 
    R -> 0R | 3R | 6R | 9R | 1T | 4T | 7T | 2 | 5 | 8 | 2S | 5S | 8S 
    T -> 0T | 3T | 6T | 9T | 1 | 4 | 7 | 1S | 4S | 7S | 2R | 5R | 8R} 

그리고 P' 정규 문법입니다 얻을. 그렇기 때문에 비 결정적인 유한 오토 마톤으로 변환 할 수 있습니다 (실제로 간단한 방법이 있습니다). 그런 다음 결과 NFA를 정규 표현식으로 변환합니다 (이 방법은 간단하지 않지만 알고리즘을 따르고 길을 잃지는 마십시오. , 너 괜찮을거야). 그리고 그것은 정규 표현식에서 설명하는 언어를 쉽게 알 수 있습니다. 이 언어에 대한 NFA를 일단

또한, 당신이 그것을보고 그것을 논리적으로 무엇을 결정할 수 있습니다 (이것은 1,4,7 및 2,5,8 단어와 자신의 차이 mod 3의 카운트 함께 할 수있는 뭔가가. 그것을 통해 생각을 afterall :-))

물론 문맥이없는 문법으로 정규 언어를 생성하지 않으면이 트릭을 사용할 수 없습니다. 문법이 생성하는 언어 (CFG의 언어 평등 문제는 해결할 수 없음)를 알 수있는 일반적인 방법은 없습니다. 모든 단일 예를 생각하고 논리적 구조에서 유사점과 패턴을 찾아야합니다.

Answer 2

제작 규칙을 적용하면됩니다.