0
나는 유한 오토마타 & 문법 시험을 위해 공부하고 나는이 질문에 붙어 : L = {A^NB^MC^2 N :어떻게이 언어를 생성하는 문법을 만들 수 있습니까? 문법 문맥 자유 문법
는 L을 생성하는 문법을 구축 | n> = 0, m> = 0}
어떻게이 언어를 생성하는 문법을 만들 수 있습니까? 문법 문맥 자유 문법 자동 기계
A
답변
0
나는 이것이 트릭을해야한다고 생각한다. http://mdaines.github.io/grammophone/에서 확인했습니다.
S -> a B c c | a S c c | .
B -> b B | .
0
나는 작은 문자열에서 큰 문자열을 만드는 방법에 대한 몇 가지 규칙을 생각해 내기 위해 항상 이러한 종류의 질문에 도움이되는 것으로 알고 있습니다. 첫째로, 당신의 언어로 littlest 끈을 확인하십시오. 우리의 경우, 우리는 n = 0이면 b^m이 우리의 언어라는 관찰로부터 시작할 수 있습니다. 즉, b * 안에있는 w는 우리의 언어입니다. x가 우리 언어의 문자열이라면 오른쪽에 왼쪽에 a를 추가하고 오른쪽에 두 개의 c를 추가하여 다른 문자열을 얻습니다. 즉 axcc는 우리 언어의 문자열이기도합니다. L에서
- ㄱ * L에서 x는 다음에 axcc 경우
- 는 L CFG의 관점에서이 글을 쓰는 는
지금은 간단하다 : 그래서 우리의 규칙은
S -> B
S -> aScc
여기서 S는 우리의 언어 L을 생성하고 B는 언어 b *를 생성합니다.
(1) S -> B
(2) S -> aScc
(3) B -> e
(4) B -> B
모든 문자열 A를^NB^MC^규칙 2의 N 개의 애플리케이션을 이용하여 생성 될 수있다 2N 규칙 (1)의 1 개 애플리케이션 m 애플리케이션 우리는 시작 심볼의 B와 B에 대한 * 문법을 제공함으로써 문법을 완료 규칙 4의 1 번 적용과 규칙 3의 1 번 적용.이 문법은 언어가 아닌 문자열을 생성하지 않으므로 연습으로 남겨 둡니다.
[필수적으로 링크로 구성된 답변을 게시하지 마십시오.] (http://stackoverflow.com/questions/how-to-answer). 당신의 대답에 중요한 포인트들을 포함 시키십시오; 추가 정보 또는 참조 용 링크를 남겨 두십시오. – techspider
가장자리 주변을 조심하십시오. 예를 들어 b의 문자열 만 생성 할 수는 없습니다. 그 대답은 당신이 여기에 어떻게 도착했는지 토론하는 데 도움이 될 것입니다. – Patrick87
나는 또한이 주제에서 초보자이며 또한 오버플로를 스택에 넣는다. 나를 고쳐 줘서 고마워. 내 대답을 편집하거나 왜 내 솔루션이 잘못 되었는가를 설명해야합니까? –