일반 언어를 확인하십시오.

Question

나는 정규 언어를 식별하는 데 상당히 분실했습니다. |

나는 R은 일반 언어 다음 인 경우는 = RR 경우 R의 연결이기 때문에, 따라서 정규 언어

입니다 그러나 B = {전주 것을 알고 w < - R} 정기?

내 첫 번째 본능은 예였습니다. 왜냐하면 그것은 또한 R의 연결이기도합니다. 그러나 그것이 연결의 부분 집합이기 때문에 나는 그런 식으로 그것을 증명할 수 없다고 느낍니다. 그렇다면 w는 정규 언어의 문자열이기 때문에 생각하고있었습니다. 이것은 싱글 톤을 연결 한 다음 연결을 연결하는 것입니다. 그런 식으로 생각한다면 그게 아닌 것 같아요. 이제는 그렇지 않다고 말하는 경향이 있습니다. 왜냐하면 나는 그것에 대한 정규 표현식을 정말로 찾을 수 없기 때문이다. 펌핑 보조 정리를 사용하려고했지만이 예제에 적용하기가 정말로 어렵습니다.

누군가 제안 할 수 있습니까? 내가 따라야 할 올바른 길조차 대단 할 것입니까?

Answer 1

앞서 가서 펌프 보조 정리를 시도하십시오. 예를 들어, 정말 간단한 정규 표현식으로 시작

R = ab* 

이 때문에 당신이 정기적 아니라는 것을 증명하려고하는이 시점에서, 당신이 필요로하는 모든 하나의 반례이다. 따라서 R 중에서 원하는 것을 선택할 수 있습니다. (위는 정상적으로 작동합니다.)