기출3

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은 정규언어가 될 수 없다