a^n b^n 이 정규 언어가 아님을 증명
=> 언어 L={a^n b^n : n>=0} 이 정규언어라고 가정하자
L을 인식하는 결정적 유한 오토마타 DFA M=(Q,{a,b,},δ,q_0, F)가 존재한다
모든 i에 대한 확장 정의 함수 δ*(q_0 , a^i )를 고려 할 때
i의 갯수는 무한이고 M의 상태갯수는 유한
유한 오토마타는 한정된 기억장소를 가진다
따라서 a^n b^n은 정규언어가 될 수 없다
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment