kleene star 가 나와서 보는 word problem

ㅇ(93.135) 2011.10.08 17:32:30

조회 74 추천 0 댓글 9

알파벳 A 를 문자들의 집합이라 하고, <A> = U(AU-A)^n, n 은 0 포함 자연수라 하자. (A={a,b} 라 할때 -A={-a,-b} 이고 a-a=-aa=람다, 람다는

아무것도 없는거.)

<A|R> 에서 R 은 <A> 에 정의된 임의의 relation, 예를들어 A={a,b} 라 하고 R={ab=a, bbb=-b} 라 하면 ababbbb=(ab)a(bbb)b=aa(-bb)=aa 이런식.

word problem 이란 A 와 R 이 둘다 유한집합이라 할때, <A|R> 에서 어떤 원소를 끄집어내어 입력하면 그 원소가 람다(아무것도 없는 aa^-1 이런거.)일때

1, 아닐때 0 을 출력하는 프로그램(알고리듬)이 존재하지 않는 A 와 R 이 존재함미다.

난 이거 존나 신기했는데, 훃들은 어떻슴요?

고정닉 0

전체 댓글 0개

등록순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	지금 결혼하면 스타 하객 많이 올 것 같은 '인맥왕' 스타는?	운영자	24/10/28	-	-
279126	유군 형은 봅니다. [3]	좋은아버지	11.10.08	65	0
279125	책추천점요 [2]	메보	11.10.08	49	0
279123	팩토리얼 계산시 [2]	일광면(119.198)	11.10.08	83	0
279122	중고 알라딘 쩐다 [5]	막장갤신학생	11.10.08	108	0
279121	넷북 필요하다는 플갤러 보셈	마타버터	11.10.08	98	0
279120	횽들은 이런 자랑거리 없지? [4]	로하로하알로하	11.10.08	101	0
279119	기억에 남는 디자인 패턴 [4]	[성대아싸]	11.10.08	158	0
279118	갤 시발들아 [5]	3군게이머	11.10.08	101	0
279117	개발이라는게 새로운 가치를 창출하는거지....	.3(36.38)	11.10.08	67	0
279116	정확히 말하자면, 프로그램을 만드는거 아니냐? [6]	3군게이머	11.10.08	98	0
279115	여기서 물어봐도되나요? ..컴관련과 학생분들.. [15]	ㅁㄴㅇㄹ(14.41)	11.10.08	228	0
279114	간단한 프로그래밍 조차 못하는 [4]	로하로하알로하	11.10.08	113	0
279113	프로그래밍 배우면 좋은점이 뭐냐? [15]	3군게이머	11.10.08	244	0
279111	과연 내 꿈을 이룰수 있을까? [4]	쵸쵸(219.251)	11.10.08	62	0
279110	시험기간이군	三didas	11.10.08	41	0
279108	바닥부터 공부해보려고 하는데 [4]	좋은아버지	11.10.08	98	0
279107	혹시 여기 디자인 패턴에 대해 많이 공부해본 형 있어? [10]	좋은아버지	11.10.08	167	0
279105	리눅스 환경에서 stdin버퍼 어케 비움? [17]	로하로하알로하	11.10.08	164	0
279104	삼성 까는데 몰랐다니!!!	전간디	11.10.08	78	0
279103	오오오 오늘 프갤은!!! [3]	쿄스케	11.10.08	62	0
279102	종로 중고 알라진 서점 괜찬흠?? [5]	막장갤신학생	11.10.08	91	0
279101	아나 오늘 프갤 떡밥 공부좀 해야겟네	오마이갓넬	11.10.08	40	0
279100	프갤 정모한적잇음? [1]	오마이갓넬	11.10.08	48	0
279099	그나저나 캐꼬횽 오늘없나 ㅜ	어떡해	11.10.08	36	0
279098	아직 뻥뻥 소리 안들리는거보니. 불꽃은 아직인가??	1234(110.11)	11.10.08	32	0
279097	윈도우7 64bit에서 사용할만한 가벼운 IDE툴 없을깡??? [4]	1234(110.11)	11.10.08	95	0
279096	기업은 윤리적이여야 하는가? [1]	Deskjet(220.75)	11.10.08	63	0
279095	휴우... 키노트 자막 파트 8,9 완성. [3]	RUMO	11.10.08	62	0
279094	윤리적인 기업이 될려면_ [2]	좋은아버지	11.10.08	48	0
279093	형들안녕?ㅋㅋㅋㅋㅋㅋㅋㅋ [2]	Sayrin	11.10.08	45	0
279092	오늘 프갤은 [1]	좋은아버지	11.10.08	34	0
279091	토요일날 일하는 노예가 실존하냐 ㄷㄷㄷㄷ [3]	쵸쵸(219.251)	11.10.08	75	0
279090	으아! 퇴근한다! [3]	Aven(112.171)	11.10.08	58	0
279089	원래 앱이라는 호환성 개판인건 과도기적인 것일뿐. [1]	쵸쵸(219.251)	11.10.08	70	0
279088	삼성이 너님들한테 윤리적인 이유 [2]	막장갤신학생	11.10.08	78	0
279086	그런데 윤리적인 기업이라는 게 있습니다. [9]	어떡해	11.10.08	146	0
279085	이 처자 쩐다.. [1]	SODMaster	11.10.08	146	0
279084	가기전에 쓴소리... [5]	물속의다이아(211.49)	11.10.08	94	0
279082	아 맞다 한국에 윤리적인 기업 하나 있다. [1]	막장갤신학생	11.10.08	81	0
279080	오픈지엘 시작부터 막힙니다..고수형님 뭐가 문제인지 좀 봐주세요 ㅠㅠㅠㅠ [3]	OpenUp(112.155)	11.10.08	69	0
279079	기업에 윤리는 무슨... [1]	SODMaster	11.10.08	49	0
279078	저는 물다횽의 "오늘의 떡밥 총정리" 결과를 인정할 수 없습니다 [2]	오사카(211.44)	11.10.08	75	0
279077	저는 막장횽이랑 비슷한 시각인데 뭐라 말을 잘못하겠음 ㅇㅇ [7]	[성대아싸]	11.10.08	103	0
279075	세상의 중심에서 섹스를 외치다	SODMaster	11.10.08	62	0
279074	그러면 이쯤에서 문제 [19]	로하로하알로하	11.10.08	123	0
279073	횽들 오버라이딩할때 접근제어자 범위가 왜 좁아지면 안되는거야? [1]	이잉이(119.192)	11.10.08	93	0
279072	오늘 떡밥 총정리... [2]	물속의다이아(211.49)	11.10.08	86	0
279071	야근데 프갤에서 안철수 까면 어떻게 되냐? [1]	1(121.182)	11.10.08	67	0
279070	물속의 다이아 이 병슨은	막장갤신학생	11.10.08	55	0
279069	자바쓰레드 sleep(1000)이랑 wait(1000)이랑차이가 뭐냐 [1]	abbey road	11.10.08	157	0