홀수 길이의 언어를 생성하는 문맥 - 자유 문법을 제공합니다. {w = 0 * 1 * : | w | 이상한 경우}

Question

Σ = {0,1}을 통해 다음 언어를 생성하는 컨텍스트없는 문법을 제공하십시오. {w = 0 * 1 * : | w | 0 | | 1 개

A-> 0A |^

B-> (1B) |^

그러나 사용이 문법

S-> AB : 홀수}

내 솔루션입니다 우리는 짝수 개의 문자열을 생성 할 수 있습니다.

난 L을 생성 할 문법 0100011100101100000111110000100011 = {...}

Answer 1

홀수 문장하므로 홀수 및 짝수의 합 언어는 0의 홀수, 1의 짝수 또는 0의 짝수 뒤에 1이 홀수 인 언어입니다. 또한, 홀수는 짝수 + 1입니다. 우리가 앞의 설명에서 그 치환을하면 "0의 짝수, 0 또는 1, 그 다음에는 1의 짝수"가 나온다. 모든 짝수는 0 또는 2 이상의 짝수이기 때문에 결국 끝납니다.

S -> A 0 B | A 1 B 
A -> ε | A 0 0 
B -> ε | B 1 1 

또는

S -> 0 | 1 | 0 0 S | S 1 1