상황에 맞는 문법

Question

나는 다음과 같은 언어에 대해 설명 상황에 맞는 문법을 찾고 있어요 :

L = { ww | w ∈ {a,b}*, |w| ≥ 1} <br> 

나는 사실에 문제가있어이 그 같은 X 같은 어떤 규칙이 없다 -> ε 사용할 수 있으며 그러므로 나는 단어의 "중간"을 나타내는 비단 말을 둘 수 없다. 문제의 트릭이 있습니까?
답변을 알고있는 경우 도움을 받으십시오.

Answer 1

물론 이것은 실제로 쉽습니다. 상황에 맞는 문법에서는 LHS에 문자열을 포함 할 수 있습니다. 그것이 바로 맥락입니다.

abababWababab 

좋아, 그래서 당신은 우수

W := -empty- 

같은 규칙을 원하지 않는 : 그럼이 같은 문자열로 끝날 가정 해 봅시다. 이 규칙은 어때? 물론

aWa := aa 
aWb := ab 
bWa := ba 
bWb := bb 

, 이것은 당신이 비어 있지 않은 문자열을 할거야 확신하지 않는 한 W을 도입하지 않도록해야합니다 것을 의미한다.