10 정칙표현

정칙표현 (regular expression) 언어를 표현하는 간단한 표현 유한 오토마톤에서 수리되는 언어의 클라스는, 정칙표현으로 나타나지는 언어의 클래스와 같다. UNIX커멘드행의 *, ?등 연접 Σ를 기호의 유한집합, L1, L2를 Σ의 유한집합이라 할때, 집합 { xy | x∈L1, y∈L2 }가 연접 L1L2로 표현 L1으로부터 취한 아무 원의 뒤에 L2의 아무 원을 계속해서 쓸수 있는 열의 전체 연접의 예 L1={10, 1}, L2={011, 11} 일때 L1L2={10011, 1011, 111} L은 집합이므로 1011은 하나만 포함된다. 폐포 L의 Kleene폐포 폐포의 예 폐포와 정폐포 L*는 임의개의 L의 원을 연접해서 만들어지는 어의 전체 L+는 L*중 0개의 경우(ε)를 제외한 것 L자체가 ε을 표현할때만 L+가 ε를 포함 폐포의 성질 LL*=L+ L*L*=L* L*L+=L+L*=L+ L+L+=LL+ 정칙표현의 정의 ∅는 정칙표현으로, 나타내는 집합은 공집합 ε...

원문링크 : 10 정칙표현