본문 바로가기

전체 글

 (97)
클리니 폐포 클리니 폐포(Kleene closure) 의 정의는 다음과 같습니다.알파벳 Σ 위의 언어 L이 있을 때,L의 클리니 폐포 L*는 다음과 같이 정의됩니다.L* = L⁰ ∪ L¹ ∪ L² ∪ L³ ∪ …여기서L⁰ = {ε} (ε는 빈 문자열)L¹ = LL² = L × L (L에 속하는 문자열을 두 번 연결한 모든 문자열 집합)L³ = L × L × L (세 번 연결)…(계속 반복됨)즉, L의 클리니 폐포는 언어 L의 문자열들을 0개 이상 반복하여 생성할 수 있는 모든 문자열의 집합입니다.
정규 언어 정규 언어(Regular language)의 정의는 다음과 같습니다.정규 언어란 유한 오토마타가 인식(수락)할 수 있는 언어를 의미합니다.또는, 정규 표현식(regular expression)을 이용하여 표현될 수 있는 언어라고 정의할 수도 있습니다.---정규 언어의 형식적 정의정규 언어는 다음의 방법으로 정의할 수 있습니다.알파벳 Σ에 대하여 다음과 같이 재귀적으로 정의된 언어를 정규 언어라 합니다.1. 공집합 ∅은 정규 언어입니다.2. 빈 문자열 {ε}은 정규 언어입니다.3. 임의의 기호 a∈Σ에 대해 {a}는 정규 언어입니다.4. 두 정규 언어 L₁과 L₂에 대하여,합집합(L₁∪L₂)연결(L₁L₂)클리니 폐포(L₁*)위 연산으로 생성되는 언어도 정규 언어입니다.
유한 오토마타와 튜링머신의 차이 유한 오토마타와 튜링 머신의 주요 차이는 다음과 같습니다.1. 기억 장치(메모리)유한 오토마타유한 개의 상태(state)만 존재하고 추가적인 무제한 기억 장치가 없습니다.상태의 개수가 유한하므로 기억 용량이 제한되어 있습니다.튜링 머신무한한 길이의 테이프를 기억 장치로 사용하며, 읽고 쓰기가 모두 가능합니다.무제한의 기억 용량을 가집니다.2. 전이와 동작 방식유한 오토마타입력 문자열을 왼쪽에서 오른쪽으로 한 번만 읽습니다.입력 문자열을 다시 읽거나 수정할 수 없습니다.튜링 머신테이프 위의 정보를 양방향으로 이동하며 여러 번 읽고 쓸 수 있으며, 테이프 위 내용을 수정할 수 있습니다.3. 인식 가능한 언어의 범위유한 오토마타정규 언어(regular language)만 인식 가능합니다.튜링 머신재귀적으로 열..

티스토리툴바