이 언어를 생성하는 문법을 어떻게 구성 할 수 있습니까?

Question

나는 유한 Automata & Grammars 테스트를 공부하고 있으며이 질문에 집착하고 있습니다.

Construct a grammar that generates L:
L = {a^n b^m c^m+n|n>=0, m>=0}

나는 내 작품 이이 라인을 따라 가야한다고 생각합니다.

    S->aA | aB
    B->bB | bC
    C->cC | c Here's where I have doubts

C에 대한 내 생산은 어떻게 m과 n의 수를 기억할 수 있습니까? 나는 이것이 상황이없는 문법이어야한다고 생각합니다. 그렇다면 어떻게해야합니까?

Answer 1

그것은 다음과 같아야합니다.

A->aAc | aBc | ac | epsilon
B->bBc | bc | epsilon

시공 과정에서 C'C가 계산되도록 강요해야합니다. 상황이 없음을 보여주기 위해 사용하는 것을 고려할 것입니다. 펌프 레마.

Answer 2

예, 이것은 숙제처럼 들리지만 힌트 :

'A'와 일치 할 때마다 'C'와 일치해야합니다. 'b'일치하는 것도 마찬가지입니다.

Answer 3

S -> X
X -> aXc | Y
Y -> bYc | e

어디 e == epsilon 그리고 X 불필요하지만 명확성을 위해 추가됩니다

Answer 4

s-> asc | a-> bac | λ

이것은 당신이 최소한 1 c를 가지고 있거나 A와 B를 얻는 경우 2 c를 가져야한다는 것을 의미합니다. 도움이 되었기를 바랍니다

Answer 5

글쎄요, 이것이 내가 할 수있는 방법입니다.

P={S::=X|epsilon,
   X::=aXc|M|epsilon,
   M::=bMc|epsilon}